Dimensionality Reduction for k-Means Clustering and Low Rank Approximation

By Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu. 2014

380 citations recorded by the source corpus.

We show how to approximate a data matrix A with a much smaller sketch ~A that can be used to solve a general class of constrained k-rank approximation problems to within (1+ε) error. Importantly, this class includes k-means clustering and unconstrained low rank approximation (i.e. principal component analysis). By reducing data points to just O(k) dimensions, we generically accelerate any exact, approximate, or heuristic algorithm for these ubiquitous problems. For k-means dimensionality reduction, we provide (1+ε) relative error results for many common sketching techniques, including random row projection, column selection, and approximate SVD. For approximate principal component analysis, we give a simple alternative to known algorithms that has applications in the streaming setting. Additionally, we extend recent work on column-based matrix reconstruction, giving column subsets that not only 'cover' a good subspace for A}, but can be used directly to compute this subspace. Finally, for k-means clustering, we show how to achieve a (9+ε) approximation by Johnson-Lindenstrauss projecting data to just O(log k/ε2) dimensions. This is the first result that leverages the specific structure of k-means to achieve dimension independent of input size and sublinear in k.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Scalable Fair Clustering (2019, methodology): “The running time can be reduced further by applying dimensionality reduction techniques, see, e.g., Cohen et al. (2015); Makarychev et al. (2018) and the references therein.”
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering (2018, methodology): “For k -means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu [CEM + 15].”
Core‐sets: An updated survey (2019, methodology): “Never-theless, most of the coresets use uniform sampling after proper scaling by sup-weights which enables smaller coresets using the notion of ε -sample (see Section 6; Cohen et al., 2015; Feldman & Langberg, 2011; Li et al., 2001).”
Practical Coreset Constructions for Machine Learning (2017, background): “Cohen et al. [2015] improved the latter result by a constant factor by projecting to a set of (random) orthonormal vectors approximating the right singular vectors of A .”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “There are other versions of approximate matrix product, such as those that replace the Frobenius norms above with operator norms [83, 82, 29, 30].”
Compressive Spectral Clustering (2016, background): “Finally, we mention works (Boutsidis et al., 2011; Cohen et al., 2015) that concentrate on reducing the feature vectors’ dimension in the k -means problem, but do not sidestep the eigendecomposition nor the large N issues.”
Communication-Optimal Distributed Clustering (2016, background): “[7] study dimensionality reduction techniques for the input data matrices that can be used for distributed k-means.”
k-Means for Streaming and Distributed Big Sparse Data (2015, background): “Coresets of size O(k/ε) that are based on projections on low-dimensional subspaces that diminishes the sparsity of the input data were recently suggested in [8] by improving the analysis in [12].”
Optimal principal component analysis in distributed and streaming models (2015, methodology): “(Dense Johnson-Lindenstrauss matrix ) [part of Theorem 12 in [20]] For ε 1 , suppose each entry of W ∈ R n × ξ is chosen O ( k ) -wise independently and uniformly in { 1 / √ ξ, − 1 / √ ξ } where ξ = O ( kε − 2 ) [17].”
Weighted low rank approximations with provable guarantees (2016, background): “Low rank approximation is arguably one of the most wellstudied problems in randomized numerical linear algebra, with diverse applications to clustering [19, 23, 38, 18], data mining [5], distance matrix completion [13], information retrieval [45], learning mixtures of distributions [2, 32], recommen”
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering (2018, methodology): “Our choice of ˜ A is AS , where S is a scaled Rademacher matrix of target dimension m ∈ O ( k/ε 2 ) , see Theorem 12 of [14].”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, background): “Specifically,Z is typically taken to be the top k left singular vectors of AΠ or ofA projected ontoAΠ [32, 4].”