Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
From MaRDI portal
Publication:5218403
DOI10.1553/ETNA_VOL51S469zbMATH Open1433.65083arXiv1803.01982OpenAlexW3099583063WikidataQ126585298 ScholiaQ126585298MaRDI QIDQ5218403FDOQ5218403
Authors:
Publication date: 3 March 2020
Published in: ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1803.01982
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
Recommendations
randomized algorithmlow-rank approximationQR factorizationnuclear norm minimizationhigher-order SVDapproximate SVD
Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
Cites Work
- LAPACK Users' Guide
- The University of Florida sparse matrix collection
- ARPACK Users' Guide
- Principal component analysis.
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Orthogonal tensor decompositions
- Robust principal component analysis?
- A Singular Value Thresholding Algorithm for Matrix Completion
- Extensions of Lipschitz mappings into a Hilbert space
- Title not available (Why is that?)
- Tensor Decompositions and Applications
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Exact matrix completion via convex optimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Numerical methods for solving linear least squares problems
- Hankel matrix rank minimization with applications to system identification and realization
- Title not available (Why is that?)
- A Multilinear Singular Value Decomposition
- On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Eigentaste: A constant time collaborative filtering algorithm
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- Title not available (Why is that?)
- Fixed point and Bregman iterative methods for matrix rank minimization
- The geometry of graphs and some of its algorithmic applications
- Authoritative sources in a hyperlinked environment
- Title not available (Why is that?)
- Title not available (Why is that?)
- Interior-point method for nuclear norm approximation with application to system identification
- On the rank minimization problem over a positive semidefinite linear matrix inequality
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Nuclear norm system identification with missing inputs and outputs
- Rank-one approximation to high order tensors
- Using Linear Algebra for Intelligent Information Retrieval
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- A randomized algorithm for principal component analysis
- Singular Value Decomposition, Eigenfaces, and 3D Reconstructions
- Handwritten digit classification using higher order singular value decomposition
- The WY Representation for Products of Householder Matrices
- A Storage-Efficient $WY$ Representation for Products of Householder Transformations
- Dimensionality reduction in higher-order signal processing and rank-\((R_1,R_2,\ldots,R_N)\) reduction in multilinear algebra
- Structure-Preserving Sparse Decomposition for Facial Expression Analysis
- The QLP Approximation to the Singular Value Decomposition
- A new truncation strategy for the higher-order singular value decomposition
- A BLAS-3 Version of the QR Factorization with Column Pivoting
- On the convergence of Stewart's QLP algorithm for approximating the SVD
- Subspace Iteration Randomization and Singular Value Problems
- A DEIM induced CUR factorization
- Randomized QR with column pivoting
- HOID: higher order interpolatory decomposition for tensors based on Tucker representation
- Stewart's pivoted QLP decomposition for low‐rank matrices
Cited In (3)
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)
