Fetching the paper…
Reading the bibliography…
We show how to approximate a data matrix $\mathbf{A}$ with a much smaller sketch $\mathbf{\tilde A}$ that can be used to solve a general class of constrained k-rank approximation problems to within $(1+\epsilon)$ error.
Symmetric gauge functions and unitarily invariant norms
Leon Mirsky · 1960
Earlier work this paper cites.
Least squares quantization in PCM
Stuart Lloyd · 1982
Earlier work this paper cites.
Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering
Mary Inaba, Naoki Katoh, and Hiroshi Imai · 1994
Earlier work this paper cites.
Local operator theory, random matrices and Banach spaces
Kenneth R. Davidson and Stanislaw J. Szarek · 2001
Earlier work this paper cites.
A local search approximation algorithm for k-means clustering
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu · 2002
Earlier work this paper cites.
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Dimitris Achlioptas · 2003
Earlier work this paper cites.
Clustering large graphs via the singular value decomposition
Petros Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, and V Vinay · 2004
Earlier work this paper cites.
On coresets for k-means and k-median clustering
Sariel Har-Peled and Soham Mazumdar · 2004
Earlier work this paper cites.
A simple linear time ( 1 + ϵ ) (1+\epsilon) -approximation algorithm for k k -means clustering in any dimensions
Amit Kumar, Yogish Sabharwal, and Sandeep Sen · 2004
Earlier work this paper cites.
Matrix approximation and projective clustering via volume sampling
Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Támas Sarlós · 2006
Earlier work this paper cites.
K-means++: The advantages of careful seeding
David Arthur and Sergei Vassilvitskii · 2007
Earlier work this paper cites.
Smaller coresets for k k -median and k k -means clustering
Sariel Har-Peled and Akash Kushal · 2007
Earlier work this paper cites.
NP-hardness of Euclidean sum-of-squares clustering
Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat · 2009
Earlier work this paper cites.
Unsupervised feature selection for the k k -means clustering problem
Christos Boutsidis, Michael W. Mahoney, and Petros Drineas · 2009
Earlier work this paper cites.
Numerical linear algebra in the streaming model
Kenneth Clarkson and David P. Woodruff · 2009
Earlier work this paper cites.
The planar k k -means problem is NP-hard
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan · 2009
Earlier work this paper cites.
Smallest singular value of a random rectangular matrix
Mark Rudelson and Roman Vershynin · 2009
Cited alongside, same era.
Random projections for k k -means clustering
Christos Boutsidis, Anastasios Zouzias, and Petros Drineas · 2010
Cited alongside, same era.
Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp · 2011
Cited alongside, same era.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Cited alongside, same era.
Twice-Ramanujan sparsifiers
Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Optimal column-based low-rank matrix reconstruction
Venkatesan Guruswami and Ali Kemal Sinop · 2012
Cited alongside, same era.
Sparse PCA through low-rank approximations
Dimitris Papailiopoulos, Alexandros Dimakis, and Stavros Korokythakis · 2013
Later among the works it cites.
Truncated power method for sparse eigenvalue problems
Xiao-Tong Yuan and Tong Zhang · 2013
Later among the works it cites.
Nonnegative sparse PCA with provable guarantees
Megasthenis Asteris, Dimitris Papailiopoulos, and Alexandros Dimakis · 2014
Closest in time.
Near-optimal column-based matrix reconstruction
Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail · 2014
Closest in time.
Improved distributed principal component analysis
Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, and David P. Woodruff · 2014
Closest in time.
Optimal CUR matrix decompositions
Christos Boutsidis and David P. Woodruff · 2014
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Tail inequalities for sums of random matrices that depend on the intrinsic dimension
Daniel Hsu, Sham Kakade, and Tong Zhang · 2012
Cited alongside, same era.
Distributed k k -means and k k -median clustering on general topologies
Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang · 2013
Cited alongside, same era.
Deterministic feature selection for k-means clustering
Christos Boutsidis and Malik Magdon-Ismail · 2013
Cited alongside, same era.
Low rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2013
Cited alongside, same era.
Turning big data into tiny data: Constant-size coresets for k k -means, PCA, and projective clustering
Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013
Cited alongside, same era.
Distributed PCA and k k -means clustering
Yingyu Liang, Maria-Florina Balcan, and Vandana Kanchanapally · 2013
Cited alongside, same era.
Optimal approximate matrix product in terms of stable rank
Michael B. Cohen, Jelani Nelson, and David P. Woodruff · 2014
Closest in time.
Relative errors for deterministic low-rank matrix approximations
Mina Ghashami and Jeff M. Phillips · 2014
Closest in time.
Sparser Johnson-Lindenstrauss transforms
Daniel M. Kane and Jelani Nelson · 2014
Closest in time.
Principal component analysis and higher correlations for distributed data
Ravindran Kannan, Santosh S. Vempala, and David P. Woodruff · 2014
Closest in time.
An implementation of a randomized algorithm for principal component analysis
Arthur Szlam, Yuval Kluger, and Mark Tygert · 2014
Closest in time.
Low rank approximation lower bounds in row-update streams
David P. Woodruff · 2014
Closest in time.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Closest in time.
Tighter low-rank approximation via sampling the leveraged element
Srinadh Bhojanapalli, Prateek Jain, and Sujay Sanghavi · 2015
Closest in time.
Randomized dimensionality reduction for k k -means clustering
Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, and Petros Drineas · 2015
Closest in time.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Closest in time.