PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-rank methods for high-dimensional approximation and model order reduction

Anthony Nouy

arXiv:1511.01554v1math.NA

TL;DR

High-dimensional tensor problems motivate complexity-reducing approximations because full tensor representations can become impractical. The paper develops low-rank formats and algorithms for approximation, compression, completion, model reduction, and tensor-structured equations, with SVD truncation giving error σr+1 and greedy quasi-optimality remaining unresolved in general.

  • Problem

    Full tensor-product spaces have exponentially growing dimension, motivating low-rank methods for high-dimensional and parameter-dependent problems.

  • Method

    The paper analyzes low-rank approximation and develops greedy correction, greedy subspace, truncation, sampling, and equation-based approaches.

  • Results

    For order-two tensors in the injective norm, the SVD gives ∥u − ur∥∨ = σr+1 for the rank-r truncation.

  • Takeaways & Limitations

    Low-rank tensor formats support complexity reduction for multivariate functions and numerical solution of stochastic or parameter-dependent equations.

  • Takeaways & Limitations

    General greedy constructions usually provide suboptimal rank-r sequences, while proving quasi-optimality for greedy subspace constructions remains open for certain function classes.

Abstract

from arXiv · show

Tensor methods are among the most prominent tools for the numerical solution of high-dimensional problems where functions of multiple variables have to be approximated. These methods exploit the tensor structure of function spaces and apply to many problems in computational science which are formulated in tensor spaces, such as problems arising in stochastic calculus, uncertainty quantification or parametric analyses. Here, we present complexity reduction methods based on low-rank approximation methods. We analyze the problem of best approximation in subsets of low-rank tensors and discuss its connection with the problem of optimal model reduction in low-dimensional reduced spaces. We present different algorithms for computing approximations of a function in low-rank formats. In particular, we present constructive algorithms which are based either on a greedy construction of an approximation (with successive corrections in subsets of low-rank tensors) or on the greedy construction of tensor subspaces (for subspace-based low-rank formats). These algorithms can be applied for tensor compression, tensor completion or for the numerical solution of equations in low-rank tensor formats. A special emphasis is given to the solution of stochastic or parameter-dependent models. Different approaches are presented for the approximation of vector-valued or multivariate functions (identified with tensors), based on samples of the functions (black-box approaches) or on the models equations which are satisfied by the functions.

Introduction

The paper develops low-rank tensor methods for reducing complexity in high-dimensional, parameter-dependent, and stochastic problems. It covers best approximation, tensor formats, constructive algorithms, sampling-based approaches, and tensor-structured equations.

  • Introduction: Low-rank approximations reduce complexity when multivariate functions arise in high-dimensional partial differential, stochastic, or parameter-dependent problems.Such reduced representations are important in parametric analyses and uncertainty quantification.
  • Introduction: The paper introduces low-rank approximation concepts for order-two and higher-order tensors, including best rank-r approximation and subspace-based formats.The order-two discussion emphasizes SVD and Bochner spaces, while the higher-order discussion emphasizes Tucker formats and optimal reduced spaces.
  • Introduction: Constructive algorithms build approximations through successive low-rank corrections or through greedy construction of tensor subspaces.Subspace-based approaches yield adaptive algorithms for projection-based model order reduction.
  • Introduction: Sampling-based methods approximate tensor-valued functions using least-squares or interpolation, with interpolation related to tensor completion.These approaches use function samples rather than only the governing equations.
  • Introduction: Parameter-dependent and stochastic models are formulated as tensor-structured equations using Bochner-space and higher-order Lebesgue-space structures.The paper also presents low-rank methods for solving these equations.

1 Tensor spaces

