An Efficient, Sparsity-Preserving, Online Algorithm for Low-Rank Approximation
It offers a practical, sparsity-preserving low-rank approximation method for large-scale data analysis, addressing the need for efficient and interpretable matrix factorizations.
The paper introduces Spectrum-Revealing LU (SRLU), a novel truncated LU factorization for low-rank matrix approximation, and provides a fast algorithm with error bounds. Experiments show SRLU preserves sparsity, is efficiently updatable, and achieves near-optimal approximation accuracy.
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 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.