Breaking the curse of dimensionality, or how to use SVD in many dimensions

I. V. Oseledets, E. E. Tyrtyshnikov

Research output: Contribution to journalArticlepeer-review

280 Citations (Scopus)

Abstract

For d-dimensional tensors with possibly large d > 3, an hierarchical data structure, called the Tree-Tucker format, is presented as an alternative to the canonical decomposition. It has asymptotically the same (and often even smaller) number of representation parameters and viable stability properties. The approach involves a recursive construction described by a tree with the leafs corresponding to the Tucker decompositions of three-dimensional tensors, and is based on a sequence of SVDs for the recursively obtained unfolding matrices and on the auxiliary dimensions added to the initial "spatial" dimensions. It is shown how this format can be applied to the problem of multidimensional convolution. Convincing numerical examples are given.

Original languageEnglish
Pages (from-to)3744-3759
Number of pages16
JournalSIAM Journal on Scientific Computing
Volume31
Issue number5
DOIs
Publication statusPublished - 2009
Externally publishedYes

Keywords

  • Canonical decomposition
  • Curse of dimensionality
  • Tree-Tucker
  • Tucker decomposition

Fingerprint

Dive into the research topics of 'Breaking the curse of dimensionality, or how to use SVD in many dimensions'. Together they form a unique fingerprint.

Cite this