This section defines tensor spaces, operator tensor spaces, norms, and function-space examples used to represent multivariate and parameter-dependent objects. It also explains finite-dimensional tensor subspaces and their exponential dimension growth.

  • 1.1 Tensor Banach spaces: Tensor Banach spaces are completions of algebraic tensor spaces under a norm, while inner-product norms yield tensor Hilbert spaces.For finite-dimensional factor spaces, the completed tensor space coincides with the normed algebraic tensor space.
  • 1.2 Tensor spaces of operators: Tensor products of linear or continuous operators form algebraic tensor spaces of operators acting across the corresponding factor spaces.The construction specializes to scalar-valued operator factors through algebraic and continuous dual spaces.
  • 1.4 Tensor norms: Injective and projective norms are the weakest and strongest reasonable crossnorms, bounding every reasonable crossnorm between them.These bounds induce inclusions between the corresponding tensor Banach spaces.
  • 1.5.1 Lp spaces with product measure: Product-measure Lp spaces represent multivariate functions on product domains, with tensor products defined through products of component functions.For p = 2, the resulting space is a tensor Hilbert space with the canonical norm.
  • 1.5.2 Bochner spaces: Bochner spaces consist of measurable vector-valued functions and are particularly important for parameter-dependent and stochastic equations.When the value space is Hilbert and p = 2, the Bochner tensor space is a tensor Hilbert space with the canonical norm.
  • 1.6 Approximation in finite-dimensional tensor spaces: Finite-dimensional tensor-product approximation spaces have dimensions growing exponentially with the number of dimensions, motivating low-rank and sparse complexity reduction.Sparse methods reduce index sets, whereas low-rank methods exploit different tensor structures.

2 Low-rank approximation of order-two tensors

The section formulates best low-rank approximation for order-two tensors and connects it to optimal reduced subspaces, with the SVD providing optimal approximations in Hilbert settings.

  • Best rank-r approximation seeks an element of Rr minimizing the norm error to a tensor u.Existence follows under suitable closedness and reflexivity conditions, but uniqueness is not guaranteed because Rr is nonconvex.
  • In Hilbert spaces, best rank-r approximation is equivalent to optimizing over r-dimensional subspaces and projecting u onto the corresponding reduced tensor space.The optimal subspace problem is posed on a Grassmann manifold.
  • With the canonical inner product, the optimal reduced subspace is a dominant eigenspace of Cu = u*∘u.The associated eigenvalues are squared singular values, and the projection has the form idS ⊗ PVr.
  • For the injective norm, the rank-r truncated SVD has error σr+1, while retaining its first r terms gives an optimal approximation in the canonical norm.The injective norm equals the operator norm, whereas the canonical norm is the Hilbert-Schmidt norm.
  • The SVD yields increasing nested sequences of optimal left and right subspaces, uniquely defined when σr > σr+1.The nesting is expressed as Vr ⊂ Vr+1 and Sr ⊂ Sr+1.
  • In Bochner spaces, the p = 2 case gives the truncated SVD, known as the Karhunen-Loève decomposition, while nested optimal spaces for p ≠ 2 remain an open question.The p = 2 setting is especially relevant to parameter-dependent and stochastic problems.

3 Low-rank approximation of higher-order tensors

Higher-order tensors admit several low-rank notions and formats, including canonical, Tucker, tree-based Tucker, and Tensor-Train representations, each with structured parameter counts.

  • Unlike order-two tensors, higher-order tensors have several rank notions, producing different low-rank approximation formats.The section emphasizes subspace-based, or Tucker, formats.
  • Canonical rank is defined through a minimal sum of rank-one terms and yields a parametrization with at most dNr real parameters.Here N is the largest factor-space dimension.
  • The α-rank converts a higher-order tensor into an order-two tensor through matricisation, where it equals the resulting classical matrix rank.Imposing α-rank bounds over collections of dimension subsets defines broader low-rank subsets.
  • Tucker rank is a tuple of mode ranks and characterizes tensors contained in products of mode subspaces with prescribed dimensions.Its parametrization has at most Rd + dNR real parameters.
  • Tree-based Tucker formats assign ranks to vertices of a dimension tree and use transfer tensors to build hierarchical representations.Their parameter count is bounded by dNR + RS + (d − 2)RS+1 under the stated definitions of R, S, and N.
  • Hierarchical Tucker and Tensor-Train formats arise as particular tree-based Tucker constructions associated with binary or degenerate binary dimension trees.Tensor-Train rank is specified by ranks of complementary dimension subsets.

