Fast low rank approximations of matrices and tensors

S. Friedland, V. Mehrmann, A. Miedlar, M. Nkengla

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1031-1048
Number of pages18
JournalElectronic Journal of Linear Algebra
Volume22
DOIs
StatePublished - 2011

Keywords

  • CUR decomposition
  • Least squares
  • Rank k approximation
  • Singular value decomposition
  • Tucker decomposition

Fingerprint

Dive into the research topics of 'Fast low rank approximations of matrices and tensors'. Together they form a unique fingerprint.

Cite this