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 × 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×n matrix A by reading only a limited number of rows and columns of A. The algorithm has complexity O(k² 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.