Fast low rank approximations of matrices and tensors

By Shmuel Friedland, Volker Mehrmann, Agnieszka K. Miedlar, M. Nkengla. 2011

38 citations recorded by the source corpus.

In many applications such as data compression, imaging or genomic data analysis, it is important to approximate a given $m\times 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\times n$ matrix $A$ by reading only a limited number of rows and columns of $A$. The algorithm has complexity $\mathcal 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.

Subfields: Computational Mathematics, Computational Mechanics, Computational Theory and Mathematics

Citations in the corpus

• A literature survey of low‐rank tensor approximation techniques (2013, neutral): “These ideas have been extended to low-rank tensor decompositions, for the Tucker decomposition in [70,89,247] and for the TT decomposition in [219].”
• Numerical solution of the Hartree-Fock equation by multilevel tensor-structured methods (2011, unknown): “6.1 Brief summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.2 Presentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140”