Geodesic
Fast low rank approximations of matrices and tensors
The electronic journal of linear algebra, Tome 22 (2011), pp. 1031-1048.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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 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.
Classification : 15A18, 15A69, 65F15, 93E24
Keywords: singular value decomposition, CU R decomposition, rank k approximation, least squares, Tucker decomposition 
@article{ELA_2011__22__a10,
     author = {Friedland, S. and Mehrmann, V. and Miedlar, A. and Nkengla, M.},
     title = {Fast low rank approximations of matrices and tensors},
     journal = {The electronic journal of linear algebra},
     pages = {1031--1048},
     publisher = {mathdoc},
     volume = {22},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2011__22__a10/}
}
TY  - JOUR
AU  - Friedland, S.
AU  - Mehrmann, V.
AU  - Miedlar, A.
AU  - Nkengla, M.
TI  - Fast low rank approximations of matrices and tensors
JO  - The electronic journal of linear algebra
PY  - 2011
SP  - 1031
EP  - 1048
VL  - 22
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2011__22__a10/
LA  - en
ID  - ELA_2011__22__a10
ER  - 
%0 Journal Article
%A Friedland, S.
%A Mehrmann, V.
%A Miedlar, A.
%A Nkengla, M.
%T Fast low rank approximations of matrices and tensors
%J The electronic journal of linear algebra
%D 2011
%P 1031-1048
%V 22
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2011__22__a10/
%G en
%F ELA_2011__22__a10
Friedland, S.; Mehrmann, V.; Miedlar, A.; Nkengla, M. Fast low rank approximations of matrices and tensors. The electronic journal of linear algebra, Tome 22 (2011), pp. 1031-1048. http://geodesic.mathdoc.fr/item/ELA_2011__22__a10/