A literature survey of low-rank tensor approximation techniques

Lars Grasedyck; Daniel Kressner; Christine Tobler

Source-linked AI summary

A literature survey of low-rank tensor approximation techniques

Lars Grasedyck, Daniel Kressner, Christine Tobler

arXiv:1302.7121v1Feb 28, 2013math.NAquant-ph

TL;DR

Large-scale linear and multilinear problems motivate low-rank tensor approximation because tensor storage and computation become infeasible with increasing dimension. This survey reviews developments with emphasis on function-related tensors, including decomposition, truncation, and tensor-network methods. It reports that SVD-based approximations can control function-approximation errors and preserve regularity properties, while iterative computations require truncation to manage rank growth.

Problem
Higher-order tensors suffer from exponentially growing storage requirements, while function-related tensors often arise only implicitly as solutions of algebraic equations.
Method
The survey synthesizes low-rank tensor approximation developments, emphasizing function-related tensors, TT and hierarchical Tucker formats, tensor-network structure, and truncation methods.
Results
SVD-based approximations of function-related tensors can directly control L2-norm errors through truncated singular values and preserve regularity of smooth functions.
Takeaways & Limitations
Low-rank tensor methods provide compressed representations and approximation procedures for function-related tensors, including tensors arising in high-dimensional PDE problems.
Takeaways & Limitations
The survey is biased toward TT and hierarchical Tucker decompositions, and tensor ranks may remain too high when a function varies strongly across its domain.

Abstract

from arXiv · show

During the last years, low-rank tensor approximation has been established as a new tool in scientific computing to address large-scale linear and multilinear algebra problems, which would be intractable by classical techniques. This survey attempts to give a literature overview of current developments in this area, with an emphasis on function-related tensors.

1 Introduction

Low-rank tensor approximation addresses exponentially growing tensor storage and computation, especially for tensors induced by discretized multivariate functions. The survey emphasizes function-related tensors while covering applications across scientific computing.

Scope: The survey focuses on multidimensional arrays and emphasizes tensors induced by discretized multivariate functions rather than observed data.Observed-data tensors are directed to other surveys and books.
Function-related tensors: Function-related tensors commonly arise by sampling multivariate functions on tensor grids, including solutions of high-dimensional PDEs.Each tensor entry stores the function value at a corresponding grid position.
Motivation: Tensor entries grow exponentially with order, making explicit storage infeasible and motivating compressed low-rank decompositions.For n = 2 and d = 50, explicit storage would require 9 petabytes.
Computational challenge: Function-related tensors differ from observed data because they are often available only as solutions of algebraic equations, requiring compatible solvers.Examples include linear systems and eigenvalue problems.
Applications: Low-rank tensor techniques have been applied to integrals, electronic structure, stochastic and parametric PDEs, Green’s functions, and other scientific-computing problems.The listed applications also include Boltzmann, Schrödinger, micromagnetics, finance, homogenization, and machine learning.
Scope: The survey is biased toward TT and hierarchical Tucker decompositions, with less detailed attention to some other developments.The authors nevertheless aim to touch on all important directions in function-related tensors.

2 Low-rank tensor decompositions

Low-rank tensor decompositions compress higher-order tensors, generalizing matrix SVD-based representations while introducing tensor-specific rank, approximation, and storage issues. The section introduces rank-one and CP representations and their limitations.

Overview: For order d = 2, tensor compression schemes reduce to the reduced matrix SVD, but they differ substantially for d ≥3.Higher-order tensors require distinct decomposition formats.
Rank-one tensors: A rank-one tensor is an outer product of d vectors, and a separable function discretization produces such a tensor.Each vector corresponds to the discretization of one univariate factor.
CP decomposition: The CP decomposition represents a tensor as a sum of rank-one tensors.Its storage requirement is (n1 + n2 + · · · + nd)R entries.
CP decomposition: CP tensor rank is the minimum number of rank-one terms, but tensors of rank at most R generally form a non-closed set.Consequently, best low-rank approximation can be ill-posed.
CP decomposition: CP compression is attractive for small R, but robust truncation methods are essential for function-related tensors.Existing truncation algorithms largely adapt optimization methods.
CP decomposition: Nonnegativity and other coefficient constraints can be imposed on CP decompositions, although their detailed treatment lies outside this survey’s scope.Such structure is primarily relevant to data-analysis applications.

2.2 Tucker decomposition

The Tucker decomposition represents a tensor using factor matrices and a core tensor, with HOSVD obtaining factors from matricization SVDs. Its truncation is usually nonoptimal but quasi-optimal, while the core limits scalability with dimension.

