PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral tensor-train decomposition

Daniele Bigoni, Allan P. Engsig-Karup, Youssef M. Marzouk

arXiv:1405.5713v4math.NAcs.NA

TL;DR

High-dimensional approximation is challenged by exponential growth in tensor-product coefficients and evaluations. The paper extends tensor trains to continuous functions and approximates regularity-preserving cores with polynomials; for sufficiently regular functions, the resulting representation can combine low-rank structure with spectral convergence.

  • Problem

    Tensor-product approximation becomes impractical as dimension grows because the number of coefficients and required function evaluations increase exponentially.

    Source: §1 · p. 1

  • Method

    The paper constructs a functional TT decomposition whose regularity-preserving cores are polynomially approximated, using TT-DMRG-cross on discretized function samples.

    Source: §1 · pp. 2–3, §6 · p. 28

  • Results

    For functions with sufficient regularity, the spectral TT approximation exploits low tensor rank and can attain spectral convergence rates.

    Source: §6 · p. 28

  • Takeaways & Limitations

    Numerical experiments demonstrate good performance, with computational effort for analytically low-rank functions examined through the function evaluations required for a given accuracy.

    Source: §6 · p. 28

    Dimension ordering can affect the number of function evaluations, and finding an optimal or near-optimal ordering remains ongoing work.

    Source: §6 · p. 28

Abstract

from arXiv · show

The accurate approximation of high-dimensional functions is an essential task in uncertainty quantification and many other fields. We propose a new function approximation scheme based on a spectral extension of the tensor-train (TT) decomposition. We first define a functional version of the TT decomposition and analyze its properties. We obtain results on the convergence of the decomposition, revealing links between the regularity of the function, the dimension of the input space, and the TT ranks. We also show that the regularity of the target function is preserved by the univariate functions (i.e., the "cores") comprising the functional TT decomposition. This result motivates an approximation scheme employing polynomial approximations of the cores. For functions with appropriate regularity, the resulting \textit{spectral tensor-train decomposition} combines the favorable dimension-scaling of the TT decomposition with the spectral convergence rate of polynomial approximations, yielding efficient and accurate surrogates for high-dimensional functions. To construct these decompositions, we use the sampling algorithm \texttt{TT-DMRG-cross} to obtain the TT decomposition of tensors resulting from suitable discretizations of the target function. We assess the performance of the method on a range of numerical examples: a modifed set of Genz functions with dimension up to $100$, and functions with mixed Fourier modes or with local features. We observe significant improvements in performance over an anisotropic adaptive Smolyak approach. The method is also used to approximate the solution of an elliptic PDE with random input data. The open source software and examples presented in this work are available online.

1. Introduction.

High-dimensional function approximation faces exponential growth in tensor-product coefficients and evaluations. This work extends tensor trains to continuous functions, preserving core regularity so polynomial approximation can yield spectral rates while retaining favorable dimension scaling.

1. Introduction.

  • Tensor-product approximation becomes impractical as dimension grows because its coefficient count and evaluation effort increase exponentially.This is the curse of dimensionality the paper seeks to mitigate.Source: §1 · p. 1
  • Earlier TT applications in uncertainty quantification addressed particular computational tasks, whereas this paper targets general non-intrusive function approximation.The cited examples include operator and coefficient compression, iterative PDE solution, recurrence evaluation, and inner-product computation,, [68],.Source: §1 · p. 2
  • The paper defines a functional TT decomposition, relates its convergence to function regularity, dimension, and TT ranks, and shows that its cores preserve regularity.This motivates polynomial approximation of the cores, producing spectral convergence for smooth functions with representation complexity that can scale linearly with dimension.Source: §1 · p. 2
  • For black-box functions, TT-DMRG-cross samples discretized tensors to construct spectral TT approximations, evaluated on Genz functions, Fourier-mode functions, local features, and a stochastic elliptic PDE.The experiments examine polynomial degree, TT ranks, accuracy, and computational effort as dimension changes.Source: §1 · p. 3

2. Tensor decompositions.

The section introduces tensor decompositions and motivates the tensor-train format as a structured alternative for representing high-dimensional tensors. It describes TT approximation and sampling-based cross methods for constructing it.

2.1. Classical tensor decompositions.

  • For tensors beyond matrices, common decomposition formats include canonical, Tucker, and tensor-train forms because the matrix SVD does not directly generalize.The canonical format can lack a best rank-r approximation, while Tucker's core tensor makes its parameter count grow exponentially with dimension.Source: §2 · p. 3, §2.1 · pp. 3–4

