Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions

By Ivan V. Oseledets, E. E. Tyrtyshnikov. 2009

528 citations recorded by the source corpus.

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.

Subfields: Biomedical Engineering, Computational Mathematics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mathematics

In Computational Theory and Mathematics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “In the context of numerical analysis, a decomposition of the form (5) was ﬁrst proposed in [212, 213, 217].”
O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling (2011, methodology): “For completeness, in the case p = 1, we define Fq,d,1 as the identity mapping.”
ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS∗ (2014, background): “The same tensor formats were recently re-discovered in the numerical linear algebra (NLA) community as the tensor train (TT) format [9, 8].”
TT-cross approximation for multidimensional arrays (2010, methodology): “Then, as soon as we have tensors in the TT format, we are able to perform many basic operations with these tensors in a very eﬃcient way [31,30,35,36].”
A New Truncation Strategy for the Higher-Order Singular Value Decomposition (2012, background): “Kroonenberg and de Leeuw were the first to propose such an (iterative) algorithm in [30].”
CANDECOMP/PARAFAC Decomposition of High-Order Tensors Through Tensor Reshaping (2012, methodology): “Oseledets an d Tyrtyshnikov [21] approximated the Laplace operator and the general second-order operator which appea rs in the Black-Scholes equation for multiasset modeling to tackle the dimensions up to N = 200.”
QTT approximation of elliptic solution operators in higher dimensions (2011, methodology): “QTT-format was successfully applied to solving quantum molecular dynamics problems [24] and to the solution of high-dimensional stochastic PDEs [25], so they can be considered as computational tools and be ingredients in numerical algorithms for solving practical problems.”
Fast and accurate 3D tensor calculation of the Fock operator in a general basis (2012, background): “The rank-structured tensor formats suitable for problems in higher dimensions include the matrix-product states (MPS) [32] [33], TT format [34] [35] and the quantized-TT (QTT) approximation which is of O(log N) complexity (see also [36]).”
Two-level Tucker-TT-QTT format for optimized tensor calculus (2012, methodology): “reconstructing the TT-SVD algorithm [23, 24] analytically.”
Constructive Representation of Functions in Low-Rank Tensor Formats (2012, methodology): “In 2009, the H -Tucker format [13, 15] and the Tree-Tucker format [30] where introduced.”
An Introduction to Hierarchical (H-) Rank and TT-Rank of Tensors with Examples (2011, methodology): “For a tensor A ∈ R I the MPS format is a representation of the form where 1 If we write all the matrix products explicitly and use the notation then the entries of the tensor are given by which is the form of the TT format, T T (k), deﬁned in [12].”
Low-rank tensor structure of linear diffusion operators in the TT and QTT formats☆ (2013, methodology): “In the present paper we construct explicit low-rank Tensor Train [5, 6] representations of S d .”