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 $\mathbf{A}$ with a much smaller sketch $\tilde{\mathbf{A}}$ that can be used to solve a general class of constrained k-rank approximation p…