2.2. Discrete tensor-train (DTT) decomposition.

  • TT represents a tensor through linked cores; it has a best rank-r approximation, and TT-SVD produces a quasi-optimal approximation.With equal ranks and mode sizes, storage scales linearly with dimension, but TT-SVD's computation and initial full-tensor storage remain dimensionally expensive.Source: §2.2 · pp. 4–5
  • TT-ranks depend on the ordering of tensor indices, since poorly ordered interacting dimensions can carry non-separability across more cores and increase cost.The ordering should keep pairs that yield high-rank unfoldings contiguous.Source: §2.2 · p. 5

2.3. Cross-interpolation of tensors.

  • TT-cross evaluates selected tensor fibers with linear scaling in evaluated entries but requires ranks in advance; TT-DMRG-cross instead determines ranks automatically.TT-DMRG-cross optimizes adjacent pairs of cores and recovers them through an SVD.Source: §2.3 · p. 6

3. Relevant results from approximation theory.

The section reviews polynomial projection and interpolation as approximation tools whose convergence is governed by smoothness. The subsequent approach combines these tools with TT by approximating the decomposition's one-dimensional cores.

3. Relevant results from approximation theory.

  • The paper sets polynomial approximation results in product-measure Sobolev spaces, where smoothness conditions provide the basis for convergence analysis.The reviewed results apply to compact and non-compact supports.Source: §3 · p. 6, §3.1 · p. 6

3.1. Projection.

  • The rate of convergence of the spectral expansion is determined by the smoothness of the function.The discrete projection approximates the orthogonal polynomial projection; a quadrature rule exact through degree 2N avoids potential O(1) internal aliasing errors.Source: §3.1 · p. 7
  • The discrete projection is exact for functions in the degree-N polynomial space when computed with a Gauss rule.The discrete projection uses quadrature points and weights.Source: §3.1 · p. 7

3.2. Interpolation.

  • Lagrange interpolation on tensor grids has convergence governed by function smoothness, and the paper combines interpolation theory with TT through one-dimensional polynomial approximations of FTT cores.The approach relies on the cores inheriting the original function's regularity, making them suitable for spectral approximation.Source: §3.2 · p. 8, §4 · p. 9

4. Spectral tensor-train decomposition.

The functional tensor-train decomposition extends TT to continuous functions by recursively applying Schmidt decompositions to square-integrable kernels. Truncating the resulting expansion gives a functional TT approximation.

4.1. Functional tensor-train decomposition.

  • The functional TT construction applies to a square-integrable function on a product domain with a finite product measure.The construction proceeds by repeatedly decomposing kernels using the Schmidt decomposition.Source: §4 · p. 9, §4.1 · p. 9
  • The recursive construction expresses the function through univariate cores connected by rank indices.Each step decomposes a kernel involving the current variable and the remaining variables.Source: §4.1 · pp. 9–10
  • Truncating the functional TT expansion yields a functional TT approximation, whose residual is the difference between the function and its approximation.The section investigates how convergence relates to regularity of the approximated function.Source: §4.1 · p. 10

4.2. Convergence of the FTT approximation.

The section establishes convergence bounds for the functional TT approximation, connecting approximation error with function regularity, input dimension, and TT ranks. Its proof builds on truncating the decomposition and controlling the resulting residual.

4.2. Convergence of the FTT approximation.

  • Truncating the functional TT decomposition while retaining the largest singular values gives an approximation whose residual is analyzed in the section.The residual bound is built inductively from estimates for successive decomposition steps.Source: §4.2 · pp. 10–11
  • The convergence analysis uses regularity-dependent estimates to connect the approximation error to properties of the target function.The section introduces auxiliary results after noting that the truncation result alone does not involve properties of f.Source: §4.2 · pp. 11–12
  • The main convergence result relates FTT approximation error to function regularity, input dimension, and the retained TT ranks.The analysis considers equal ranks across dimensions.Source: §4.2 · p. 12
  • The section motivates polynomial approximation by seeking conditions under which the FTT decomposition converges absolutely almost everywhere.It identifies integrated Hölder continuity with exponent greater than 1/2 as a sufficient condition for the Schmidt decomposition, then extends the result to FTT.Source: §4.2 · pp. 12–13

4.3. Regularity of the FTT decomposition.

The section shows how regularity of the target function is reflected in the functional TT decomposition. Under stated regularity conditions, the decomposition converges absolutely almost everywhere and its cores retain regularity properties.