Tucker representation: Tucker decomposition uses factor matrices Uµ and a core tensor C to represent a tensor with multilinear ranks rµ.The factor matrices have dimensions nµ×rµ, while C has dimensions r1×···×rd.
Multilinear rank: Tucker decomposition is closely connected to tensor matricizations, whose matrix ranks motivate the multilinear-rank tuple.The set of tensors with bounded multilinear ranks is closed.
HOSVD: HOSVD computes each factor matrix from the kµ dominant left singular vectors of the corresponding matricization.The core is then formed from the factor matrices and the tensor.
Approximation quality: Truncated HOSVD is usually not optimal, unlike matrix SVD truncation, but it satisfies a quasi-optimality condition.This condition is usually sufficient for accurate approximation of a function-related tensor.
Extensions: Several methods have been developed to improve HOSVD approximations, including manifold Newton methods, Jacobi algorithms, Krylov methods, and HOSVD modifications.These alternatives address approximation quality beyond the basic truncation.

2.3 Tensor train decomposition

The tensor train (TT) decomposition avoids exponentially growing Tucker-core storage by representing a tensor as a chain of matrix-valued factors. Its ranks are tied to sequential matricizations, enabling SVD-based quasi-best approximation and specialized truncation algorithms.

2.3 Tensor train decomposition: TT was motivated by the need to avoid the exponentially growing memory requirements of the Tucker core while retaining closedness and SVD-based compression.These properties motivate TT as a candidate for high-order tensor compression.
2.3 Tensor train decomposition: The TT decomposition represents each tensor entry as a product of mode-specific matrices, with boundary ranks r0 = rd = 1.The matrices Gµ(iµ) have dimensions rµ−1 × rµ.
2.3 Tensor train decomposition: The format was introduced in numerical analysis and is also known as a matrix product state representation in quantum physics.Tensor network diagrams visualize the contraction underlying the TT representation, which is therefore also called a linear tensor network.
2.3 Tensor train decomposition: TT ranks are the ranks of matricizations that group the first µ modes against the remaining modes.For each µ, the corresponding matricization has rank at most rµ.
2.3 Tensor train decomposition: SVDs of these matricizations provide a quasi-best TT approximation for a prescribed TT-rank.Practical truncation algorithms avoid explicitly constructing the matricizations and their SVDs.

2.4 Hierarchical Tucker decomposition

The hierarchical Tucker decomposition reduces Tucker complexity by recursively splitting tensor modes according to a binary tree. Nested basis relations enable implicit storage, with quasi-best approximation and truncation procedures linked to matricization SVDs.

Hierarchical Tucker structure: Hierarchical Tucker recursively splits tensor modes into subsets organized as nodes of a binary tree.Each node corresponds to a subset of the tensor modes and is associated with a matricization.
Implicit representation: Nestedness allows the tensor and its basis matrices to be stored implicitly through leaf-node bases and transfer matrices.For nonleaf nodes, transfer matrices connect the bases of the node's disjoint child subsets.
Storage requirements: O(dnr + dr^3) storage results when all mode sizes are n and all HT-ranks are r.This storage count assumes uniform mode sizes and ranks.
Approximation and truncation: For a prescribed HT-rank, quasi-best approximations can be obtained from the SVDs of the tensor matricizations.Algorithms also avoid explicitly computing these SVDs when truncating tensors already represented in HT format.
Approximation and truncation: The set of tensors with fixed HT-rank forms a smooth manifold.This geometric property is also noted for Tucker and TT formats in the survey.

2.5 More general tensor network formats

Tensor-network formats beyond tree structures have been developed to represent interaction topologies that include cycles. PEPS and MERA are prominent cyclic examples arising in strongly correlated quantum spin-system simulations.

General tensor networks: Tensor networks beyond trees are motivated by topologies describing interactions in strongly correlated quantum spin systems.These formats were considered in the context of renormalization group methods.
Cyclic formats: Projected entangled-pair states (PEPS) and multiscale entanglement renormalization ansatz (MERA) are examples of tensor networks containing cycles.This distinguishes them from tree-structured formats such as hierarchical Tucker.

2.6 Hybrid formats

Hybrid formats combine different low-rank representations to broaden the available approximation structures. Examples include Tucker representations with CP-approximated cores and combinations with hierarchical matrices.

Hybrid formats: Different low-rank formats can be combined when useful, creating hybrid tensor representations.The survey presents such combinations as an extension of the formats discussed earlier.
Tucker–CP combinations: One popular hybrid uses the Tucker format together with a CP approximation of the core tensor.The survey cites several works on this Tucker–CP combination and related variants.
Tensor–matrix combinations: Other studies combine low-rank tensor formats with hierarchical matrices.These combinations are investigated in several cited works.

2.7 A priori approximation results

Low-rank approximability of function-related tensors is tied to separable-function approximation, with constructive bounds and error control available for several function classes. However, smoothness alone does not guarantee sufficiently low ranks when function variation is strong.

