Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition

Yuehua Feng, Jianwei Xiao, Ming Gu

Abstract

We present the 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 computes 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 the Flip-Flop SRQR factorization. In situations where singular values of the input matrix decay relatively quickly, the low-rank approximation computed by Flip-Flop SRQR is guaranteed to be as accurate as the truncated SVD. We also perform a complexity analysis to show that Flip-Flop SRQR is faster than the randomized subspace iteration for approximating the SVD, the standard method used in the Matlab tensor toolbox. We additionally compare Flip-Flop SRQR with alternatives on two applications, a tensor approximation and a nuclear norm minimization, to demonstrate its efficiency and effectiveness.
BibTeX
@inproceedings{feng2019flip,
  author = {Yuehua Feng and Jianwei Xiao and Ming Gu},
  title = {{Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition}},
  booktitle = {ETNA},
  year = {2019},
  doi = {10.1553/etna\_vol51s469},
}

Loading related content...

Figure