Algorithms for $\ell_p$ Low-Rank Approximation

Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:806-814, 2017.

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 this Paper

BibTeX
@InProceedings{pmlr-v70-chierichetti17a, title = {Algorithms for $\ell_p$ Low-Rank Approximation}, author = {Flavio Chierichetti and Sreenivas Gollapudi and Ravi Kumar and Silvio Lattanzi and Rina Panigrahy and David P. Woodruff}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {806--814}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/chierichetti17a/chierichetti17a.pdf}, url = {https://proceedings.mlr.press/v70/chierichetti17a.html}, 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.} }
Endnote
%0 Conference Paper %T Algorithms for $\ell_p$ Low-Rank Approximation %A Flavio Chierichetti %A Sreenivas Gollapudi %A Ravi Kumar %A Silvio Lattanzi %A Rina Panigrahy %A David P. Woodruff %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-chierichetti17a %I PMLR %P 806--814 %U https://proceedings.mlr.press/v70/chierichetti17a.html %V 70 %X 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.
APA
Chierichetti, F., Gollapudi, S., Kumar, R., Lattanzi, S., Panigrahy, R. & Woodruff, D.P.. (2017). Algorithms for $\ell_p$ Low-Rank Approximation. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:806-814 Available from https://proceedings.mlr.press/v70/chierichetti17a.html.

Related Material