Fast Low-Rank Approximation of Matrices via Randomization with Application to Tensor Completion

The approximation of voluminous datasets, which admit a low-rank structure, by ones of considerably lower ranks have recently found many practical applications in science and engineering. Randomized algorithms have emerged as an powerful choice, due to their efficacy and efficiency, particularly in exploiting parallelism in modern architectures. In this paper, we present a fast randomized rank-revealing algorithm tailored for low-rank matrix approximation and decomposition. However, unlike the previous works, which have applied deterministic decompositional algorithms such as the singular value decomposition (SVD), pivoted QR and QLP, we make use of a randomized algorithm to factorize the compressed matrix. We furnish bounds for the rank-revealing property of the proposed algorithm. In addition, we utilize our proposed algorithm to develop an efficient algorithm for the low-rank tensor decomposition, namely the tensor-SVD. We apply our proposed algorithms to various classes of multidimensional synthetic and real-world datasets.