Fetching the paper…
Reading the bibliography…
Recently, Musco and Woodruff (FOCS, 2017) showed that given an $n \times n$ positive semidefinite (PSD) matrix $A$, it is possible to compute a $(1+\epsilon)$-approximate relative-error low-rank approximation to $A$ by querying $O(nk/\epsilon^{2.5})$ entries of $A$ in time $O(nk/\epsilon^{2.5} +n k^{\omega-1}/\epsilon^{2(\omega-1)})$.
Metric spaces and positive definite functions
Isaac J Schoenberg · 1938
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Chi-Chin Yao · 1977
Earlier work this paper cites.
The classification of finite connected hypermetric spaces
Paul Terwilliger and Michel Deza · 1987
Earlier work this paper cites.
The electrical resistance of a graph captures its commute and cover times
Ashok K Chandra, Prabhakar Raghavan, Walter L Ruzzo, Roman Smolensky, and Prasoon Tiwari · 1996
Earlier work this paper cites.
Authoritative sources in a hyperlinked environment
Jon M Kleinberg · 1999
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.
Spectral partitioning of random graphs
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.
Computing the nearest correlation matrix—a problem from finance
Nicholas J Higham · 2002
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.
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.
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
Shuchi Chawla, Anupam Gupta, and Harald Räcke · 2005
Earlier work this paper cites.
A very short proof of cauchy’s interlace theorem for eigenvalues of hermitian matrices
Steve Fisk · 2005
Earlier work this paper cites.
The spectral method for general mixture models
Ravindran Kannan, Hadi Salmasian, and Santosh Vempala · 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.
Improved approximation algorithms for large matrices via random projections
Tamas Sarlos · 2006
Earlier work this paper cites.
Fréchet embeddings of negative type metrics
Sanjeev Arora, James R Lee, and Assaf Naor · 2007
Earlier work this paper cites.
Generalized rank-constrained matrix approximations
Shmuel Friedland and Anatoli Torokhti · 2007
Earlier work this paper cites.
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson and Roman Vershynin · 2007
Cited alongside, same era.
Euclidean distortion and the sparsest cut
Sanjeev Arora, James Lee, and Assaf Naor · 2008
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Cited alongside, same era.
Numerical linear algebra in the streaming model
Kenneth L Clarkson and David P Woodruff · 2009
Cited alongside, same era.
Geometry of cuts and metrics
Michel Marie Deza and Monique Laurent · 2009
Cited alongside, same era.
Multiclass support vector classification via coding and regression
Pei-Chun Chen, Kuang-Yao Lee, Tsung-Ju Lee, Yuh-Jye Lee, and Su-Yun Huang · 2010
Cited alongside, same era.
Optimal approximate matrix product in terms of stable rank
Michael B Cohen, Jelani Nelson, and David P Woodruff · 2015
Later among the works it cites.
Efficient inverse maintenance and faster algorithms for linear programming
Yin Tat Lee and Aaron Sidford · 2015
Later among the works it cites.
Fast generation of random spanning trees and the effective resistance metric
Aleksander Madry, Damian Straszak, and Jakub Tarnawski · 2015
Later among the works it cites.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B Cohen · 2016
Later among the works it cites.
Quantum recommendation systems
Iordanis Kerenidis and Anupam Prakash · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum state tomography via compressed sensing
David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert · 2010
Cited alongside, same era.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
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-means, pca and projective clustering
Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2013
Cited alongside, same era.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B. Cohen, Cameron Musco, and Christopher Musco · 2017
Later among the works it cites.
Low-rank psd approximation in input-sparsity time
Kenneth L Clarkson and David P Woodruff · 2017
Later among the works it cites.
Improving Efficiency by Shrinkage: The James–Stein and Ridge Regression Estimators
Marvin Gruber · 2017
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, CN Musco, Christopher Paul Musco, and Aaron Sidford · 2017
Later among the works it cites.
Recursive sampling for the nystrom method
Cameron Musco and Christopher Musco · 2017
Later among the works it cites.
Sublinear time low-rank approximation of positive semidefinite matrices
Cameron Musco and David P. Woodruff · 2017
Later among the works it cites.
Sublinear time low-rank approximation of distance matrices
Ainesh Bakshi and David Woodruff · 2018
Later among the works it cites.
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang · 2018
Later among the works it cites.
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
András Gilyén, Seth Lloyd, and Ewin Tang · 2018
Later among the works it cites.
Quantum singular-value decomposition of nonsparse low-rank matrices
Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd · 2018
Later among the works it cites.
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe · 2019
Closest in time.
Sample-optimal low-rank approximation of distance matrices
Piotr Indyk, Ali Vakilian, Tal Wagner, and David Woodruff · 2019
Closest in time.
Sublinear time numerical linear algebra for structured matrices
Xiaofei Shi and David P. Woodruff · 2019
Closest in time.
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang · 2019
Closest in time.