PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation of high-dimensional parametric PDEs

Albert Cohen, Ronald Devore

arXiv:1502.06797v2math.APmath.NA

TL;DR

High-dimensional and infinite-dimensional parameter spaces make parametric PDE solution maps difficult to approximate numerically. The paper analyzes holomorphic, anisotropic structure and develops sparse polynomial and low-dimensional-space algorithms, showing that n-width decay is almost preserved under holomorphic maps, with a loss of 1 in the rate.

  • Problem

    High-dimensional parameter spaces make numerical approximation of the nonlinear solution map for parametric PDEs challenging.

  • Method

    The paper combines holomorphic-map and n-width analysis with sparse interpolation, polynomial expansions, proper orthogonal decomposition, and reduced basis methods.

  • Results

    The n-width decay rate is almost preserved under holomorphic maps, up to a loss of 1 in the rate.

  • Takeaways & Limitations

    Holomorphic structure provides a theoretical basis for transferring approximation properties of parameter sets to their solution manifolds.

  • Takeaways & Limitations

    Convergence of the adaptive interpolation algorithm is not guaranteed without additional assumptions on the solution map.

Abstract

from arXiv · show

Parametrized families of PDEs arise in various contexts such as inverse problems, control and optimization, risk assessment, and uncertainty quantification. In most of these applications, the number of parameters is large or perhaps even infinite. Thus, the development of numerical methods for these parametric problems is faced with the possible curse of dimensionality. This article is directed at (i) identifying and understanding which properties of parametric equations allow one to avoid this curse and (ii) developing and analyzing effective numerical methodd which fully exploit these properties and, in turn, are immune to the growth in dimensionality. The first part of this article studies the smoothness and approximability of the solution map, that is, the map $a\mapsto u(a)$ where $a$ is the parameter value and $u(a)$ is the corresponding solution to the PDE. It is shown that for many relevant parametric PDEs, the parametric smoothness of this map is typically holomorphic and also highly anisotropic in that the relevant parameters are of widely varying importance in describing the solution. These two properties are then exploited to establish convergence rates of $n$-term approximations to the solution map for which each term is separable in the parametric and physical variables. These results reveal that, at least on a theoretical level, the solution map can be well approximated by discretizations of moderate complexity, thereby showing how the curse of dimensionality is broken. This theoretical analysis is carried out through concepts of approximation theory such as best $n$-term approximation, sparsity, and $n$-widths. These notions determine a priori the best possible performance of numerical methods and thus serve as a benchmark for concrete algorithms. The second part of this article turns to the development of numerical algorithms based on the theoretically established sparse separable approximations. The numerical methods studied fall into two general categories. The first uses polynomial expansions in terms of the parameters to approximate the solution map. The second one searches for suitable low dimensional spaces for simultaneously approximating all members of the parametric family. The numerical implementation of these approaches is carried out through adaptive and greedy algorithms. An a priori analysis of the performance of these algorithms establishes how well they meet the theoretical benchmarks.

1 Overview

The paper develops theory and algorithms for approximating high- or infinite-dimensional parametric PDE solution maps without succumbing to dimensionality growth. It exploits holomorphy, anisotropy, sparsity, and reduced spaces to establish approximation guarantees and computational strategies.

  • Motivation: Reduced modeling seeks to reduce the computations required to evaluate many approximate PDE solutions across parameter instances.The paper studies which reduced-modeling strategies are effective when the parameter dimension is large or infinite.
  • Solution-map properties: Holomorphy of the solution map is established for linear and certain nonlinear parametric PDEs using LBB theory and the complex Banach-space implicit function theorem.The first approach covers several linear PDE classes, while the second also applies to certain nonlinear equations.
  • Solution-map properties: Affine parameter representations reveal anisotropy because parameters associated with smaller representer norms have reduced effects on the solution.This anisotropy supports holomorphic extensions to tensor-product complex domains used in approximation analysis.
  • Approximation theory: Holomorphy and anisotropy yield coefficient bounds, ℓp summability, and algebraic n^-s convergence for sparse or best n-term separable expansions.Retaining the largest coefficients makes the truncation nonlinear and links the rate exponent to coefficient summability.
  • Approximation theory: For relevant parametric PDEs, algebraic convergence despite infinitely many parameters shows that the curse of dimensionality can be avoided.Fast decay is attributed to smoothness and anisotropy in the parameter variable rather than physical-variable smoothness of individual solutions.
  • Numerical algorithms: The paper analyzes polynomial interpolation and low-dimensional reduced-space algorithms, including adaptive, greedy, proper orthogonal decomposition, and reduced basis approaches.Holomorphic-map results show n-width decay is almost preserved, with a loss of 1 in the convergence rate; algorithmic spaces can have larger errors but comparable decay rates.

