Subspace-Orbit Randomized Decomposition for Low-Rank Matrix Approximations

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 a low-rank approximation to an input matrix. Given a large and dense data matrix of size $m\times n$, the algorithm requires a few passes through data to compute a rank-$k$ approximation 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.