93 citations · 537 across the 73 of their papers we have counts for
7 papers · 2 filters
Row Sampling by Lewis Weights
Michael B. Cohen, Richard Peng
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 -by- matrix …
Approximate Undirected Maximum Flows in O(m polylog(n)) Time
Richard Peng
We give the first O(m polylog(n)) time algorithms for approximating maximum flows in undirected graphs and constructing polylog(n) -quality cut-approximating hierarchical tree deco…
Partitioning Well-Clustered Graphs: Spectral Clustering Works!
Richard Peng, He Sun, Luca Zanetti
In this paper we study variants of the widely used spectral clustering that partitions a graph into k clusters by (1) embedding the vertices of a graph into a low-dimensional space…
Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models
Dehua Cheng, Yu Cheng, Yan Liu +2
Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical…
Uniform Sampling for Matrix Approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco +3
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…
Stretching Stretch
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki +2
We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discoun…