2 Holomorphic extensions

Under suitable assumptions, parametric PDE solution maps extend holomorphically to complex domains, often with uniform bounds on neighborhoods of compact parameter sets. These extensions provide the analytic foundation for approximation methods that avoid dimensionality-driven degradation.

  • General framework: Complex Lax–Milgram theory provides existence, uniqueness, invertibility, and a priori bounds for the variational problems under an inf-sup condition.For each right-hand side, the solution is obtained through the bounded inverse operator.
  • General framework: Holomorphy is established by combining holomorphic parameter dependence of the operator and forcing with invertibility of the operator.The resulting solution map is holomorphic over the parameter domain.
  • Linear PDEs: For elliptic and parabolic problems, uniform ellipticity yields solution maps defined and uniformly bounded on complex domains, with holomorphy following from affine parameter dependence.The domain is formed as D := ∪r>0 Dr.
  • Nonlinear and generalized problems: For nonlinear problems and parametrized-domain problems, holomorphic extensions still exist on open neighborhoods of compact real parameter sets, although extensions may be shorter in imaginary directions.These neighborhoods support bounded holomorphic extensions even when full polydisc extensions are unavailable.
  • Approximation implications: The solution map’s holomorphy on a neighborhood of the compact parameter domain is sufficient for approximation results immune to the curse of dimensionality.Affine representations additionally expose anisotropy through parameter-dependent extension radii.
  • Scope boundary: For parametrized-domain and nonlinear problems, uniform ellipticity ensures well-definedness but not holomorphic extensions on the full polydiscs used for elliptic and parabolic problems.The available complex domains can instead have shorter extensions along imaginary axes.

3 Best n-term polynomial approximations

Polynomial expansions provide separable approximations of parametric solution maps, with best n-term selection governed by coefficient sizes and summability. Under suitable ℓp or weak-ℓp conditions, retaining the largest coefficients yields algebraic convergence rates.

  • Approximation framework: Polynomial approximations are formed by truncating infinite separable expansions in the parameter variables, with n measuring the truncation complexity.The framework includes expansions whose terms separate parametric functions from physical-space coefficients.
  • Convergence: Orthonormal expansions converge unconditionally in L2, while ℓ1-summable coefficient norms additionally yield unconditional convergence and uniform L∞ control.The L∞ conclusion holds for normalized basis functions under the stated assumptions.
  • Best n-term selection: For L2 error with an orthonormal basis, the optimal n-term set contains indices of the n largest coefficient norms.For L∞ error with normalized basis functions, the same choice minimizes the available ℓ1-tail bound.
  • Rates: For L∞ error, ℓp summability with p < 1 gives algebraic rate n^−s with s = 1/p − 1.This rate concerns the ℓ1 tail of coefficient norms.
  • Rates: Weak-ℓp properties also characterize the n-term ℓq-tail decay rate for 0 < p < q ≤ ∞.Thus exact rate characterization can use weaker summability than ordinary ℓp membership.

3.2 Convergence of n-term truncated polynomial expansions

The section analyzes Taylor and Legendre polynomial expansions of the solution map and identifies conditions for their convergence and sparse truncation. Under ℓp summability of affine-parametrization norms, best n-term approximations achieve algebraic convergence rates that can avoid dimensionality dependence.

  • Polynomial expansions: The polynomial expansions considered are Taylor, Legendre, and renormalized Legendre series indexed by finitely supported multi-indices.The three series use different polynomial bases or normalizations for the parameter variables.
  • Convergence: Taylor expansions converge conditionally in L∞(U, V ) when the solution map satisfies the holomorphy assumptions of Theorem 2.8.The proof uses finite-dimensional truncations and an exhausting sequence of index sets.
  • Summability: If (∥ψj∥X)j≥1 belongs to ℓp(N) for p < 1, Taylor coefficient norms belong to ℓp(F), and Legendre coefficient norms do likewise under Theorem 2.9.For Taylor coefficients this yields the same p; for Legendre expansions it applies to both vν and wν.
  • Error bounds: Under these summability conditions, Taylor and Legendre series converge unconditionally in the stated L∞ and L2 spaces, with n-term error bounds obtained from coefficient tails.Taylor results use the n largest ∥tν∥V; Legendre results use the n largest ∥vν∥V or ∥wν∥V, depending on the norm.
  • Breaking dimensionality: Although the solution map may have infinitely many variables, best n-term polynomial approximations can converge at an algebraic rate n−s, with s potentially larger for smaller p.The argument relies on holomorphic extension, anisotropy, and best n-term polynomial approximation.
  • Scope: The same summability and convergence results extend to general maps u from A to V, not only solution maps of parametric PDEs.This follows because the cited holomorphy theorems hold in a more general framework.

