Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation

Abstract

An efficient, accurate and reliable approximation of a matrix by one of lower rank is a fundamental task in numerical linear algebra and signal processing applications. In this paper, we introduce a new matrix decomposition approach termed Subspace-Orbit Randomized singular value decomposition (SOR-SVD), which makes use of random sampling techniques to give an approximation to a low-rank matrix. Given a large and dense data matrix of size $m\times n$ with numerical rank $k$, where $k\ll \text{min}\{m,n\}$, the algorithm requires a few passes through data, and can be computed in $O(mnk)$ floating-point operations. Moreover, the SOR-SVD algorithm can utilize advanced computer architectures, and, as a result, it can be optimized for maximum efficiency. The SOR-SVD algorithm is simple, accurate, and provably correct, and outperforms previously reported techniques in terms of accuracy and efficiency. Our numerical experiments support these claims.

References in corpus (11)

• Quantum state tomography via compressed sensing
• Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
• Rank-Sparsity Incoherence for Matrix Decomposition
• Latent variable graphical model selection via convex optimization
• Robust subspace clustering
• Practical sketching algorithms for low-rank matrix approximation
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• In-network Sparsity-regularized Rank Minimization: Algorithms and Applications
• Online Categorical Subspace Learning for Sketching Big Data with Misses

Cited by in corpus (10)

• Projection-based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matrices
• Knowledge-Aided Normalized Iterative Hard Thresholding Algorithms and Applications to Sparse Reconstruction
• Compressed Sensing with Probability-based Prior Information
• Sparsity-Aware SSAF Algorithm with Individual Weighting Factors for Acoustic Echo Cancellation
• Study of Diffusion Normalized Least Mean M-estimate Algorithms
• Study of Compressed Randomized UTV Decompositions for Low-Rank Matrix Approximations in Data Science
• Study of List-Based OMP and an Enhanced Model for Direction Finding with Non-Uniform Arrays
• Randomized Rank-Revealing UZV Decomposition for Low-Rank Approximation of Matrices
• Single-pass randomized QLP decomposition for low-rank approximation
• Study of Distributed Robust Beamforming with Low-Rank and Cross-Correlation Techniques