Low Rank Approximation and Regression in Input Sparsity Time
arXiv:1207.6365
Abstract
We design a new distribution over $\poly(r \eps^{-1}) \times n$ matrices so that for any fixed matrix of rank , with probability at least 9/10, $\norm{SAx}_2 = (1 \pm \eps)\norm{Ax}_2$ simultaneously for all . Such a matrix is called a \emph{subspace embedding}. Furthermore, can be computed in $\nnz(A) + \poly(d \eps^{-1})$ time, where $\nnz(A)$ is the number of non-zero entries of . This improves over all previous subspace embeddings, which required at least time to achieve this property. We call our matrices \emph{sparse embedding matrices}. Using our sparse embedding matrices, we obtain the fastest known algorithms for $(1+\eps)$-approximation for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and -regression. The leading order term in the time complexity of our algorithms is $O(\nnz(A))$ or $O(\nnz(A)\log n)$. We optimize the low-order $\poly(d/\eps)$ terms in our running times (or for rank- approximation, the $n*\poly(k/eps)$ term), and show various tradeoffs. For instance, we also use our methods to design new preconditioners that improve the dependence on $\eps$ in least squares regression to $\log 1/\eps$. Finally, we provide preliminary experimental results which suggest that our algorithms are competitive in practice.
Included optimization of subspace embedding dimension from (d/eps)^4 to O~(d/eps)^2 in Section 4, by more careful analysis of perfect hashing, and minor improvements to regression / low rank approximation because of it