4.3. Regularity of the FTT decomposition.

  • Hölder continuity with exponent greater than 1/2 ensures absolute almost-everywhere convergence of the FTT decomposition on the stated domain.Source: §4.3 · p. 13
  • If f belongs to a Sobolev space and is Hölder continuous with exponent greater than 1/2, its FTT cores belong to the same Sobolev space.The result is stated for functions on a closed, bounded domain.Source: §4.3 · pp. 13–15
  • The cited absolute-convergence result is limited to closed, bounded domains; the corresponding result for the real line with a finite measure was not established by the authors.Source: §4.3 · p. 15
  • Continuous target functions yield continuous FTT cores.Source: §4.3 · p. 15
  • Under the stated Lipschitz and differentiability conditions, the FTT cores have the corresponding strong derivatives.The theorem places each core in C^βk(Ik).Source: §4.3 · p. 15

4.4. Connecting the DTT and FTT decompositions.

The section connects the functional TT approximation to a discrete TT decomposition by discretizing function evaluations and using quadrature to approximate the functional norm. The resulting error includes quadrature and tensor-approximation contributions.

4.4. Connecting the DTT and FTT decompositions.

  • A discrete TT decomposition of weighted function samples approximates the functional L2 minimization problem through a finite-order quadrature rule.The construction uses product quadrature nodes and weights; the discussion does not restrict the approach to Gaussian rules.Source: §4.4 · pp. 15–16
  • The approximation error includes quadrature error and aliasing from approximating weighted samples with a discrete TT tensor; both decrease as quadrature orders increase.Source: §4.4 · p. 16
  • Numerical tests support achieving the relative L2 error bound when the quadrature orders are sufficiently large.The recovery of the error-weighted DTT approximation assumes strictly positive quadrature weights.Source: §4.4 · p. 16

4.5. Polynomial approximation of the FTT decomposition.

The section constructs spectral tensor-train approximations by applying polynomial projection or interpolation to functional TT cores. Projection convergence depends on rank, polynomial degree, and function regularity, while interpolation offers local support that limits the spread of singularity errors.

4.5.1. Functional tensor-train projection.

  • Projecting the FTT cores onto univariate basis functions yields a spectral expansion whose coefficient tensor has a TT representation.The projection error combines the FTT truncation error and the polynomial approximation error; convergence improves with increasing regularity and depends on rank and polynomial degree.Source: §4.5.1 · p. 16

4.5.2. Functional tensor-train interpolation.

  • Core-wise interpolation can use linear or higher-order Lagrange bases, and the local support of the basis functions prevents singularity errors from polluting the entire domain.The stated linear-interpolation convergence is quadratic under the section's Sobolev regularity condition.Source: §4.5.2 · p. 18

4.5. Polynomial approximation of the FTT decomposition.

  • Spectral tensor-train approximations combine a truncated FTT representation with polynomial or piecewise-linear approximations of its cores.Source: §4.5.3 · p. 19

4.5.3. Summary of algorithms.

  • The construction selects candidate nodes, applies TT-DMRG-cross to the relevant discretized tensors, and evaluates the approximation using the projection or interpolation procedure.The algorithms also apply TT-DMRG-cross to quantics-folded tensors.Source: §4.5.3 · p. 19

5. Numerical examples.

The numerical examples assess relative L2 error and function-evaluation cost across modified Genz functions, mixed Fourier modes, local features, and a random-input elliptic PDE. Across the modified Genz tests, FTT-projection consistently outperforms anisotropic adaptive Smolyak, with convergence and cost depending on function regularity and TT rank.

5.1. Genz functions and modified Genz functions.

  • Modified Genz tests leave coefficients unnormalized so functions do not become constant as dimension grows; selected tests span dimensions up to 100.The corner peak tests reach d = 15 and product peak tests reach d = 20; the latter limit reflects machine precision.Source: §5.1 · p. 20, §5.1.1 · p. 21

5.1.1. FTT-projection of the modified Genz functions.

  • Smooth modified Genz functions f1–f4 converge spectrally under FTT-projection, while the continuous case converges quadratically and the discontinuous case very slowly.For finite FTT ranks independent of dimension, evaluation counts grow linearly with dimension; the corner peak's dimension-dependent ranks yield superlinear growth.Source: §5.1.1 · p. 21
  • FTT-projection consistently outperformed anisotropic adaptive Smolyak on the mildly anisotropic, truly high-dimensional tests; its algorithmic complexity grows polynomially rather than exponentially with dimension and rank.The authors note that sparse grids could perform better for more anisotropic functions.Source: §5.1.1 · p. 21

