Compressed Randomized UTV Decompositions for Low-Rank Approximations and Big Data Applications
Provides a faster and more accurate low-rank decomposition method for large dense matrices, benefiting numerical linear algebra and signal processing applications.
The paper introduces Compressed Randomized UTV (CoR-UTV) decomposition for low-rank matrix approximations, achieving O(mnk) complexity and outperforming alternative methods in efficiency and accuracy on synthetic and real data.
Low-rank matrix approximations play a fundamental role in numerical linear algebra and signal processing applications. This paper introduces a novel rank-revealing matrix decomposition algorithm termed Compressed Randomized UTV (CoR-UTV) decomposition along with a CoR-UTV variant aided by the power method technique. CoR-UTV is primarily developed to compute an approximation to a low-rank input matrix by making use of random sampling schemes. Given a large and dense matrix of size $m\times n$ with numerical rank $k$, where $k \ll \text{min} \{m,n\}$, CoR-UTV requires a few passes over the data, and runs in $O(mnk)$ floating-point operations. Furthermore, CoR-UTV can exploit modern computational platforms and, consequently, can be optimized for maximum efficiency. CoR-UTV is simple and accurate, and outperforms reported alternative methods in terms of efficiency and accuracy. Simulations with synthetic data as well as real data in image reconstruction and robust principal component analysis applications support our claims.