Fetching the paper…
Reading the bibliography…
We present a new algorithm for finding a near optimal low-rank approximation of a matrix $A$ in $O(nnz(A))$ time.
A theorem on the difference of the generalized inverses of two nonnegative matrices
George A. Milliken and Fikri Akdeniz · 1977
Earlier work this paper cites.
Decomposable searching problems I: Static-to-dynamic transformation
Jon Louis Bentley and James B. Saxe · 1980
Earlier work this paper cites.
Sampling techniques for kernel methods
Dimitris Achlioptas, Frank Mcsherry, and Bernhard Schölkopf · 2001
Earlier work this paper cites.
Using the Nyström method to speed up kernel machines
Christopher K. I. Williams and Matthias Seeger · 2001
Earlier work this paper cites.
Efficient SVM training using low-rank kernel representations
Shai Fine and Katya Scheinberg · 2002
Earlier work this paper cites.
Approximating extent measures of points
Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan · 2004
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 Frieze, Ravi Kannan, and Santosh Vempala · 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.
On the Nyström method for approximating a gram matrix for improved kernel-based learning
Michael W. Mahoney and Petros Drineas · 2005
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition
Petros Drineas, Ravi Kannan, and Michael W. Mahoney · 2006
Earlier work this paper cites.
Sampling algorithms for ℓ 2 \ell_{2} regression and applications
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
Támas Sarlós · 2006
Earlier work this paper cites.
PCA-correlated SNPs for structure identification in worldwide human populations
Peristera Paschou, Elad Ziv, Esteban G. Burchard, Shweta Choudhry, William Rodriguez-Cintron, Michael W. Mahoney, and Petros Drineas · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2007
Earlier work this paper cites.
Relative-error CUR matrix decompositions
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan · 2008
Earlier work this paper cites.
On landmark selection and sampling in high-dimensional data analysis
Mohamed-Ali Belabbas and Patrick J. Wolfe · 2009
Earlier work this paper cites.
Spectral methods in machine learning: New strategies for very large datasets
Mohamed-Ali Belabbas and Patrick J. Wolfe · 2009
Earlier work this paper cites.
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Earlier work this paper cites.
ScalaNLP: Breeze
David Hall, Daniel Ramage, Jason Zaugg, Alexander Lehmann, Jonathan Merritt, Keith Stevens, Jason Baldridge, Timothy Hunter, Dave DeCaprio, Daniel Duckworth, Eric Christiansen, Marc Millstone, Mérő László, Alexey Noskov, Devon Bryant, Kentaroh Takagaki, Sam Halliday, Chris Stucchio, and Xiangrui Meng · 2009
Earlier work this paper cites.
CUR matrix decompositions for improved data analysis
Michael W. Mahoney and Petros Drineas · 2009
Cited alongside, same era.
redsvd: RandomizED SVD
Daisuke Okanohara · 2010
Cited alongside, same era.
Scikit-learn: Machine learning in Python
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
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.
Sharp analysis of low-rank kernel matrix approximations
Francis Bach · 2013
Cited alongside, same era.
Fast randomized kernel methods with statistical guarantees
Ahmed El Alaoui and Michael W. Mahoney · 2015
Closest in time.
Toward a unified theory of sparse dimensionality reduction in euclidean space
Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson · 2015
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.
Coherent matrix completion
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward · 2015
Closest in time.
Dimensionality reduction for k-means clustering and low rank approximation
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Efficient multi-label classification with many labels
Wei Bi and James Kwok · 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.
Revisiting the Nyström method for improved large-scale machine learning
Alex Gittens and Michael Mahoney · 2013
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
Jonathan A. Kelner and Alex Levin · 2013
Cited alongside, same era.
Simple and deterministic matrix sketching
Edo Liberty · 2013
Cited alongside, same era.
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 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.
Online row sampling
Michael B. Cohen, Cameron Musco, and Jakub Pachocki · 2015
Closest in time.
Frequent Directions: Simple and deterministic matrix sketching
Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff · 2015
Closest in time.
Randomized approximation of the Gram matrix: Exact computation and probabilistic bounds
John T. Holodnak and Ilse C. F. Ipsen · 2015
Closest in time.
Sparsified cholesky solvers for SDD linear systems
Yin Tat Lee, Richard Peng, and Daniel A. Spielman · 2015
Closest in time.
Efficient inverse maintenance and faster algorithms for linear programming
Yin Tat Lee and Aaron Sidford · 2015
Closest in time.
A faster cutting plane method and its implications for combinatorial and convex optimization
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong · 2015
Closest in time.
Randomized block krylov methods for stronger and faster approximate singular value decomposition
Cameron Musco and Christopher Musco · 2015
Closest in time.
Dimensionality reduction for k k -means clustering
Cameron Musco · 2015
Closest in time.
An introduction to matrix concentration inequalities
Joel A. Tropp · 2015
Closest in time.
Sergey Voronin and Per-Gunnar Martinsson · 2015
Closest in time.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B. Cohen · 2016
Closest in time.
An efficient parallel algorithm for spectral sparsification of laplacian and SDDM matrix polynomials
Gorav Jindal and Pavel Kolev · 2016
Closest in time.
Sparsified cholesky and multigrid solvers for connection laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman · 2016
Closest in time.
Fast DPP sampling for nyström with application to kernel methods
Chengtao Li, Stefanie Jegelka, and Suvrit Sra · 2016
Closest in time.
Provably useful kernel matrix approximation in linear time
Cameron Musco and Christopher Musco · 2016
Closest in time.