5.1.2. FTT-interpolation of the modified Genz functions.

  • Linear FTT-interpolation gives at least second-order convergence for the first four smooth functions and almost first-order convergence for the discontinuous function.Local support prevents the discontinuity from globally corrupting the approximation; Lagrange FTT-interpolation results closely follow FTT-projection.Source: §5.1.2 · p. 24

5.2. FTT-projection and mixed Fourier modes.

  • A single high-degree mixed mode remains rank one with few samples, but separating interacting dimensions raises ranks and evaluation cost without changing accuracy.For non-neighboring interactions, the maximum rank is 11 across intermediate cuts; for neighboring interactions, it is 11 at one cut.Source: §5.2 · p. 25

5.3. Resolution of local features.

  • TT-DMRG-cross adaptively clusters selected nodes around an off-center Gaussian bump in d = 2 and d = 3, achieving relative accuracy ε = 10^-10.The method selects relevant evaluation nodes while exploring the function's structure.Source: Figure 5.5 · p. 26, §5.3 · p. 26

5.4. Elliptic equation with random input data.

  • For the stochastic elliptic PDE example, approximation error improves spectrally until the TT-DMRG-cross tolerance sets a plateau; degrees above one use many orders of magnitude fewer evaluations than full tensor.Choosing ε on the order of the desired error is most efficient; the example retains 95% of field variance with 12 KL terms.Source: §5.4 · p. 27

6. Conclusions.

The paper develops a spectral tensor-train approximation by combining functional TT theory with polynomial approximation of its cores. For sufficiently regular functions, it exploits low tensor rank and spectral convergence; numerical results show favorable dimension scaling for analytically low-rank functions and strong performance against adaptive sparse grids.

6. Conclusions.

  • For functions with sufficient regularity, the spectral tensor-train approximation exploits low tensor rank and can attain spectral convergence rates.The functional TT analysis relates target regularity, input dimension, and tensor ranks; regularity is inherited by the univariate cores, whose truncation and polynomial approximation are covered by error bounds.Source: §6 · p. 28
  • For analytically low-rank functions, computational effort measured by function evaluations scales linearly with dimension, while non-analytically low-rank examples significantly outperform adaptive sparse grids.The numerical construction applies TT-DMRG-cross to weighted pointwise evaluations of the target function; the user selects polynomial degree and relative accuracy.Source: §6 · p. 28
  • The approximation can resolve local features by clustering evaluation points near the feature.The method uses singular functions of the target function rather than prescribing a basis for the separation; polynomial basis choice enters when approximating those singular functions.Source: §6 · p. 28
  • Dimension ordering can affect the number of evaluations, and optimal ordering, fuller adaptivity, and convergence results on unbounded domains remain future work.The paper also identifies relating cross-interpolation error to pointwise approximation of the functional TT cores as an open direction.Source: §6 · p. 28
  • An open-source Python implementation of the approximation algorithm and the paper's numerical examples is available online.The passage gives the TensorToolbox PyPI address.Source: §6 · p. 28

Appendix B. Proofs of auxiliary results for Theorem 4.7.

The appendix begins the auxiliary proofs by invoking the definitions of the Sobolev norm, seminorm, and weak derivative.

Appendix B. Proofs of auxiliary results for Theorem 4.7.

  • The proof uses the definitions of the Sobolev norm, seminorm, and weak derivative.These definitions are the stated starting point for the auxiliary results supporting Theorem 4.7.Source: §B.1 · p. 29

B.1. Proof of Lemma 4.5.

The proof of Lemma 4.5 bounds an expression indexed by multi-indices using Cauchy–Schwarz, then considers the first dimension with the others following similarly.

B.1. Proof of Lemma 4.5.

  • For Lemma 4.5, the proof applies Cauchy–Schwarz to a bound indexed by multi-indices and proves the claim first for one dimension.It sets the remaining dimensions apart as a multi-index and states that the other dimensions follow similarly.Source: §B.1 · p. 29, §B.2 · p. 30

B.2. Proof of Lemma 4.6.

The proof of Lemma 4.6 uses α1=1 and the Hölder continuity of f for α>1/2.

B.2. Proof of Lemma 4.6.

  • The proof assumes α1=1 and uses Hölder continuity of f for α>1/2.Source: §B.2 · p. 30
Loading 1405.5713v4…