Michael B. Cohen - the MLDC 3 participants

Michael B. Cohen
Are you Michael B. Cohen?

Claim your profile, edit publications, add additional information:

Contact Details

Name
Michael B. Cohen
Affiliation
the MLDC 3 participants
Location

Pubs By Year

External Links

Pub Categories

 
Computer Science - Data Structures and Algorithms (14)
 
General Relativity and Quantum Cosmology (6)
 
Computer Science - Learning (4)
 
Mathematics - Group Theory (4)
 
Statistics - Machine Learning (2)
 
Mathematics - Dynamical Systems (2)
 
Mathematics - Numerical Analysis (2)
 
Statistics - Methodology (2)
 
Computer Science - Computer Vision and Pattern Recognition (1)
 
Physics - Statistical Mechanics (1)
 
Computer Science - Robotics (1)
 
Physics - Physics and Society (1)
 
Mathematics - Combinatorics (1)
 
Mathematics - Optimization and Control (1)
 
Mathematics - Geometric Topology (1)
 
Computer Science - Computational Geometry (1)
 
Mathematics - Probability (1)
 
Computer Science - Numerical Analysis (1)

Publications Authored By Michael B. Cohen

In this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We provide algorithms for both these problems that, ignoring logarithmic factors involving the dimension of the input matrix and the size of its entries, both run in time $\widetilde{O}\left(m\log \kappa \log^2 (1/\epsilon)\right)$ where $\epsilon$ is the amount of error we are willing to tolerate. Here, $\kappa$ represents the ratio between the largest and the smallest entries of the optimal scalings. Read More

In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Read More

