Low-Rank Matrix Approximations with Flip-Flop Spectrum-Revealing QR Factorization

Yuehua Feng, Jianwei Xiao, Ming Gu

Abstract

We present Flip-Flop Spectrum-Revealing QR (Flip-Flop SRQR) factorization, a significantly faster and more reliable variant of the QLP factorization of Stewart, for low-rank matrix approximations. Flip-Flop SRQR uses SRQR factorization to initialize a partial column pivoted QR factorization and then compute a partial LQ factorization. As observed by Stewart in his original QLP work, Flip-Flop SRQR tracks the exact singular values with "considerable fidelity". We develop singular value lower bounds and residual error upper bounds for Flip-Flop SRQR factorization. In situations where singular values of the input matrix decay relatively quickly, the low-rank approximation computed by SRQR is guaranteed to be as accurate as truncated SVD. We also perform a complexity analysis to show that for the same accuracy, Flip-Flop SRQR is faster than randomized subspace iteration for approximating the SVD, the standard method used in Matlab tensor toolbox. We also compare Flip-Flop SRQR with alternatives on two applications, tensor approximation and nuclear norm minimization, to demonstrate its efficiency and effectiveness.

Introduction

In modern machine learning and big data analytics, the Singular Value Decomposition (SVD) serves as the gold standard for identifying the low-rank structure of massive datasets. However, as data dimensions scale into the millions, the computational cost of a full SVD becomes a significant bottleneck. While faster alternatives like QR factorization with column pivoting (QRCP) and randomized subspace iteration exist, they often face a trade-off between speed and accuracy. Specifically, "greedy" pivoting strategies may fail to capture the full spectrum of a matrix, leading to suboptimal approximations.

This paper introduces Flip-Flop Spectrum-Revealing QR (Flip-Flop SRQR), a high-performance algorithm designed to bridge this gap. By refining the classical QLP factorization—which involves a QR factorization followed by an LQ factorization—with randomized techniques and spectrum-revealing checks, Flip-Flop SRQR achieves the accuracy of a truncated SVD at a fraction of the computational cost.

Methodology

The Flip-Flop SRQR algorithm improves upon traditional low-rank approximation methods through a three-stage process:

  1. Initialization via Truncated Randomized QRCP (TRQRCP): The algorithm begins by computing a partial QR factorization. To accelerate this, it employs Gaussian random projections to compress the matrix, allowing for much faster column pivoting than traditional deterministic methods.
  2. Spectrum-Revealing Step: To ensure the approximation is high-quality, the algorithm performs a "spectrum-revealing" check. If the initial randomized pass fails to capture the singular values with sufficient accuracy, the algorithm performs pair-wise column swaps. This acts as a safety net, correcting the "unlucky" outcomes that can occasionally occur in randomized algorithms.
  3. The "Flip-Flop" (Partial LQ Factorization): Following the QR step, the algorithm performs a partial LQ factorization on the resulting upper triangular matrix. This "flip-flop" ensures that the diagonal elements of the final matrix track the true singular values of the original matrix with high fidelity.

By focusing only on the rank-$k$ components needed (truncation), the algorithm avoids the expensive trailing matrix updates that typically slow down standard QR methods.

Theoretical Guarantees

A key contribution of this work is the development of rigorous mathematical bounds for the Flip-Flop SRQR factorization. The authors prove that for matrices where singular values decay relatively quickly—a common characteristic in real-world datasets—Flip-Flop SRQR is guaranteed to be as accurate as the truncated SVD. Furthermore, complexity analysis demonstrates that Flip-Flop SRQR is more efficient than randomized subspace iteration (RSISVD) for achieving a target level of accuracy.

Experimental Results

The effectiveness of Flip-Flop SRQR was evaluated across several diverse applications and datasets:

Tensor Approximation and MNIST Classification

In the context of Sequentially Truncated Higher-Order SVD (ST-HOSVD), Flip-Flop SRQR significantly outperformed the standard RSISVD used in the Matlab Tensorlab toolbox. The speed advantage became more pronounced as the target rank $k$ increased.

On the MNIST dataset (70,000 handwritten digits), the algorithm was used for a classification task. It achieved an accuracy of 94.98%, nearly matching the full HOSVD accuracy of 95.19%. Crucially, the training time was reduced from 27.2 seconds to just 1.5 seconds, demonstrating a massive gain in efficiency without a meaningful loss in performance.

Robust PCA and Matrix Completion

The algorithm was also tested on Robust PCA (separating low-rank matrices from sparse noise) and collaborative filtering.

  • Robust PCA: The IALM_FFSRQR variant was faster than popular methods like LANSVD and RSISVD while maintaining comparable error rates.
  • Collaborative Filtering: On the MovieLens 1M dataset, Flip-Flop SRQR achieved a lower Normalized Mean Absolute Error (NMAE) and faster execution times compared to randomized subspace iteration alternatives.

Conclusion

Flip-Flop SRQR provides a robust and efficient framework for low-rank matrix approximation. By combining the speed of randomization with the reliability of spectrum-revealing swaps, it offers a compelling alternative to both traditional SVD and existing randomized methods. While the current implementation shows significant speedups, future work will focus on reducing remaining overhead and extending the algorithm to distributed memory architectures to handle the next generation of massive-scale data analytics.

Summary updated

Abstract

We present Flip-Flop Spectrum-Revealing QR (Flip-Flop SRQR) factorization, a significantly faster and more reliable variant of the QLP factorization of Stewart, for low-rank matrix approximations. Flip-Flop SRQR uses SRQR factorization to initialize a partial column pivoted QR factorization and then compute a partial LQ factorization. As observed by Stewart in his original QLP work, Flip-Flop SRQR tracks the exact singular values with "considerable fidelity". We develop singular value lower bounds and residual error upper bounds for Flip-Flop SRQR factorization. In situations where singular values of the input matrix decay relatively quickly, the low-rank approximation computed by SRQR is guaranteed to be as accurate as truncated SVD. We also perform a complexity analysis to show that for the same accuracy, Flip-Flop SRQR is faster than randomized subspace iteration for approximating the SVD, the standard method used in Matlab tensor toolbox. We also compare Flip-Flop SRQR with alternatives on two applications, tensor approximation and nuclear norm minimization, to demonstrate its efficiency and effectiveness.
BibTeX
@inproceedings{feng2019low,
  author = {Yuehua Feng and Jianwei Xiao and Ming Gu},
  title = {{Low-Rank Matrix Approximations with Flip-Flop Spectrum-Revealing QR Factorization}},
  booktitle = {ETNA},
  year = {2019},
  doi = {10.1553/etna\_vol51s469},
}
Figure