3.2 Best approximations in subspace-based low-rank tensor formats

Best approximation in subspace-based formats is reformulated as optimization over structured subspaces, while nonconvex parametrizations motivate specialized algorithms with limited convergence guarantees.

  • 3.2.1 Tucker format: 3.2.1 Tucker format: Best Tucker approximation minimizes the error over both mode subspaces and a tensor in their product.A solution yields optimal mode subspaces whose dimensions are at most the prescribed ranks.
  • 3.2.1 Tucker format: 3.2.1 Tucker format: Tucker best approximations exist under conditions such as weak closedness with reflexivity or closedness in finite dimensions.These conditions apply, for example, to canonical tensor Hilbert spaces and certain Lp tensor spaces.
  • 3.2.2 Tree-based Tucker format: 3.2.2 Tree-based Tucker format: Best approximation is similarly reformulated through hierarchically structured subspaces assigned to tree vertices.The resulting approximation supplies optimal subspaces with the prescribed hierarchical dimensions.
  • 3.2.2 Tree-based Tucker format: 3.2.2 Tree-based Tucker format: Existence requires technical norm conditions across tree vertices, satisfied for canonical tensor Hilbert spaces and Lp spaces.
  • 3.3 Optimization problems in subsets of low-rank tensors: 3.3 Optimization problems in subsets of low-rank tensors: Nonconvex low-rank formats are parametrized by multilinear maps over vector spaces or manifolds.This converts tensor optimization into parameter optimization using methods such as Newton, steepest descent, and block coordinate descent.
  • 3.3 Optimization problems in subsets of low-rank tensors: 3.3 Optimization problems in subsets of low-rank tensors: Alternating minimization solves successive simpler subproblems in individual parameter blocks.Each subproblem inherits structure from the original functional through linearity in that block.
  • 3.3 Optimization problems in subsets of low-rank tensors: 3.3 Optimization problems in subsets of low-rank tensors: General convergence results guarantee only local convergence or convergence to critical points.

3.4 Higher-order singular value decomposition

Higher-order SVD generalizes matrix SVD by applying truncated SVDs to tensor matricisations, producing nested subspaces and quasi-best approximations in structured formats.

  • HOSVD extends SVD to order d ≥3 by applying matrix SVDs to tensor matricisations.It produces quasi-best, but not necessarily best, approximations in tree-based low-rank formats.
  • The construction is restricted technically when u lies in the topological tensor space but outside the algebraic tensor space.
  • For Tucker approximation, truncated HOSVD constructs mode subspaces from dominant singular spaces of mode unfoldings.The resulting subspaces are nested as the prescribed multilinear ranks increase.
  • The truncated HOSVD converges to u as every mode rank reaches the corresponding tensor rank and provides a quasi-optimal Tucker approximation.
  • For tree-based Tucker formats, truncated HOSVD applies projections associated with tree vertices and yields quasi-optimal approximations.The error bound depends on the tree structure through the stated parameter s.
  • In the Tensor-Train format, truncated HOSVD projects onto optimal subspaces associated with suffix dimension sets rather than singleton vertices.

4 Greedy algorithms for low-rank approximation

The section develops greedy low-rank approximation algorithms that recover decompositions or reduced subspaces while lowering the cost of high-rank approximation. These constructions can be suboptimal, and their convergence and anisotropy limitations remain important considerations.

  • Motivation: Best low-rank approximations can converge well with rank, but computing them becomes drastically more expensive as rank increases.Best approximations also generally cannot be obtained by truncating a tensor decomposition.
  • Greedy constructions: Greedy algorithms construct successive low-rank corrections or nested subspaces to reduce the computational complexity of high-rank approximations.They minimize a distance E(u, w) and can sometimes achieve quasi-optimal convergence, although theoretical justification remains incomplete.
  • Greedy construction of the approximation: Rank-one greedy corrections recover a decomposition whose rank-r approximation is obtained by truncating the resulting series, assuming strong convergence.Except in particular Hilbert-space cases, the resulting rank-r sequence is generally suboptimal relative to best canonical-format approximation.
  • Greedy construction of the approximation: Orthogonal greedy improvement steps often do not significantly improve convergence in practical applications.Unlike the basic construction, orthogonal greedy approximations cannot generally be obtained by truncating a decomposition of the same form.
  • Greedy construction of subspaces: Subspace-based constructions enrich reduced spaces and support adaptive projection-based model order reduction, including higher-order tensor formats.The higher-order extension uses constructive algorithms for subspace-based formats, while isotropic enrichment cannot exploit anisotropic tensor structure.
  • Greedy construction of subspaces: For Tucker-format subspace constructions, good rank convergence is observed, but proving quasi-optimality relative to best rank-r approximation remains open.The open question concerns classes of functions characterized by specific decay of best approximation errors.

