Low-Rank Approximation and Regression in Input Sparsity Time
Abstract
We design a new distribution over m × n matrices S so that, for any fixed n × d matrix A of rank r , with probability at least 9/10, ∥ SAx ∥ 2 = (1 ± ε)∥ Ax ∥ 2 simultaneously for all x ∈ R d . Here, m is bounded by a polynomial in r ε − 1 , and the parameter ε ∈ (0, 1]. Such a matrix S is called a subspace embedding . Furthermore, SA can be computed in O (nnz( A )) time, where nnz( A ) is the number of nonzero entries of A . This improves over all previous subspace embeddings, for which computing SA required at least Ω( nd log d ) time. We call these S sparse embedding matrices .
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 30, 2017
- Source ID
- 10.1145/3019134
Entities
People
- David P. Woodruff
- Kenneth L. Clarkson
Organizations
- Air Force Research Laboratory
- Defense Advanced Research Projects Agency
- IBM Research