65 citations · 187 across the 18 of their papers we have counts for
5 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 …
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Michael B. Cohen, Sam Elder, Cameron Musco +2
We show how to approximate a data matrix with a much smaller sketch that can be used to solve a general class of constrained k-rank approximation p…
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…
Preconditioning in Expectation
Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki +2
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…