3.3 Estimates of Taylor coefficients

Taylor coefficient estimates are derived from holomorphic extensions of the solution map to complex polydiscs. Cauchy’s formula yields bounds for each coefficient, while optimizing the extension radii leads to a combinatorial problem that motivates explicit suboptimal choices.

  • Coefficient estimates: Cauchy’s integral formula applied across parameter variables provides upper estimates for Taylor coefficients from bounded holomorphic extensions.The extension is taken over polydiscs whose radii satisfy a prescribed constraint.
  • Finite-dimensional reduction: Finite-dimensional truncation w(z1, . . . , zJ) = u(TJz) reduces the analysis to a holomorphic function of finitely many variables.Its Taylor coefficients correspond to multi-indices supported on the first J parameters.
  • Radius optimization: For a fixed coefficient index ν, the sharpest bound is obtained by minimizing the radius-dependent estimate over admissible sequences ρ.Only coordinates in supp(ν) affect the objective, reducing the optimization to finitely many active variables.
  • Radius optimization: The optimal active set E is characterized through a constrained finite-dimensional minimization over subsets of supp(ν).The minimizing set must satisfy the associated radius conditions, making the characterization combinatorial.
  • Practical bounds: Because the exact combinatorial optimization is difficult except for multi-indices with small support, the analysis uses explicit suboptimal radius choices instead.These choices are introduced later to obtain usable bounds on ∥tν∥V.

3.4 Refined estimates for elliptic and parabolic PDEs

For elliptic and parabolic PDEs, the general Taylor-coefficient radius optimization can simplify under special affine decompositions. Disjoint supports yield a separable optimization, while constant-modulus functions lead to a different explicit minimizer and a tunable bound.

  • Refined estimates: For elliptic and parabolic problems, the general coefficient estimate can be refined using the structure of the affine representation.The refinement is based on the corresponding uniform ellipticity constraints.
  • Disjoint supports: When the functions ψj have disjoint supports, the uniform ellipticity constraint decouples and the radius minimization becomes explicitly solvable.This setting is also called the model of disjoint inclusions.
  • Disjoint supports: In the disjoint-support case, the optimal radius sequence does not depend on ν, producing an explicit coefficient estimate.The simplification follows from the decoupled minimization problem.
  • Parameter choice: Choosing a smaller parameter t can improve the coefficient bound, but the associated constant Ct tends to +∞ as t → 0.The analysis does not pursue optimization of t.
  • Constant moduli: For constant-modulus functions such as complex exponentials, uniform ellipticity has an explicit condition and the radius minimization again admits a ν-dependent solution.The resulting minimizer leads to another coefficient estimate.

3.5 Estimates of Legendre coefficients

Legendre coefficient estimates follow from holomorphic extensions to polyellipses and a multivariate Cauchy argument. Compared with Taylor bounds they include extra factors, but they require weaker holomorphy assumptions and retain the same ℓp summability behavior.

  • Polyellipse estimates: Legendre coefficients vν and wν are estimated by applying Cauchy’s formula on polyellipses to the parameter variables active in ν.The variables are partitioned into active coordinates and a remaining infinite-dimensional tail.
  • Polyellipse estimates: The polyellipse construction converts a uniform holomorphic bound for u into integral estimates for the Legendre coefficients.The bound holds uniformly over the ellipse variables and the inactive parameter tail.
  • Comparison with Taylor estimates: Legendre estimates are more pessimistic than Taylor estimates because they contain additional factors θ(ρj) and (1+2νj).These factors are associated with the Legendre basis estimates.
  • Summability: The additional Legendre factors are absorbed by decay in ρj^−νj and do not affect the ℓp summability properties of the estimates.This preserves the summability conclusions needed for sparse approximation.
  • Assumptions: Legendre coefficient estimates require weaker conditions than Taylor estimates because Theorem 2.9 only requires holomorphy near the parameter image.The cited text notes problems satisfying Theorem 2.9 but not Theorem 2.8.
  • Optimization: The resulting coefficient bounds can be optimized over admissible radius sequences, with only coordinates in supp(ν) affecting the infima.Coordinates outside the support may be set to 1.

