Algorithms for $\ell_p$ Low-Rank Approximation
Abstract
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 robust version of low-rank approximation that work for every value of $p$. 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.
Cite
Text
Chierichetti et al. "Algorithms for $\ell_p$ Low-Rank Approximation." International Conference on Machine Learning, 2017.Markdown
[Chierichetti et al. "Algorithms for $\ell_p$ Low-Rank Approximation." International Conference on Machine Learning, 2017.](https://mlanthology.org/icml/2017/chierichetti2017icml-algorithms/)BibTeX
@inproceedings{chierichetti2017icml-algorithms,
title = {{Algorithms for $\ell_p$ Low-Rank Approximation}},
author = {Chierichetti, Flavio and Gollapudi, Sreenivas and Kumar, Ravi and Lattanzi, Silvio and Panigrahy, Rina and Woodruff, David P.},
booktitle = {International Conference on Machine Learning},
year = {2017},
pages = {806-814},
volume = {70},
url = {https://mlanthology.org/icml/2017/chierichetti2017icml-algorithms/}
}