Fetching the paper…
Reading the bibliography…
We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) matrix in sublinear time, i.e., for any $n \times n$ PSD matrix $A$, in $\tilde O(n \cdot poly(k/\epsilon))$ time we output a rank-$k$ matrix $B$, in factored form, for which $\|A-B\|_F^2 \leq (1+\epsilon)\|A-A_k\|_F^2$, where $A_k$ is the best rank-$k$ approximation to $A$.
Discussion of a set of points in terms of their mutual distances
Gale Young and Alston S Householder · 1938
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chin Yao · 1977
Earlier work this paper cites.
Authoritative sources in a hyperlinked environment
Jon M. Kleinberg · 1999
Earlier work this paper cites.
Multidimensional scaling
Trevor F Cox and Michael AA Cox · 2000
Earlier work this paper cites.
Latent semantic indexing: A probabilistic analysis
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala · 2000
Earlier work this paper cites.
Spectral analysis of data
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, and Jared Saia · 2001
Earlier work this paper cites.
Web search via hub synthesis
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, and Frank McSherry · 2001
Earlier work this paper cites.
The Complexity of Massive Data Set Computations
Ziv Bar-Yossef · 2002
Earlier work this paper cites.
Competitive recommendation systems
Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan · 2002
Earlier work this paper cites.
Collaborative filtering via Gaussian probabilistic latent semantic analysis
Thomas Hofmann · 2003
Earlier work this paper cites.
Clustering large graphs via the singular value decomposition
Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay · 2004
Earlier work this paper cites.
Fast Monte-Carlo algorithms for finding low-rank approximations
Alan M. Frieze, Ravi Kannan, and Santosh Vempala · 2004
Earlier work this paper cites.
On spectral learning of mixtures of distributions
Dimitris Achlioptas and Frank McSherry · 2005
Earlier work this paper cites.
On the Nyström method for approximating a Gram matrix for improved kernel-based learning
Petros Drineas and Michael W Mahoney · 2005
Earlier work this paper cites.
Theory of semidefinite programming for sensor network localization
Anthony Man-Cho So and Yinyu Ye · 2005
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication
Petros Drineas, Ravi Kannan, and Michael W Mahoney · 2006
Earlier work this paper cites.
Subspace sampling and relative-error matrix approximation: Column-row-based methods
Petros Drineas, Michael W Mahoney, and S Muthukrishnan · 2006
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.
Adaptive sampling and fast low-rank matrix approximation
Amit Deshpande and Santosh Vempala · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamas Sarlos · 2006
Cited alongside, same era.
Fast computation of low-rank matrix approximations
Dimitris Achlioptas and Frank McSherry · 2007
Cited alongside, same era.
Random dot product graph models for social networks
Stephen J Young and Edward R Scheinerman · 2007
Cited alongside, same era.
Relative-error CUR matrix decompositions
Petros Drineas, Michael W Mahoney, and S Muthukrishnan · 2008
Cited alongside, same era.
The spectral method for general mixture models
Ravindran Kannan, Hadi Salmasian, and Santosh Vempala · 2008
Cited alongside, same era.
Improved Nyström low-rank approximation and error analysis
Kai Zhang, Ivor W Tsang, and James T Kwok · 2008
Low rank approximation of the symmetric positive semidefinite matrix
Xuefeng Duan, Jiaofen Li, Qingwen Wang, and Xinjun Zhang · 2014
Later among the works it cites.
Subspace iteration randomization and singular value problems
Ming Gu · 2014
Later among the works it cites.
Understanding alternating minimization for matrix completion
Moritz Hardt · 2014
Later among the works it cites.
Improved distributed principal component analysis
Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, and David P. Woodruff · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Later among the works it cites.
Toward a unified theory of sparse dimensionality reduction in Euclidean space
Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Spectral methods in machine learning and new strategies for very large datasets
Mohamed-Ali Belabbas and Patrick J Wolfe · 2009
Cited alongside, same era.
Exact matrix completion via convex optimization
Emmanuel J Candès and Benjamin Recht · 2009
Cited alongside, same era.
Sampling techniques for the Nyström method
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar · 2009
Cited alongside, same era.
Quantum state tomography via compressed sensing
David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert · 2010
Cited alongside, same era.
Making large-scale Nyström approximation possible
Mu Li, James Tin-Yau Kwok, and Baoliang Lu · 2010
Cited alongside, same era.
The spectral norm error of the naive Nyström extension
Alex Gittens · 2011
Cited alongside, same era.
Later among the works it cites.
Dimensionality reduction for k-means clustering and low rank approximation
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2015
Later among the works it cites.
Randomized block Krylov methods for stronger and faster approximate singular value decomposition
Cameron Musco and Christopher Musco · 2015
Later among the works it cites.
An introduction to matrix concentration inequalities
Joel A Tropp · 2015
Later among the works it cites.
Sharper bounds for regression and low-rank approximation with regularization, 2016
Haim Avron, Kenneth L. Clarkson, and David P. Woodruff · 2016
Later among the works it cites.
Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes
Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei · 2016
Later among the works it cites.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B. Cohen · 2016
Later among the works it cites.
Fast DPP sampling for Nyström with application to kernel methods
Chengtao Li, Stefanie Jegelka, and Suvrit Sra · 2016
Later among the works it cites.
Recursive sampling for the Nyström method
Cameron Musco and Christopher Musco · 2016
Later among the works it cites.
Sublinear time orthogonal tensor decomposition
Zhao Song, David P. Woodruff, and Huan Zhang · 2016
Later among the works it cites.
Randomized single-view algorithms for low-rank matrix approximation
Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher · 2016
Later among the works it cites.
SPSD matrix approximation vis column selection: theories, algorithms, and extensions
Shusen Wang, Luo Luo, and Zhihua Zhang · 2016
Later among the works it cites.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B Cohen, Cameron Musco, and Christopher Musco · 2017
Closest in time.
Low-rank PSD approximation in input-sparsity time
Ken Clarkson and David P. Woodruff · 2017
Closest in time.