Low-rank Matrix Approximation Based on Intermingled Randomized Decomposition

Abstract

This work introduces a novel matrix decomposition method termed Intermingled Randomized Singular Value Decomposition (InR-SVD), along with an InR-SVD variant powered by the power iteration scheme. InR-SVD computes a low-rank approximation to an input matrix by means of random sampling techniques. Given a large and dense m × n matrix, InR-SVD constructs a low-rank approximation with a few passes over the data in O(mnk) floating-point operations, where k is much smaller than m and n. Furthermore, InR-SVD can exploit modern computational platforms and thereby being optimized for maximum efficiency. InR-SVD is applied to synthetic data as well as real data in image reconstruction and robust principal component analysis problems. Simulations show that InR-SVD outperforms existing approaches.