Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
From MaRDI portal
Publication:5218403
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5161643 (Why is no real title available?)
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 2045481 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- A BLAS-3 Version of the QR Factorization with Column Pivoting
- A DEIM induced CUR factorization
- A Multilinear Singular Value Decomposition
- A Singular Value Thresholding Algorithm for Matrix Completion
- A Storage-Efficient $WY$ Representation for Products of Householder Transformations
- A new truncation strategy for the higher-order singular value decomposition
- A randomized algorithm for principal component analysis
- ARPACK Users' Guide
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Authoritative sources in a hyperlinked environment
- Dimensionality reduction in higher-order signal processing and rank-\((R_1,R_2,\ldots,R_N)\) reduction in multilinear algebra
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Eigentaste: A constant time collaborative filtering algorithm
- Exact matrix completion via convex optimization
- Extensions of Lipschitz mappings into a Hilbert space
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Fixed point and Bregman iterative methods for matrix rank minimization
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- HOID: higher order interpolatory decomposition for tensors based on Tucker representation
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Handwritten digit classification using higher order singular value decomposition
- Hankel matrix rank minimization with applications to system identification and realization
- Interior-point method for nuclear norm approximation with application to system identification
- LAPACK Users' Guide
- Nuclear norm system identification with missing inputs and outputs
- Numerical methods for solving linear least squares problems
- On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
- On the convergence of Stewart's QLP algorithm for approximating the SVD
- On the rank minimization problem over a positive semidefinite linear matrix inequality
- Orthogonal tensor decompositions
- Principal component analysis.
- Randomized QR with column pivoting
- Rank-one approximation to high order tensors
- Robust principal component analysis?
- Singular Value Decomposition, Eigenfaces, and 3D Reconstructions
- Stewart's pivoted QLP decomposition for low‐rank matrices
- Structure-Preserving Sparse Decomposition for Facial Expression Analysis
- Subspace Iteration Randomization and Singular Value Problems
- Tensor Decompositions and Applications
- The QLP Approximation to the Singular Value Decomposition
- The University of Florida sparse matrix collection
- The WY Representation for Products of Householder Matrices
- The geometry of graphs and some of its algorithmic applications
- Using Linear Algebra for Intelligent Information Retrieval
Cited in
(3)
Describes a project that uses
Uses Software
This page was built for publication: Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218403)