In this paper, we provide faster algorithms for computing various fundamental quantities associated with random walks on a directed graph, including the stationary distribution, personalized PageRank vectors, hitting times, and escape probabilities. In particular, on a directed graph with $n$ vertices and $m$ edges, we show how to compute each quantity in time $\tilde{O}(m^{3/4}n+mn^{2/3})$, where the $\tilde{O}$ notation suppresses polylogarithmic factors in $n$, the desired accuracy, and the appropriate condition number (i.e. Read More

In this paper we provide faster algorithms for solving the geometric median problem: given $n$ points in $\mathbb{R}^{d}$ compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite an abundance of research the previous fastest algorithms for computing a $(1+\epsilon)$-approximate geometric median were $O(d\cdot n^{4/3}\epsilon^{-8/3})$ by Chin et. al, $\tilde{O}(d\exp{\epsilon^{-4}\log\epsilon^{-1}})$ by Badoiu et. Read More

We apply the framework of Rosendal to study the large-scale geometry of the topological groups $\Diff_+^k(M^1)$, consisting of orientation-preserving $C^k$-diffeomorphisms (for $1\leq k\leq\infty$) of a compact $1$-manifold $M^1$ ($=I$ or $\mathbb{S}^1$). We characterize the relative property (OB) in such groups: $A\subseteq\Diff_+^k(M^1)$ has property (OB) relative to $\Diff_+^k(M^1)$ if and only if $\displaystyle\sup_{f\in A}\sup_{x\in M^1}|\log f'(x)|<\infty$ and $\displaystyle\sup_{f\in A}\sup_{x\in M^1}|f^{(j)}(x)|<\infty$ for every integer $2\leq j\leq k$. We deduce that $\Diff_+^k(M^1)$ has the local property (OB), and consequently a well-defined non-trivial quasi-isometry class, if and only if $k<\infty$. Read More

In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching problem, the unit-capacity minimum-cost maximum flow problem and the weighted perfect bipartite $b$-matching problem under the assumption that $\Vert b\Vert_1=O(m)$. We show that each one of these four problems can be solved in $\tilde{O}(m^{10/7}\log W)$ time, where $W$ is the absolute maximum weight of an edge in the graph, which gives the first in over 25 years polynomial improvement in their sparse-graph time complexity. At a high level, our algorithms build on the interior-point method-based framework developed by Madry (FOCS 2013) for solving unit-capacity maximum flow problem. Read More

Finding a small spectral approximation for a tall $n \times d$ matrix $A$ is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows are sampled from those of $A$. Row sampling improves interpretability, saves space when $A$ is sparse, and preserves row structure, which is especially important, for example, when $A$ represents a graph. Read More

The recent work by Marcus, Spielman and Srivastava proves the existence of bipartite Ramanujan (multi)graphs of all degrees and all sizes. However, that paper did not provide a polynomial time algorithm to actually compute such graphs. Here, we provide a polynomial time algorithm to compute certain expected characteristic polynomials related to this construction. Read More

We present a new algorithm for finding a near optimal low-rank approximation of a matrix $A$ in $O(nnz(A))$ time. Our method is based on a recursive sampling scheme for computing a representative subset of $A$'s columns, which is then used to find a low-rank approximation. This approach differs substantially from prior $O(nnz(A))$ time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. Read More

We show that the topological groups $Diff_{+}^{1}(I)$ and $Diff_{+}^{1}(\mathbb{S}^1)$ of orientation-preserving $C^1$-diffeomorphisms of the interval and the circle, respectively, admit finitely generated dense subgroups. We also investigate the question of genericity (in the sense of Baire category) of such finite topological generating sets in related groups. We show that the generic pair of elements in the homeomorphism group $Homeo_+(I)$ generate a dense subgroup of $Homeo_+(I)$. Read More

We prove, using the subspace embedding guarantee in a black box way, that one can achieve the spectral norm guarantee for approximate matrix multiplication with a dimensionality-reducing map having $m = O(\tilde{r}/\varepsilon^2)$ rows. Here $\tilde{r}$ is the maximum stable rank, i.e. Read More

Deployment of high-penetration photovoltaic (PV) power is expected to have a range of effects -- both positive and negative -- on the distribution grid. The magnitude of these effects may vary greatly depending upon feeder topology, climate, PV penetration level, and other factors. In this paper we present a simulation study of eight representative distribution feeders in three California climates at PV penetration levels up to 100\%, supported by a unique database of distributed PV generation data that enables us to capture the impact of PV variability on feeder voltage and voltage regulating equipment. Read More

Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes the closeness of the points in the same cluster, even if the Euclidean cluster diameter is large. Therefore, it is preferred to assign smaller costs to the paths that stay close to the input points. Read More

We give a simple algorithm to efficiently sample the rows of a matrix while preserving the p-norms of its product with vectors. Given an $n$-by-$d$ matrix $\boldsymbol{\mathit{A}}$, we find with high probability and in input sparsity time an $\boldsymbol{\mathit{A}}'$ consisting of about $d \log{d}$ rescaled rows of $\boldsymbol{\mathit{A}}$ such that $\| \boldsymbol{\mathit{A}} \boldsymbol{\mathit{x}} \|_1$ is close to $\| \boldsymbol{\mathit{A}}' \boldsymbol{\mathit{x}} \|_1$ for all vectors $\boldsymbol{\mathit{x}}$. We also show similar results for all $\ell_p$ that give nearly optimal sample bounds in input sparsity time. Read More

We show how to approximate a data matrix $\mathbf{A}$ with a much smaller sketch $\mathbf{\tilde A}$ that can be used to solve a general class of constrained k-rank approximation problems to within $(1+\epsilon)$ error. Importantly, this class of problems includes $k$-means clustering and unconstrained low rank approximation (i.e. Read More

Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Read More

The group $\mathop{\rm PL}_+(I)$ of increasing piecewise linear self-homeomorphisms of the interval $I=[0,1]$ may not be assigned a topology in such a way that it becomes a Polish group. The same statement holds for the groups $\mathop{\rm Homeo}_+^{Lip}(I)$ of bi-Lipschitz homeomorphisms of $I$, and $\mathop{\rm Diff}_+^{1+\epsilon}(I)$ of diffeomorphisms of $I$ whose derivatives are H\"older continuous with exponent $\epsilon$. Read More

We obtain a simple obstruction to embedding groups into the analytic diffeomorphism groups of 1-manifolds. Using this, we classify all RAAGs which embed into $\mathrm{Diff}_{+}^{\omega }(\mathbb{S}^1)$. We also prove that a branch group does not embed into $\mathrm{Diff}_{+}^{\omega }(\mathbb{S}^1)$. Read More

We show that preconditioners constructed by random sampling can perform well without meeting the standard requirements of iterative methods. When applied to graph Laplacians, this leads to ultra-sparsifiers that in expectation behave as the nearly-optimal ones given by [Kolla-Makarychev-Saberi-Teng STOC`10]. Combining this with the recursive preconditioning framework by [Spielman-Teng STOC`04] and improved embedding algorithms, this leads to algorithms that solve symmetric diagonally dominant linear systems and electrical flow problems in expected time close to $m\log^{1/2}n$ . Read More

We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discounting highly stretched edges by taking their $p$-th power for some $0 < p < 1$, is directly related to performances of existing algorithms. This discounting of high-stretch edges allows us to treat many classes of edges with coarser granularity. Read More

We present a real-time approach for image-based localization within large scenes that have been reconstructed offline using structure from motion (Sfm). From monocular video, our method continuously computes a precise 6-DOF camera pose, by efficiently tracking natural features and matching them to 3D points in the Sfm point cloud. Our main contribution lies in efficiently interleaving a fast keypoint tracker that uses inexpensive binary feature descriptors with a new approach for direct 2D-to-3D matching. Read More

We examine the structure of the event horizon for numerical simulations of two black holes that begin in a quasicircular orbit, inspiral, and finally merge. We find that the spatial cross section of the merged event horizon has spherical topology (to the limit of our resolution), despite the expectation that generic binary black hole mergers in the absence of symmetries should result in an event horizon that briefly has a toroidal cross section. Using insight gained from our numerical simulations, we investigate how the choice of time slicing affects both the spatial cross section of the event horizon and the locus of points at which generators of the event horizon cross. Read More

We describe an expansion of Legendre polynomials, analogous to the Taylor expansion, to approximate arbitrary functions. We show that the polynomial coefficients in Legendre expansion, therefore the whole series, converge to zero much more rapidly compared to the Taylor expansion of the same order. Furthermore, using numerical analysis using sixth-order polynomial expansion, we demonstrate that the Legendre polynomial approximation yields an error at least an order of magnitude smaller than the analogous Taylor series approximation. Read More

Wavelet coefficients are estimated recursively at progressively coarser scales recursively. As a result, the estimation is prone to multiplicative propagation of truncation errors due to quantization and round-off at each stage. Yet, the influence of this propagation on wavelet filter output has not been explored systematically. Read More

We present numerical simulations of a Kerr black hole perturbed by a pulse of ingoing gravitational radiation. For strong perturbations we find up to five concentric marginally outer trapped surfaces. These trapped surfaces appear and disappear in pairs, so that the total number of such surfaces at any given time is odd. Read More

A network of observable, macroscopic cosmic (super-)strings may have formed in the early universe. If so, the cusps that generically develop on cosmic-string loops emit bursts of gravitational radiation that could be detectable by both ground- and space-based gravitational-wave interferometers. Here we report on two versions of a LISA-oriented string-burst search pipeline that we have developed and tested within the context of the Mock LISA Data Challenges. Read More

2009Dec
Affiliations: 1the Mock LISA Data Challenge Task Force, 2the Mock LISA Data Challenge Task Force, 3the Mock LISA Data Challenge Task Force, 4the Mock LISA Data Challenge Task Force, 5the Mock LISA Data Challenge Task Force, 6the Mock LISA Data Challenge Task Force, 7the Mock LISA Data Challenge Task Force, 8the Mock LISA Data Challenge Task Force, 9the Mock LISA Data Challenge Task Force, 10the Mock LISA Data Challenge Task Force, 11the Mock LISA Data Challenge Task Force, 12the Mock LISA Data Challenge Task Force, 13the MLDC 3 participants, 14the MLDC 3 participants, 15the MLDC 3 participants, 16the MLDC 3 participants, 17the MLDC 3 participants, 18the MLDC 3 participants, 19the MLDC 3 participants, 20the MLDC 3 participants, 21the MLDC 3 participants, 22the MLDC 3 participants, 23the MLDC 3 participants, 24the MLDC 3 participants, 25the MLDC 3 participants, 26the MLDC 3 participants, 27the MLDC 3 participants, 28the MLDC 3 participants, 29the MLDC 3 participants, 30the MLDC 3 participants

The Mock LISA Data Challenges are a program to demonstrate LISA data-analysis capabilities and to encourage their development. Each round of challenges consists of one or more datasets containing simulated instrument noise and gravitational waves from sources of undisclosed parameters. Participants analyze the datasets and report best-fit solutions for the source parameters. Read More

Research on extracting science from binary-black-hole (BBH) simulations has often adopted a "scattering matrix" perspective: given the binary's initial parameters, what are the final hole's parameters and the emitted gravitational waveform? In contrast, we are using BBH simulations to explore the nonlinear dynamics of curved spacetime. Focusing on the head-on plunge, merger, and ringdown of a BBH with transverse, antiparallel spins, we explore numerically the momentum flow between the holes and the surrounding spacetime. We use the Landau-Lifshitz field-theory-in-flat-spacetime formulation of general relativity to define and compute the density of field energy and field momentum outside horizons and the energy and momentum contained within horizons, and we define the effective velocity of each apparent and event horizon as the ratio of its enclosed momentum to its enclosed mass-energy. Read More

Event horizons are the defining physical features of black hole spacetimes, and are of considerable interest in studying black hole dynamics. Here, we reconsider three techniques to localise event horizons in numerical spacetimes: integrating geodesics, integrating a surface, and integrating a level-set of surfaces over a volume. We implement the first two techniques and find that straightforward integration of geodesics backward in time to be most robust. Read More

We discuss the exact solutions of various models of the statistics of dimer coverings of a Bethe lattice. We reproduce the well-known exact results for noninteracting hard-core dimers by both a very simple geometrical argument and a general algebraic formulation for lattice statistical problems. For the Bethe lattice we also obtain the exact solution when either a) the dimers interact via a short-range interaction or b) the underlying lattice is anisotropic. Read More