FAST LOW RANK APPROXIMATIONS OF MATRICES AND TENSORS

In many applications such as data compression, imaging or genomic data analysis, it is important to approximate a given m x n matrix A by a matrix B of rank at most k which is much smaller than m and n. The best rank k approximation can be determined via the singular value decomposition which, however, has prohibitively high computational complexity and storage requirements for very large m and n. We present an optimal least squares algorithm for computing a rank k approximation to an m x n matrix A by reading only a limited number of rows and columns of A. The algorithm has complexity O(k(2) max(m, n)) and allows to iteratively improve given rank k approximations by reading additional rows and columns of A. We also show how this approach can be extended to tensors and present numerical results.