3.6 Summability of multi-indexed sequences

This section establishes ℓp summability criteria for multi-indexed sequences arising in parametric PDE coefficient estimates. It also shows that weak ℓp summability can fail even when ordinary ℓp conditions appear plausible.

  • Summability framework: Theorem 3.9 is proved using ℓp summability results for multi-indexed sequences associated with Taylor and Legendre coefficient estimates.The argument reduces coefficient bounds to general sequence forms and applies the auxiliary lemmas developed in this section.
  • Product sequences: For sequences formed from products of a positive sequence b, membership in ℓp(F) is equivalent to b ∈ℓp(N) and ∥b∥ℓ∞< 1.This criterion holds for every 0 < p < ∞.
  • Weak summability: Weak ℓp summability does not generally replace ℓp summability in the multi-indexed construction.A prototype weak-ℓp sequence leads, through multiplicative-partition counting, to a contradiction with the required bound.
  • Algebraic factors: Additional algebraic factors preserve ℓp summability under the same condition b ∈ℓp(N) and ∥b∥ℓ∞< 1.Lemma 3.19 extends the product-sequence criterion to factors depending on multi-index size and component values.
  • Multinomial weights: For 0 < p < 1, multinomially weighted sequences belong to ℓp(F) if and only if b ∈ℓp(N) and ∥b∥ℓ1 < 1.The ℓ1 condition is stricter because the multinomial factor can substantially increase sequence terms.

3.7 Proof of Theorem 3.9

The proof of Theorem 3.9 constructs admissible parameter sequences separately for finite and infinite index blocks, then applies the summability lemmas to the resulting coefficient bounds. It establishes ℓp summability but leaves a quantitative norm bound unresolved.

  • Proof strategy: The proof targets ℓp summability of the coefficient norms ∥tν∥V, ∥vν∥V, and ∥wν∥V using estimates of the general form Cr(ν, ρ).For each multi-index, the sequence ρ is selected to satisfy the constraint associated with the coefficient estimates.
  • Block decomposition: The index set is split into finite and infinite blocks, E = {1, …, J} and F = {J + 1, J + 2, …}, to control the two parts separately.The proof chooses J sufficiently large and defines corresponding restrictions of each multi-index.
  • Infinite-block estimate: The infinite-block contribution is finite after introducing a sequence d containing the factorial factor and applying Lemma 3.21.The assumption b ∈ℓp(N) implies d ∈ℓp(N), which supplies the required summability.
  • Limitation: The proof establishes ℓp summability of the three coefficient sequences but does not provide a simple bound in terms of ∥ψj∥X's ℓp norm.This is identified as a defect of the proof in Remark 3.22.

3.8 Approximation using downward closed sets

The section shows that polynomial approximations can retain their convergence rates when index sets are required to be downward closed. Monotone majorants provide the key bridge from unrestricted best n-term selection to structured sets.

  • Approximation rates: Corollaries 3.10 and 3.11 establish algebraic convergence rates n−s for Taylor and Legendre polynomial approximations.For L2(U, V, µ), the rate uses s = 1/p − 1/2.
  • Downward closed sets: A downward closed set contains every multi-index below each of its members in the componentwise partial ordering.This structure is natural for polynomial spaces and supports tensorized polynomial representations.
  • Structured selection: If a coefficient sequence is monotone non-increasing, indices of its n largest terms can be chosen as nested downward closed sets.This observation motivates replacing arbitrary coefficient sequences by monotone majorants.
  • Algorithmic implication: Corollary 3.26 preserves the convergence rates using downward closed sets selected from monotone majorants rather than directly from the largest coefficients.This supplies the structured index sets needed by later numerical algorithms.

3.9 Exponential approximation rates

