Subspace-Orbit Randomized - Based Decomposition for Low-Rank Matrix Approximations

In this paper we introduce a novel matrix decomposition algorithm termed Subspace-Orbit Randomized Singular Value Decomposition (SOR-SVD). It is computed by using random sampling techniques to give a low-rank approximation to an input matrix. Given a large and dense data matrix of size m x n, SOR-SVD requires a few passes through data to compute a rank-k approximation in O (mnk) floating-point operations. Furthermore, SOR-SVD 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.