2.7 A priori approximation results: Function-related tensor rank is closely linked to approximating the underlying multivariate function by sums of separable functions.Exact representation by such sums is exceptional; approximation is therefore generally required.
2.7 A priori approximation results: Functions of sums of variables can be approximated through exponential-sum approximations, numerical quadrature, Taylor expansions, or polynomial interpolation.For f(x1, . . . , xd) = g(x1 + · · · + xd), approximating g by exponentials gives a direct construction.
2.7 A priori approximation results: Strong variation across the domain can prevent sufficiently low ranks even for smooth functions.Subdividing the domain and approximating each subdomain separately can then be advantageous.
2.7 A priori approximation results: SVD-based approximations control the L2-norm error of the underlying function directly through the truncated singular values.For smooth functions, tensor-format best approximations and SVD-based quasi-best approximations can inherit function regularity, with additional control of error smoothness.
2.7 A priori approximation results: For quantum many-body systems, low-rank TT approximability of ground states is closely linked to entropy and entanglement.

2.8 Low-rank decomposition of linear operators

A linear operator can be reshaped into a higher-order tensor by pairing row and column indices. Low-rank decompositions of this operator support efficient matrix-vector products when the input tensor is also low rank.

2.8 Low-rank decomposition of linear operators: Pairing each row and column index transforms a matrix representation of a linear operator into an m1n1 × m2n2 × · · · × mdnd tensor.
2.8 Low-rank decomposition of linear operators: Applying low-rank tensor decompositions to the reshaped operator enables efficient matrix-vector products with low-rank input tensors.This operator representation is used broadly in low-rank tensor decomposition literature.

2.9 Tensorization

Tensorization reshapes vectors and tensor modes into binary dimensions so that low-rank formats can compress high-dimensional objects, especially discretized functions. QTT and related formats have been applied across PDE, eigenvalue, integral, convolution, and transform computations.

2.9 Tensorization: A vector of length 2^d can be rearranged into an order-d tensor with mode sizes 2, and low-rank approximation of that tensor compresses the original vector.
2.9 Tensorization: Tensorization combined with TT is called Quantics-TT or QTT and was introduced as a compression scheme for matrices before broader use.
2.9 Tensorization: QTT is particularly relevant when the vector samples a function at 2^d usually uniformly distributed points, with exact and approximate ranks studied for several function classes.
2.9 Tensorization: Applying quantization to every mode of an order-D tensor with N = 2^d produces an order-d·D binary tensor and mixed low-rank decompositions.
2.9 Tensorization: QTT has been applied to PDEs, eigenvalue problems, boundary integrals, convolution, and the FFT, with representations also discussed for several structured operators.
2.9 Tensorization: Software support includes MATLAB toolboxes for CP, Tucker, TT, QTT, and HT, a Python TT implementation, and C++ or Fortran packages for tensor networks and quantum dynamics.

3 Algorithms

Algorithms for function-related tensors either combine classical iterations with repeated low-rank truncation or formulate constrained low-rank optimization problems. The survey also covers greedy, dynamical, and cross-approximation approaches, emphasizing rank control and efficient tensor operations.

3 Algorithms: Function-related tensors are often implicit solutions of linear systems or eigenvalue problems, motivating iterative truncation and low-rank optimization approaches.
3.1 Iterative methods combined with truncation: Truncated Richardson iteration applies a preconditioned update followed by truncation in a chosen low-rank tensor format.The update uses a preconditioner P and scalar ω, while truncation prevents the iterate from leaving the admissible representation.
3.1 Iterative methods combined with truncation: Low-rank truncation can be combined with projection, Krylov, GMRES, power, Lanczos, Richardson, and conjugate-gradient-type methods across CP, Tucker, TT, HT, QTT, and matrix formats.
3.1 Iterative methods combined with truncation: Rank growth is inevitable during iterative low-rank computation: summing k tensors can multiply ranks by k, while a Hadamard product can square them.Operations should be combined directly with truncation rather than allowing this growth to occur explicitly.
3.1 Iterative methods combined with truncation: Effective preconditioners can limit intermediate rank growth while remaining efficiently applicable to low-rank tensor decompositions.Numerical evidence supports the rank-growth benefit, and low-rank preconditioners include Kronecker, approximate inverse, PDE-coefficient, multilevel, and wavelet constructions.
3.2 Optimization-based algorithms: Constrained optimization fixes a low-rank admissible set for linear-system or eigenvalue objectives, but the resulting problem is generally highly nonlinear and non-convex.Examples include residual minimization, Rayleigh-quotient minimization, trace minimization, ALS, DMRG, and Riemannian methods.
3.3 Successive low-rank approximation: Greedy methods build an approximation through successive rank-1 corrections and target a reasonable approximation after a moderate number of steps rather than the best rank-R approximation.The correction is determined through a nonlinear optimization problem and iterations continue until the residual is sufficiently small.
3.4 Dynamical low-rank approximation: Dynamical low-rank methods restrict time-dependent dynamics to the tangent space of a low-rank tensor manifold and require efficient, robust numerical integration.They have been extended to Tucker, TT/MPS, and HT formats.