In finite-dimensional parameter spaces, the paper derives exponential approximation rates by selecting polynomial indices inside weighted simplices. The rate deteriorates with dimension, while the infinite-dimensional analysis retains algebraic rates under uniform sparsity assumptions.

  • Finite-dimensional setting: Finite-dimensional parameter dependence permits estimates with a fixed vector ρ whose coordinates are strictly larger than 1.The solution map is approximated by truncating Taylor or Legendre series in the finite parameter domain U = [−1, 1]^d.
  • Index selection: Thresholding the values ρ−ν selects indices corresponding to the largest estimated coefficients, and the resulting sets are downward closed.These sets can be represented as integer lattice points inside weighted simplices.
  • Exponential rates: The resulting finite-dimensional polynomial approximations achieve an exponential convergence rate for all n, up to multiplicative constants depending on d and the weights.The proof first establishes the rate for cardinalities growing like k^d and extends it to every n.
  • Dimension dependence: The exponential rate deteriorates as d grows because of the power 1/d and the dimension dependence hidden in the constants.When the ℓp norm of the affine-representer norms remains uniformly bounded as d increases, the infinite-dimensional analysis still gives an algebraic rate n−s.
  • Legendre series: Legendre approximations exhibit the same exponential rates under the corresponding assumptions, after accounting for their additional algebraic coefficient factors.The relevant factors are θ(νj) and (1 + 2νj).

4 Estimating the n-widths of solution manifolds

The section bounds the n-widths of solution manifolds by exploiting holomorphy, affine parameter representations, and approximation properties of the parameter set. It also shows that holomorphic solution maps nearly preserve n-width decay, while special structures can make polynomial truncations sub-optimal.

  • Polynomial approximations: Polynomial approximations of the solution map induce upper bounds for the Kolmogorov n-width of the solution manifold.The approximation space is formed from the physical coefficients associated with selected polynomial indices.
  • Polynomial approximations: Under a suitable affine representation and bounded holomorphic extension, truncated polynomial expansions yield explicit n-width decay estimates.The result requires Assumption A and a holomorphic extension over an open set containing the parameter image.
  • Local approximations: When Assumption A fails, local polynomial approximations replace the global construction by covering the compact parameter set with finitely many admissible subsets.The covering lemma controls complex neighborhoods and ensures the resulting compact subsets lie inside the holomorphy domain.
  • Widths under holomorphic maps: A compact parameter set can be embedded in an affine representer whose coefficient norms inherit the decay rate of the set’s n-widths.The construction uses the Auerbach lemma and normalized primal-dual bases.
  • Widths under holomorphic maps: If the parameter-set n-width decays as n^-s, the solution-manifold n-width nearly preserves this rate under a holomorphic map, with a loss of 1 in the exponent.Holomorphic maps therefore behave almost as well as linear maps for this approximation measure.
  • Faster low-rank approximations: In certain structured examples, n-width spaces outperform best n-term polynomial truncations because disjoint-support affine functions enable rank reduction.For overlapping supports, numerical rates can instead approach the optimal rates for general separable approximations.

5 Towards concrete algorithms

The section converts theoretical separable-approximation results into affordable algorithms using polynomial expansions and reduced spaces. It addresses spatial discretization, computational cost, index-set selection, interpolation, recursive Taylor computation, and greedy reduced bases.

  • Algorithmic motivation: The theoretical separable approximations cannot be implemented directly because coefficients have limited spatial precision and infinitely many multi-indices cannot be exhaustively searched.These limitations motivate computable numerical procedures.
  • Algorithmic motivation: Concrete methods compute separable approximations at affordable cost while targeting the convergence benchmarks established by the theoretical analysis.The desired error bounds include a term accounting for spatial discretization.
  • Space discretization: Spatial discretization computes every coefficient in a common finite element space Vh, producing an error bound ε(h) proportional to h^(r−1) under stated regularity assumptions.The common-space choice is simple but does not optimize degrees of freedom coefficient by coefficient.
  • Polynomial methods: The first algorithmic class constructs computable polynomial approximations, with index sets selected and coefficients computed through non-intrusive or intrusive strategies.Interpolation uses selected parameter points, whereas recursive Taylor computation exploits linearity in the parameter and solution.
  • Computational cost: Identifying a downward-closed index set requires at most n^2/2 evaluations and has cost of order n^2 log(n), generally below polynomial construction cost nNh when Nh ≫ n.The bound follows from the anchored structure of the index sets.
  • Reduced basis methods: The reduced basis method builds an n-dimensional space from selected solution instances, and a greedy strategy achieves convergence rates similar to the n-width benchmark.The selection is made from a large candidate set and is critical to the method’s success.

6 Sparse polynomial interpolation

