Simple and practical algorithms for $\ell_p$-norm low-rank approximation

Anastasios Kyrillidis
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:413-423, 2018.

Abstract

We propose practical algorithms for entrywise ‘p-norm low-rank approximation, for p = 1 or p = 1. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approx- imations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain (1 + ")- OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desider- ata only assuming algorithm’s hyperparame- ters are known apriori—or are at least approx- imable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46].

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-kyrillidis18a, title = {Simple and practical algorithms for $\ell_p$-norm low-rank approximation}, author = {Kyrillidis, Anastasios}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {413--423}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/kyrillidis18a/kyrillidis18a.pdf}, url = {https://proceedings.mlr.press/r16/kyrillidis18a.html}, abstract = {We propose practical algorithms for entrywise ‘p-norm low-rank approximation, for p = 1 or p = 1. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approx- imations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain (1 + ")- OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desider- ata only assuming algorithm’s hyperparame- ters are known apriori—or are at least approx- imable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46].}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Simple and practical algorithms for $\ell_p$-norm low-rank approximation %A Anastasios Kyrillidis %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-kyrillidis18a %I PMLR %P 413--423 %U https://proceedings.mlr.press/r16/kyrillidis18a.html %V R16 %X We propose practical algorithms for entrywise ‘p-norm low-rank approximation, for p = 1 or p = 1. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approx- imations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain (1 + ")- OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desider- ata only assuming algorithm’s hyperparame- ters are known apriori—or are at least approx- imable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46]. %Z Reissued by PMLR on 04 October 2026.
APA
Kyrillidis, A.. (2018). Simple and practical algorithms for $\ell_p$-norm low-rank approximation. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:413-423 Available from https://proceedings.mlr.press/r16/kyrillidis18a.html. Reissued by PMLR on 04 October 2026.

Related Material