TY - JOUR

T1 - Fast low rank approximations of matrices and tensors

AU - Friedland, S.

AU - Mehrmann, V.

AU - Miedlar, A.

AU - Nkengla, M.

PY - 2011

Y1 - 2011

N2 - 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(k2 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.

AB - 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(k2 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.

KW - CUR decomposition

KW - Least squares

KW - Rank k approximation

KW - Singular value decomposition

KW - Tucker decomposition

UR - http://www.scopus.com/inward/record.url?scp=80555145106&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80555145106&partnerID=8YFLogxK

U2 - 10.13001/1081-3810.1489

DO - 10.13001/1081-3810.1489

M3 - Article

AN - SCOPUS:80555145106

VL - 22

SP - 1031

EP - 1048

JO - Electronic Journal of Linear Algebra

JF - Electronic Journal of Linear Algebra

SN - 1081-3810

ER -