Tucker dimensionality reduction of three-dimensional arrays in linear time

I. V. Oseledets, D. V. Savostianov, E. E. Tyrtyshnikov

Research output: Contribution to journalArticlepeer-review

125 Citations (Scopus)

Abstract

We consider Tucker-like approximations with an τ × τ × τ core tensor for three-dimensional n × n × n arrays in the case of r « n and possibly very large n (up to 104-106). As the approximation contains only O(rn + r3) parameters, it is natural to ask if it can be computed using only a small amount of entries of the given array. A similar question for matrices (two-dimensional tensors) was asked and positively answered in [S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudo-skeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1-21]. In the present paper we extend the positive answer to the case of three-dimensional tensors. More specifically, it is shown that if the tensor admits a good Tucker approximation for some (small) rank r, then this approximation can be computed using only O(nr) entries with O(nr3) complexity.

Original languageEnglish
Pages (from-to)939-956
Number of pages18
JournalSIAM Journal on Matrix Analysis and Applications
Volume30
Issue number3
DOIs
Publication statusPublished - 2008
Externally publishedYes

Keywords

  • Data compression
  • Data-sparse methods
  • Dimensionality reduction
  • Large-scale matrices
  • Low-rank approximations
  • Multidimensional arrays
  • Skeleton decompositions
  • Tensor approximations
  • Tucker decomposition

Fingerprint

Dive into the research topics of 'Tucker dimensionality reduction of three-dimensional arrays in linear time'. Together they form a unique fingerprint.

Cite this