5 Low-rank approximation using samples

This section presents sample-based low-rank approximation of vector-valued and multivariate functions using discrete norms, interpolation, least squares, and tensor completion. Sample-based reduced spaces can support approximation across the parameter domain, but stability and sampling requirements remain unresolved.

  • Sample-based approximation: Sample evaluations support low-rank approximation of vector-valued or multivariate functions identified with tensors.The approaches include least-squares and interpolation methods, with interpolation connected to tensor completion.
  • Discrete norms: For i.i.d. samples with equal weights, the discrete Bochner norm estimates the corresponding population norm.The sampled restriction can be identified with a tensor in R^K ⊗ V, allowing discrete best rank-r approximation.
  • Interpolation and completion: Interpolation reconstructs a particular function from sampled low-rank tensor coefficients, using methods suited to structured or unstructured sample sets.Without the interpolation property, a least-squares or other reconstruction is not necessarily a solution of the discrete best-approximation problem.
  • PCA and reduced spaces: For p = 2 and Hilbert-valued functions, the dominant empirical eigenspace estimates the optimal reduced subspace for best rank-r approximation.This is the standard Principal Component Analysis and underlies Galerkin Proper Orthogonal Decomposition for parameter-dependent equations.
  • Greedy sample methods: Greedy approximation on a finite sample set yields nested reduced spaces and coincides with EIM or DEIM for finite parameter sets.The resulting reduced space can be used to compute approximations for all parameter values.
  • Stability limitations: When samples are insufficient for stable parameter estimation, regularization is straightforward but remains heuristic.Open questions concern the required sample count and whether nonrandom sampling strategies can be optimal for a given low-rank format.
  • Interpolation and completion: Tensor completion applies low-rank approximation to a tensor of function evaluations using only a few entries, with adaptive cross methods interpolating selected entries.The entries may be sampled randomly before reconstruction, or selected adaptively by ACA extensions.

6 Tensor-structured parameter-dependent or stochastic equations

The paper formulates linear parameter-dependent and stochastic equations as tensor-structured equations, creating a setting for low-rank numerical methods.

  • Linear parameter-dependent or stochastic equations are formulated as tensor-structured equations.

6.1 A class of linear parameter-dependent equations

The section defines a general class of parameter-dependent variational equations under uniform continuity and weak coercivity assumptions, then relates representative stochastic and space-time problems to tensor-product approximation spaces.

  • Linear parameter-dependent equations: The model seeks a parameter-dependent function u satisfying a variational equation for almost every parameter value.The formulation uses parameter-dependent continuous bilinear forms and linear functionals on Hilbert spaces.
  • Well-posedness assumptions: Uniform continuity and weak coercivity provide parameter-independent conditions under which the associated operator is an isomorphism.The operator formulation is equivalent to the variational problem.
  • Well-posedness assumptions: Under these assumptions, the parameter-dependent problem admits a unique solution with the stated integrability regularity.
  • Stochastic diffusion example: A diffusion problem with a random field coefficient is given as a representative stochastic boundary-value problem.The random field may be represented using truncated Karhunen–Loève decomposition and polynomial chaos expansions.
  • Stochastic diffusion example: For some stochastic problems, the coefficient may not be uniformly bounded, so its lower and upper bounds can depend on the parameter.The paper refers to separate analyses for such cases, including log-normal random fields.
  • Space-time equations: Time-dependent problems admit space-time Galerkin approximations in tensor-product spaces over time and physical domains.Low-rank representations exploit this structure and provide the basis for POD and earlier variational-in-time PGD methods.

