An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation

David Anderson, Ming Gu
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:156-165, 2017.

Abstract

Low-rank matrix approximation is a fundamental tool in data analysis for processing large datasets, reducing noise, and finding important signals. In this work, we present a novel truncated LU factorization called Spectrum-Revealing LU (SRLU) for effective low-rank matrix approximation, and develop a fast algorithm to compute an SRLU factorization. We provide both matrix and singular value approximation error bounds for the SRLU approximation computed by our algorithm. Our analysis suggests that SRLU is competitive with the best low-rank matrix approximation methods, deterministic or randomized, in both computational complexity and approximation quality. Numeric experiments illustrate that SRLU preserves sparsity, highlights important data features and variables, can be efficiently updated, and calculates data approximations nearly as accurately as the best possible. To the best of our knowledge this is the first practical variant of the LU factorization for effective and efficient low-rank matrix approximation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-anderson17a, title = {An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation}, author = {David Anderson and Ming Gu}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {156--165}, 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/anderson17a/anderson17a.pdf}, url = {https://proceedings.mlr.press/v70/anderson17a.html}, abstract = {Low-rank matrix approximation is a fundamental tool in data analysis for processing large datasets, reducing noise, and finding important signals. In this work, we present a novel truncated LU factorization called Spectrum-Revealing LU (SRLU) for effective low-rank matrix approximation, and develop a fast algorithm to compute an SRLU factorization. We provide both matrix and singular value approximation error bounds for the SRLU approximation computed by our algorithm. Our analysis suggests that SRLU is competitive with the best low-rank matrix approximation methods, deterministic or randomized, in both computational complexity and approximation quality. Numeric experiments illustrate that SRLU preserves sparsity, highlights important data features and variables, can be efficiently updated, and calculates data approximations nearly as accurately as the best possible. To the best of our knowledge this is the first practical variant of the LU factorization for effective and efficient low-rank matrix approximation.} }
Endnote
%0 Conference Paper %T An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation %A David Anderson %A Ming Gu %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-anderson17a %I PMLR %P 156--165 %U https://proceedings.mlr.press/v70/anderson17a.html %V 70 %X Low-rank matrix approximation is a fundamental tool in data analysis for processing large datasets, reducing noise, and finding important signals. In this work, we present a novel truncated LU factorization called Spectrum-Revealing LU (SRLU) for effective low-rank matrix approximation, and develop a fast algorithm to compute an SRLU factorization. We provide both matrix and singular value approximation error bounds for the SRLU approximation computed by our algorithm. Our analysis suggests that SRLU is competitive with the best low-rank matrix approximation methods, deterministic or randomized, in both computational complexity and approximation quality. Numeric experiments illustrate that SRLU preserves sparsity, highlights important data features and variables, can be efficiently updated, and calculates data approximations nearly as accurately as the best possible. To the best of our knowledge this is the first practical variant of the LU factorization for effective and efficient low-rank matrix approximation.
APA
Anderson, D. & Gu, M.. (2017). An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:156-165 Available from https://proceedings.mlr.press/v70/anderson17a.html.

Related Material