• search hit 13 of 24
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.