arXiv Analytics

Sign in

arXiv:1705.06730 [cs.DS]AbstractReferencesReviewsResources

Algorithms for $\ell_p$ Low Rank Approximation

Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff

Published 2017-05-18Version 1

We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entrywise $\ell_p$-approximation error, for any $p \geq 1$; the case $p = 2$ is the classical SVD problem. We obtain the first provably good approximation algorithms for this version of low-rank approximation that work for every value of $p \geq 1$, including $p = \infty$. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.

Related articles: Most relevant | Search more
arXiv:1104.4597 [cs.DS] (Published 2011-04-24)
The Entropy Rounding Method in Approximation Algorithms
arXiv:1804.10696 [cs.DS] (Published 2018-04-27)
Low Rank Approximation in the Presence of Outliers
arXiv:1207.6365 [cs.DS] (Published 2012-07-26, updated 2013-04-05)
Low Rank Approximation and Regression in Input Sparsity Time