Fast low rank approximations of matrices and tensors
Please always quote using this URN:urn:nbn:de:0296-matheon-4652
- 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.
Author: | Shmuel Friedland |
---|---|
URN: | urn:nbn:de:0296-matheon-4652 |
Referee: | Peter Deuflhard |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2008/02/25 |
Release Date: | 2008/02/20 |
Tag: | |
Institute: | Technische Universität Berlin |
MSC-Classification: | 15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY / 15Axx Basic linear algebra / 15A18 Eigenvalues, singular values, and eigenvectors |
15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY / 15Axx Basic linear algebra / 15A69 Multilinear algebra, tensor products | |
62-XX STATISTICS / 62-07 Data analysis | |
65-XX NUMERICAL ANALYSIS / 65Fxx Numerical linear algebra / 65F15 Eigenvalues, eigenvectors | |
Preprint Number: | 456 |