Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Open accessThe DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Least squares quantization in PCM
Lloyd, S. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056489 · Cited by 15,836
(2007) · doi:10.5555/1283383.1283494 · Cited by 7,364
Top 10 algorithms in data mining
Wu, X., Kumar, V., Ross Quinlan, J., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A., Liu, B., Yu, P. S., et al. (2008) · Knowledge and Information Systems · doi:10.1007/s10115-007-0114-2 · Cited by 5,667
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,392
NP-hardness of Euclidean sum-of-squares clustering
Aloise, D., Deshpande, A., Hansen, P., & Popat, P. (2009) · Machine Learning · doi:10.1007/s10994-009-5103-0 · Cited by 867
Computational Advertising: Techniques for Targeting Relevant Ads
Woodruff, D. P. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000060 · Cited by 866
Improved Approximation Algorithms for Large Matrices via Random Projections
Sarlos, T. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.37 · Cited by 646
SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
MIRSKY, L. (1960) · The Quarterly Journal of Mathematics · doi:10.1093/qmath/11.1.50 · Cited by 611
On coresets for k-means and k-median clustering
Har-Peled, S., & Mazumdar, S. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007400 · Cited by 527
Clustering Large Graphs via the Singular Value Decomposition
Petros Drineas, B., FRIEZE, A. M., Kannan, R., Vempala, S., & Vinay, V. (2004) · Machine Learning · doi:10.1023/b:mach.0000033113.59016.96 · Cited by 487
A local search approximation algorithm for k-means clustering
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002) · Proceedings of the eighteenth annual symposium on Computational geometry · doi:10.1145/513400.513402 · Cited by 474
Inaba, M., Katoh, N., & Imai, H. (1994) · Proceedings of the tenth annual symposium on Computational geometry - SCG '94 · doi:10.1145/177424.178042 · Cited by 321
The Planar k-Means Problem is NP-Hard
Mahajan, M., Nimbhorkar, P., & Varadarajan, K. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00202-1_24 · Cited by 308
Numerical linear algebra in the streaming model
Clarkson, K. L., & Woodruff, D. P. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536445 · Cited by 301
Simple and deterministic matrix sketching
Liberty, E. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487623 · Cited by 257
A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
Kumar, A., Sabharwal, Y., & Sen, S. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.7 · Cited by 247
Truncated Power Method for Sparse Eigenvalue Problems
Yuan, X., & Zhang, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.2679 · Cited by 238
Randomized Algorithms for Matrices and Data
Mahoney, M. W. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000035 · Cited by 232
Randomized Dimensionality Reduction for $k$ -Means Clustering
Boutsidis, C., Zouzias, A., Mahoney, M. W., & Drineas, P. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2375327 · Cited by 207
Unsupervised Feature Selection for the k-means Clustering Problem
Boutsidis, C., Petros Drineas, B., & Mahoney, M. W. (2009) · neural information processing systems · Cited by 191
Near-Optimal Column-Based Matrix Reconstruction
Boutsidis, C., Drineas, P., & Magdon-Ismail, M. (2014) · SIAM Journal on Computing · doi:10.1137/12086755x · Cited by 169
Smaller Coresets for k-Median and k-Means Clustering
Har-Peled, S., & Kushal, A. (2006) · Discrete & Computational Geometry · doi:10.1007/s00454-006-1271-x · Cited by 137
Truncated power method for sparse eigenvalue problems
YuanXiao-Tong, & ZhangTong (2013) · Journal of Machine Learning Research · doi:10.5555/2567709.2502610 · Cited by 104
Distributed k-Means and k-Median Clustering on General TopologiesPreprint
Balcan, M.-F., Ehrlich, S., & Liang, Y. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.0604 · Cited by 85
Improved Distributed Principal Component AnalysisPreprint
Balcan, M.-F., Kanchanapally, V., Liang, Y., & Woodruff, D. P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.5823 · Cited by 58
2 Deterministic Feature Selection for K-means ClusteringPreprint
Boutsidis, C., & Magdon‐Ismail, M. (n.d.) · Cited by 57
Sparse PCA through Low-rank ApproximationsPreprint
Papailiopoulos, D., Dimakis, A. G., & Korokythakis, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.0551 · Cited by 51
Deterministic Feature Selection for K-Means Clustering
Boutsidis, C., & Magdon‐Ismail, M. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2255021 · Cited by 49
Nonnegative Sparse PCA with Provable Guarantees
Asteris, M., Papailiopoulos, D., & Dimakis, A. G. (2014) · Cited by 29
Low Rank Approximation Lower Bounds in Row-Update Streams
Woodruff, D. P. (2014) · neural information processing systems · Cited by 22
Cited by
Computational Advertising: Techniques for Targeting Relevant Ads
Woodruff, D. P. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000060 · Cited by 866
Metadata
- Authors
- Cohen, M. B., Elder, S., Musco, C., Musco, C., & Persu, M.
- Venue
- Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2015-06-14
- Pages
- 163-172
- OpenAlex
- W2133157266
- Cited by
- 276
- References
- 31
- FWCI
- 16.48
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.