93 citations · 388 across the 44 of their papers we have counts for
4 papers · 1 filter
Faster Eigenvector Computation via Shift-and-Invert Preconditioning
Dan Garber, Elad Hazan, Chi Jin +4
We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix -- i.e. computing a unit vector such that …
Recursive Sampling for the Nyström Method
Cameron Musco, Christopher Musco
We give the first algorithm for kernel Nyström approximation that runs in *linear time in the number of training points* and is provably accurate for all kernel matrices, without d…
Online Row Sampling
Michael B. Cohen, Cameron Musco, Jakub Pachocki
Finding a small spectral approximation for a tall matrix is a fundamental numerical primitive. For a number of reasons, one often seeks an approximation whose rows…
Principal Component Projection Without Principal Component Analysis
Roy Frostig, Cameron Musco, Christopher Musco +1
We show how to efficiently project a vector onto the top principal components of a matrix, without explicitly computing these components. Specifically, we introduce an iterative al…