The section develops interpolation of parametric PDE solution maps using unisolvent grids and downward closed multi-index sets. Under holomorphy and coefficient sparsity assumptions, suitable nested interpolation schemes achieve convergence rates without dimensional deterioration, including for infinitely many variables.

  • Interpolation framework: A discrete parameter set is unisolvent for PΛ when arbitrary prescribed values determine a unique polynomial interpolant.The interpolation operator is expressed in Lagrange form using basis functions associated with the interpolation points.
  • Interpolation framework: Interpolation constructs a polynomial approximation IΛu in the space VΛ from exactly or approximately computed solution instances at selected parameter points.The process is non-intrusive and applies interpolation to V-valued solution maps.
  • Downward closed sets: For finite downward closed Λ, the grid ΓΛ is unisolvent for PΛ and its operator IΛ is the interpolation operator onto PΛ.For general Λ, the same grid need not be unisolvent, so downward closedness is the key structural condition.
  • Adaptive selection: Adaptive selection can fail when an interpolation detail vanishes, potentially preventing all higher indices from being selected.Alternating the error-based rule with a rule that eventually selects every admissible index is proposed to avoid this example-specific pathology.
  • Convergence analysis: For parametric PDEs with ℓp-summable representer norms, weighted Legendre coefficients satisfy ℓp summability, yielding interpolation rates without deterioration relative to Legendre approximation.The result provides nested downward closed sets of cardinality n under suitable univariate point-sequence conditions.
  • Convergence analysis: The resulting interpolation algorithm has an accuracy–complexity trade-off that remains immune to the curse of dimensionality, even with infinitely many variables.The cost estimates distinguish offline and online work and include the numerical solver accuracy ε(h).

7 Taylor approximation

Taylor expansions provide sparse approximations of parametric PDE solution maps, and adaptive algorithms can achieve benchmark convergence rates under stated assumptions. The approach is theoretically effective for infinitely many parameters, with implementation and cost depending on the specific algorithm and discretization.

  • Taylor approximations: Best n-term truncations of Taylor series provide effective polynomial approximations to the solution map for relevant parametric PDEs.These approximations exploit the established properties of the solution map.
  • Taylor approximations: The Taylor-coefficient strategy is intrusive and applies to a limited but relevant range of parametric problems.It computes coefficients by exploiting the specific structure of the parametric PDE.
  • Adaptive algorithms: Adaptive coefficient selection can generate downward closed sets whose truncated Taylor series converges at rate n^-s when coefficient norms belong to ℓp for p < 1.The convergence is stated in L∞(U, V), with s defined from the relevant sparsity assumptions.
  • Adaptive algorithms: For elliptic problems, a specific adaptive procedure matches the algebraic convergence rate obtained by retaining the largest n Taylor terms.The procedure uses the margin of a finite downward closed set to guide selection.
  • Convergence guarantees: The adaptive algorithms are designed to meet best n-term benchmark rates under conditional convergence and saturation assumptions.The results include uniform convergence estimates and apply to both standard and ε-accuracy bulk-chasing variants.
  • Complexity: Both Taylor algorithms are described as immune to the curse of dimensionality, even with infinitely many variables.The claimed immunity follows from the stated accuracy-complexity trade-offs for the algorithms.

8 Reduced basis methods

Reduced basis methods approximate the solution manifold with low-dimensional spaces generated from selected snapshots. Greedy analyses show that these spaces can inherit n-width convergence rates, though discretization and high-dimensional search create practical costs and limitations.

  • Reduced basis methods: Reduced basis methods approximate the solution manifold using a small space V_n spanned by snapshots u(a_1), …, u(a_n).The ideal optimal space is generally computationally inaccessible, so snapshots provide a practical alternative.
  • Greedy selection algorithms: Greedy approximation errors are monotone non-increasing, but the selected snapshots and resulting error sequence need not be unique.The notation allows any sequence produced by a weak greedy implementation with fixed γ.
  • Hilbert-space convergence: Polynomial decay of the Kolmogorov widths d_n implies the same algebraic decay rate for weak greedy errors σ_n in Hilbert spaces.The comparison is established through the stated corollary for any s > 0 under d_n(K)_V ≤ C_0(max{1,n})^-s.
  • Banach-space convergence: In Banach spaces, weak greedy algorithms generally incur a loss of 1/2 in the algebraic decay rate relative to n-widths, and this loss cannot generally be avoided.The paper states that the example establishes the general unavoidability of this loss, while noting a small gap between the corollary and the example.
  • Computational cost: Reduced basis methods can achieve n-width decay rates and prescribed accuracy with fewer basis elements than polynomial expansions, but their offline cost can be very high in high parametric dimension.The offline burden is attributed in particular to a brute-force discrete search over the parameter set.
Loading 1502.06797v2…