6.2 Tensor-structured equations

The section formulates parameter-dependent problems as tensor-structured operator equations, using affine representations to expose separable structure and support low-rank methods.

  • Operator formulation: The bilinear form induces a continuous operator A from V to W′, allowing the variational problem to be rewritten as an operator equation.The relation ⟨Av,w⟩ = a(v,w) defines the operator associated with the bilinear form.
  • Well-posedness: Under the stated assumptions, A is an isomorphism and the resulting problem has the stability properties needed for a well-posed tensor formulation.The assumptions imply continuity, boundedness, and positivity properties for the bilinear form and operator.
  • Affine representations: Parameter-dependent operators and right-hand sides are represented through parameter-independent components weighted by scalar parameter functions.The operator uses an affine representation with operators B_i and functions λ_i; analogous assumptions are made for f.
  • Representation compression: Low-rank approximation can compress non-affine or overly long affine representations into forms with fewer terms.The section identifies SVD and the Empirical Interpolation Method as approaches for constructing such compressed representations.
  • Tensor structure: Tensor-product measures and separable parameter functions place the right-hand side and operator in tensor spaces, yielding tensor-structured equations.Product measures and separated functions provide the functional tensor factors used in the representation.

6.3 Galerkin approximations

Galerkin approximations solve parameter-dependent problems in tensor-product trial and test spaces, with Petrov-Galerkin and minimal-residual formulations providing structured reduced approximations.

  • Approximation spaces: Galerkin methods approximate the solution in a tensor-product subspace equipped with the natural Bochner-space norm.The approximation space has the form S ⊗ V, with finite-dimensional parameter space S.
  • Petrov-Galerkin approximation: The Petrov-Galerkin solution is defined by testing the variational problem in a tensor-product test space and can be rewritten as an operator equation.The operator A is associated with the bilinear form through Equation (6.17).
  • Petrov-Galerkin approximation: The Petrov-Galerkin approximation is unique and quasi-optimal when the trial and test spaces satisfy the required stability properties.Its error is bounded by a quasi-optimality estimate involving the continuity and stability constants.
  • Implementation: In practice, integrals in these formulations can be replaced by suitable quadrature rules, while affine representations preserve tensor-structured equation forms.The same tensor structure is retained when quantities are replaced by their tilded versions under the stated affine assumptions.
  • Minimal-residual approximation: Minimal-residual Galerkin approximation reformulates the problem using the adjoint and a parameter-dependent weighting operator.The resulting operator is ˜B(ξ) = B(ξ)∗C(ξ)B(ξ), and the right-hand side is transformed correspondingly.

6.4 Interpolation (or collocation) method

The interpolation method approximates parameter-dependent solutions from values at selected points and represents the resulting data and operators as tensors.

  • Interpolation construction: Interpolation uses K selected points in the parameter domain together with associated interpolation functions to construct an approximation of the solution.The interpolant is formed from solution values at the interpolation points.
  • Order-two tensor structure: For order-two structure, sampled operators become matrix-valued tensor factors, with diagonal matrices encoding parameter-function values at interpolation points.Under affine assumptions, Λ_i is diagonal with entries λ_i(y_k), and the sampled right-hand side has corresponding vectors γ_i.
  • Higher-order tensor structure: Tensorized interpolation grids produce higher-order tensor representations for sampled solutions, right-hand sides, and operators.Each parameter dimension contributes its own tensor factor and diagonal operator matrix.
  • Relation to Galerkin methods: Interpolation coincides with a pseudo-spectral Galerkin approximation when the Galerkin integrals use quadrature points as integration points.The equivalence holds for the interpolation space generated by the interpolation functions.

6.5 Low-rank structures of the solution of parameter-dependent or stochastic equations

