Volume 51, pp. 469-494, 2019.

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

Yuehua Feng, Jianwei Xiao, and 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.

Full Text (PDF) [468 KB], BibTeX

Key words

QR factorization, randomized algorithm, low-rank approximation, approximate SVD, higher-order SVD, nuclear norm minimization

AMS subject classifications

15A18, 15A23, 65F99

< Back