TY - GEN
T1 - Input sparsity time low-rank approximation via ridge leverage score sampling
AU - Musco, Christopher
AU - Cohen, Michael B.
AU - Musco, Cameron
N1 - Funding Information:
We thank Richard Peng, Christos Boutsidis, and Michael Mahoney for several valuable conversations. Michael B. Cohen is supported by NSF grant CCF- 1111109. Christopher Musco is supported by NSF grant CCF-1111109 and an NSF Graduate Research Fellowship. Cameron Musco is supported an NSF Graduate Research Fellowship, AFOSR grant FA9550-13-1-0042, and the NSF Center for Science of Information.
Publisher Copyright:
Copyright © by SIAM.
PY - 2017
Y1 - 2017
N2 - We present a new algorithm for finding a near optimal low-rank approximation of a matrix A in O(nnz(A)) time. Our method is based on a recursive sampling scheme for computing a representative subset of A's columns, which is then used to find a low-rank approximation. This approach differs substantially from prior O(nnz(A)) time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. Our algorithm matches the guarantees of the random projection methods while offering a number of advantages. In addition to better performance on sparse and structured data, sampling algorithms can be applied in settings where random projections cannot. For example, we give new streaming algorithms for the column subset selection and projection-cost preserving sample problems. Our method has also been used in the fastest algorithms for provably accurate Nystrom approximation of kernel matrices [56].
AB - We present a new algorithm for finding a near optimal low-rank approximation of a matrix A in O(nnz(A)) time. Our method is based on a recursive sampling scheme for computing a representative subset of A's columns, which is then used to find a low-rank approximation. This approach differs substantially from prior O(nnz(A)) time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. Our algorithm matches the guarantees of the random projection methods while offering a number of advantages. In addition to better performance on sparse and structured data, sampling algorithms can be applied in settings where random projections cannot. For example, we give new streaming algorithms for the column subset selection and projection-cost preserving sample problems. Our method has also been used in the fastest algorithms for provably accurate Nystrom approximation of kernel matrices [56].
UR - http://www.scopus.com/inward/record.url?scp=85016218195&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85016218195&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974782.115
DO - 10.1137/1.9781611974782.115
M3 - Conference contribution
AN - SCOPUS:85016218195
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1758
EP - 1777
BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
A2 - Klein, Philip N.
PB - Association for Computing Machinery
T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Y2 - 16 January 2017 through 19 January 2017
ER -