The section examines when parameter-dependent or stochastic solution maps admit accurate low-rank approximations, emphasizing that rigorous predictive results remain limited.

  • A priori understanding: Only a few quantitative results currently answer whether solutions of parameter-dependent or stochastic equations are accurately approximable at low rank.This uncertainty is identified as the first question when applying low-rank tensor methods.
  • Convergence analysis: For p = 2, convergence of best rank-r approximations is connected to singular-value decay, whereas for p = ∞ it is connected to Kolmogorov widths.These relationships provide different routes for analyzing approximation convergence.
  • Limitations of current results: Existing general convergence results often rely on global regularity and do not exploit solution-specific structures such as anisotropy.The combinatorial definition of rank makes convergence analysis difficult, especially when exploiting detailed equation structure.
  • Induced low-rank structure: Operator and right-hand-side parametrizations can induce low-rank solution structure; in the example, rank2(u) equals rank2(f).The equation B(ξ1)u(ξ1,ξ2) = f(ξ2) transfers the relevant rank structure from f to u.
  • Structural sources of low rank: Low effective dimensionality and low-order interactions are specific structures that low-rank methods can capture.A function depending effectively on a subset of variables can have rank one across the corresponding tensor partitions.
  • Open problem: Applications often observe good low-rank approximability, but a rigorous classification by expected approximation accuracy is still needed.The section consequently shifts from general approximability questions toward numerical methods for these equations.

7 Low-rank approximation for equations in tensor format

The section presents low-rank algorithms for tensor-structured operator equations, combining iterative solvers, truncation, residual minimization, and Galerkin strategies. It emphasizes parameter-dependent settings and error control through appropriate norms.

  • 7 Low-rank approximation for equations in tensor format: Low-rank equation solvers either truncate iterates from classical iterative methods or directly minimize a distance to the solution over low-rank formats.The direct approaches use residual-based minimization, optimization on low-rank subsets, or constructive greedy algorithms.
  • 7 Low-rank approximation for equations in tensor format: Tensor equations can be represented over finite-dimensional tensor-product spaces, including order-two or higher-order parameter-dependent formulations.For parameter-dependent equations, the spaces may use approximation, interpolation, or collocation representations.
  • 7.1 Classical iterative methods using low-rank truncations: Low-rank truncations reduce storage and computational complexity during algebraic operations in iterative methods, yielding approximate iterations that can be analyzed as perturbed algorithms.The truncation operator can be defined with a prescribed precision.
  • 7.1 Classical iterative methods using low-rank truncations: Truncation norms should match the desired parameter-dependent error control: the 2-norm supports mean-square control, while the ∞-norm supports uniform control over the discrete parameter set.Under regularity assumptions, controlling the 2-norm may also suffice for the ∞-norm; an (∞,2)-norm directly controls the maximum V-norm over samples.
  • 7.2 Minimization of a residual-based distance to the solution: Residual-based minimization defines a low-rank approximation by minimizing a residual-induced distance, with a preconditioner determining the residual norm.For suitable linear operators, the resulting approximation is quasi-best in the target low-rank subset.
  • 7.2 Minimization of a residual-based distance to the solution: For coercive linear problems, residual-distance minimization is equivalent to minimizing a strongly convex quadratic functional and provides a best approximation in the associated operator norm.In interpolation settings, the relevant function-space norm can coincide with the discrete 2-norm over samples.
  • 7.3 Coupling iterative methods and residual norm minimizations: Iterative low-rank truncation and residual minimization can be combined to construct broader classes of low-rank iterative solvers.Residual methods guarantee convergence of low-rank approximations but may suffer ill-conditioning, high-rank intermediate operations, high computational cost, and nonstandard parameter-dependent subproblems; alternative Galerkin criteria address these issues.
  • 7.4.1 Galerkin orthogonality: Galerkin orthogonality can yield optimal rank-one approximations in the canonical norm by interpreting alternating-direction iterations as a power method for a dominant eigenvector.This connects the algorithm with invariant-subspace problems and generalized singular-value decompositions.
Loading 1511.01554v1…