Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
Lists
Only you see this
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...