PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperbolic Cross Approximation

Dinh Dũng, Vladimir N. Temlyakov, Tino Ullrich

arXiv:1601.03978v3math.NA

TL;DR

High-dimensional multivariate approximation needs methods that capture mixed smoothness, but both analysis and practical algorithm construction remain difficult and many fundamental problems are open. This survey synthesizes hyperbolic cross approximation and related sparse-grid methods, emphasizing their ideas, methods, applications, and connections to probability, discrepancy, and numerical integration. It reports optimal-order cubature and approximation results alongside unresolved questions, including nonconstructive aspects and high-dimensional limitations.

  • Problem

    The survey addresses the need for multivariate approximation methods for high-dimensional problems while many fundamental theoretical and algorithmic questions remain unsolved.

  • Method

    The paper surveys hyperbolic cross approximation, mixed-smoothness function classes, sparse grids, widths, nonlinear approximation, and related numerical methods, emphasizing ideas and methods over a complete results list.

  • Results

    The survey reports optimal-order Fibonacci cubature formulas for mixed-derivative and mixed-difference classes and identifies hyperbolic cross projections as optimal for orthowidths except at p=q=1 and p=q=∞.

  • Takeaways & Limitations

    Hyperbolic cross approximation provides a framework connecting multivariate approximation, mixed smoothness, sparse grids, and numerical integration, while motivating further work on open problems.

  • Takeaways & Limitations

    The survey includes nonconstructive results and unresolved questions, including the open problem of deterministically constructing near-optimal RIP matrices.

Abstract

from arXiv · show

Hyperbolic cross approximation is a special type of multivariate approximation. Recently, driven by applications in engineering, biology, medicine and other areas of science new challenging problems have appeared. The common feature of these problems is high dimensions. We present here a survey on classical methods developed in multivariate approximation theory, which are known to work very well for moderate dimensions and which have potential for applications in really high dimensions. The theory of hyperbolic cross approximation and related theory of functions with mixed smoothness are under detailed study for more than 50 years. It is now well understood that this theory is important both for theoretical study and for practical applications. It is also understood that both theoretical analysis and construction of practical algorithms are very difficult problems. This explains why many fundamental problems in this area are still unsolved. Only a few survey papers and monographs on the topic are published. This and recently discovered deep connections between the hyperbolic cross approximation (and related sparse grids) and other areas of mathematics such as probability, discrepancy, and numerical integration motivated us to write this survey. We try to put emphases on the development of ideas and methods rather than list all the known results in the area. We formulate many problems, which, to our knowledge, are open problems. We also include some very recent results on the topic, which sometimes highlight new interesting directions of research. We hope that this survey will stimulate further active research in this fascinating and challenging area of approximation theory and numerical analysis.

1 Introduction

The survey develops the theory and applications of hyperbolic cross approximation for multivariate functions with mixed smoothness, emphasizing both established results and persistent open problems. It connects approximation widths, sampling recovery, nonlinear approximation, and numerical integration while highlighting the difficulty of high-dimensional analysis and algorithm construction.

  • Scope and motivation: Korobov’s cubature formulas achieve accuracy of order m^-r(log m)^(rd) for bounded mixed-derivative classes, nearly matching the Sobolev-class rate.The Fibonacci formulas work optimally for both bounded mixed derivatives and bounded mixed differences because they are exact on associated hyperbolic cross polynomials.
  • Scope and motivation: The survey addresses multivariate approximation through function classes defined by mixed derivatives or mixed differences, extending classical univariate approximation theory.These classes include W-type Sobolev-type classes and H-type or B-type Besov-type classes.
  • Scope and motivation: Hyperbolic cross polynomials play the multivariate approximation role that classical univariate trigonometric polynomials play in one dimension.This correspondence motivated extensive study of their approximation properties and widths.
  • Linear approximation and widths: For orthowidths, orthogonal projections onto suitable hyperbolic-cross polynomial subspaces are optimal in order for all 1 ≤ p,q ≤ ∞ except p=q=1 and p=q=∞.Establishing the corresponding lower bounds required new nontrivial methods.
  • Sampling recovery: Sampling widths coincide with linear widths in some parameter ranges but are strictly worse in others, and their complete behavior remains unknown.Even for p=2, the exact order of sampling recovery is still unknown; the best-known upper bounds use sparse-grid constructions.
  • Open problems: Several central problems remain unresolved, including entropy-number behavior, the Small Ball Problem connection, and approximation orders for some parameter ranges.The survey stresses that different solved cases required different nontrivial methods.
  • Nonlinear approximation: Nonlinear m-term approximation can substantially improve on hyperbolic cross approximation for some classes, including the regime 2 ≤ p < q < ∞.Wavelet-type bases are often optimal among orthogonal bases for sparse approximation.

2 Trigonometric polynomials

This section introduces trigonometric polynomials as central objects in approximation theory and begins listing concrete kernels used throughout the subject.

  • Trigonometric polynomials are defined through finite sine and cosine expansions.
  • The notation T(n) denotes the set of trigonometric polynomials of order n, while RT(n) denotes its real-valued subset.
  • The section begins examining concrete polynomials that play important roles in approximation theory.
  • The Dirichlet kernel of order n is introduced as the first principal example.

1. The Dirichlet kernel.

The Dirichlet kernel is characterized as an even trigonometric polynomial, used through convolution and partial-sum operators, with logarithmic L1 growth.

  • The Dirichlet kernel is even and has a majorant used in subsequent estimates.
  • ∥D_n∥1 ≤ C ln n for n = 2, 3, . . . .
  • Modified Dirichlet kernels are also introduced through their zeros and related identities.
  • The operator S_n is the partial-sum operator, and its L1 representation is stated for functions in L1.
  • Convolution with D_n defines the operator S_n(f) = f ∗ D_n.
  • S_n leaves polynomials in T(n) unchanged, and its endpoint behavior is established for p = 1 or ∞.

2. The Fejér kernel.

The Fejér kernel is introduced as a standard nonnegative trigonometric polynomial, with basic relations supplying properties used later.

  • The Fejér kernel of order n − 1 is an even, nonnegative trigonometric polynomial in T(n − 1).
  • Its majorant and elementary relations are used to derive subsequent kernel estimates.

3. The de la Vallée Poussin kernels.

The de la Vallée Poussin kernels are constructed from Fejér kernels and define operators that preserve lower-order trigonometric polynomials while supporting Lp estimates.

  • The de la Vallée Poussin kernels are introduced as a distinct family of approximation kernels.
  • They are represented in terms of Fejér kernels.
  • V_m,n is an even trigonometric polynomial of order n − 1 with a stated majorant.
  • The relation (2.8) yields an estimate for these kernels.
  • The commonly used specialization is V_m(x) := V_m,2m(x), with V_0(x) = 1.
  • The operators are defined on L1 through the kernel formula.
  • The operator V_m does not change polynomials from T(m), and the theorem provides bounds for all 1 ≤ p ≤ ∞.
  • For any natural number N, a polynomial of the stated form exists.

4. The Rudin-Shapiro polynomials.

The section develops multivariate trigonometric kernels and emphasizes the distinct behavior of Rudin–Shapiro polynomials within hyperbolic-cross approximation.

  • Kernel constructions: The multivariate system lacks a natural ordering, so the survey defines Dirichlet, Fejér, de la Vallée Poussin, and Rudin–Shapiro analogs for parallelepipeds.These constructions extend familiar univariate tools to frequency sets Π(N, d).
  • 4. The Rudin-Shapiro polynomials: Rudin–Shapiro polynomials have Fourier coefficients of absolute value one while their Lp norms behave differently from Dirichlet kernels.This contrast motivates constructing analogous polynomials in subspaces of multivariate trigonometric polynomial spaces.
  • 4. The Rudin-Shapiro polynomials: For a subspace Ψ ⊂ T(N, d) with dim Ψ ≥ εϑ(N), there exists a polynomial t ∈ Ψ satisfying the stated norm estimate.The result supplies a dimension-based existence statement for polynomials with controlled behavior in large subspaces.
  • Hyperbolic-cross kernels: Hyperbolic-cross kernels retain useful projection properties, but their de la Vallée Poussin analogs lack uniformly bounded L1 norms.This limitation substantially complicates approximation in the L1 and L∞ norms.

1. The Bernstein inequalities.

The Bernstein inequalities are extended from univariate to multivariate trigonometric polynomials and reveal different hyperbolic-cross behavior across Lp spaces.

  • 1. The Bernstein inequalities: The operator D_r^α defines an (r, α)-derivative that is invertible on each T(n), distinguishing it from the ordinary differential operator.The paper uses this operator to formulate Bernstein-type inequalities for trigonometric polynomials.
  • Hyperbolic-cross estimates: For 1 < p < ∞, the hyperbolic-cross Bernstein bound has order N^r.The corresponding displayed theorem gives the interior-Lp estimate for r ≥ 0.
  • Hyperbolic-cross estimates: For p = ∞ and r > 0, the bound has order N^r(log N)^(d−1).The logarithmic factor marks the different form of the uniform-norm inequality.
  • Open endpoint: The correct form of the Bernstein inequalities for p = 1 remains unknown.The survey identifies this as an unresolved endpoint case.

2. The Nikol’skii inequalities.

The Nikol’skii inequalities compare Lq and Lp norms for trigonometric polynomials, with multivariate extensions used in embedding arguments.

  • 2. The Nikol’skii inequalities: The multivariate inequalities extend the univariate Nikol’skii estimates to polynomials in T(N, d) for 1 ≤ q ≤ p ≤ ∞.They are formulated for vector exponents because that form supports embedding-type inequalities.
  • Embedding relations: Theorem 2.11 provides relations for function classes defined by arrays ε, with constants independent of ε.These relations are subsequently interpreted as embeddings.
  • Endpoint behavior: The case q = 1 is nontrivial for polynomials from T(N), and the stated theorems address this difficult regime under p > 1.The survey attributes these results to earlier work.

3. The Marcinkiewicz theorem.

The section presents discrete norm equivalences and volume estimates for trigonometric-polynomial spaces, including special results for hyperbolic-cross frequency sets.

  • 3. The Marcinkiewicz theorem: Marcinkiewicz-type inequalities relate norms of univariate trigonometric polynomials to values sampled on prescribed lattices.The formulation includes the endpoint cases p = 1 and p = ∞ through the theorem using M(t).
  • Finite frequency sets: For finite Λ ⊂ Z^d and 1 ≤ p ≤ 2, Theorem 2.19 gives the stated estimate for the associated trigonometric-polynomial space.This result is presented as an estimate implied by earlier work.
  • Volume estimates: For Λ formed from hyperbolic layers, the volume of the Lp unit ball satisfies vol(BΛ(Lp))(2|Λ|)^−1 ≍ |Λ|^−1/2 for 1 ≤ p < ∞.The comparison is dimension-independent in its displayed exponent, with the theorem applying to finite unions of blocks ρ(s).
  • Hyperbolic-cross volume estimates: For the hyperbolic-cross set Λ = ∆Qn, the estimate for p = ∞ differs from the estimate for 1 ≤ p < ∞.The survey explicitly contrasts this with parallelepiped frequency sets.

3 Function spaces on Td

The survey defines function spaces on the torus through mixed derivatives, differences, Fourier decompositions, and related kernels. These formulations support the analysis of multivariate approximation classes, including Sobolev-, Besov-, Korobov-, and mixed-difference spaces.

  • Sobolev-type spaces: The classes W^r_p are defined using integral representations with tensor-product Bernoulli kernels and generalized to fractional mixed derivatives.The parameter α accommodates mixed derivatives and their trigonometric conjugates; for α=(r,…,r), the notation is simplified.
  • Sobolev-type spaces: For integer r, W^r_p can be characterized through mixed partial derivatives, while fractional r uses weak Weil fractional derivatives.The derivative-based description is equivalent to the integral representation in the classical integer-order setting.
  • Fourier characterizations: Fourier and dyadic decompositions provide useful characterizations of mixed-smoothness classes and are particularly suited to hyperbolic-cross approximation.The Littlewood–Paley norm is stated for 1<p<∞, while endpoint Besov characterizations use modified operators.
  • Besov spaces: Besov spaces B^r_{p,θ} are introduced through mixed moduli of smoothness and remain unchanged, up to equivalent quasi-norms, when the auxiliary integer m>r varies.For p=1 or p=∞, modified frequency-block operators are needed because the standard dyadic operators are not uniformly bounded.
  • Mixed-difference spaces: The spaces H^r_p consist of L_p functions whose mixed differences satisfy bounds for every coordinate subset.Mixed difference operators apply univariate differences coordinatewise while keeping the other variables fixed.
  • Korobov spaces: The classical Korobov space E^r_d is slightly larger than H^r_1 because its kernel condition ensures integrability but does not impose the full H^r_1 condition.The survey states that the relevant kernel condition is exactly the criterion for membership in H^r_1.

4 Linear approximation

Linear approximation studies finite-dimensional subspaces and restricted approximation operators for mixed-smoothness classes. Hyperbolic-cross spaces and projections are optimal in many parameter regions, but endpoint norms, some regions, and constructive realization remain difficult or unresolved.

  • Hyperbolic-cross subspaces: For m=|Γ(N)|, the L_2-optimal approximation subspace is the space of hyperbolic-cross polynomials T(Γ(N)).This follows from ordering the trigonometric eigenfunctions of the relevant operator.
  • Kolmogorov widths: For (p,q)∈D1, trigonometric approximation in T(n) gives the order of the Kolmogorov widths, whereas outside D1 it generally does not.The survey distinguishes regions where standard hyperbolic-cross approximation realizes Kolmogorov-width orders from regions requiring different methods.
  • Linear widths: The operators V_n with m=4^n−1 realize linear-width orders in D1∪D2, but their order cannot be realized by V_n in D3.In D3, achieving the linear-width order requires operators other than the standard V_n projections.
  • Orthowidths: The Fourier operators S_n with m=2^n+1 are order-optimal for W^r_p in all (p,q) except (1,1) and (∞,∞).For 1<p<∞, the analogous role is played by the projections S_{Q_n}.
  • Width comparisons: Kolmogorov widths can decrease faster than corresponding linear widths, as demonstrated for p=2 and q=∞.Better approximation in such cases requires sacrificing useful properties of the standard operators.
  • Constructivity: Some bounds rely on probabilistic existence proofs of special matrices, making the resulting approximation results non-constructive.These matrices are connected to restricted-isometry constructions used in compressed sensing.
  • Open problems: The survey identifies unresolved orders for several parameter regions, especially extreme p or q values and parts of the H^r_p theory.It also notes that uniform-norm approximation and some high-dimensional cases remain particularly difficult.

5 Sampling recovery

The section studies sampling recovery for multivariate function classes with mixed smoothness, focusing on sparse-grid and hyperbolic-cross constructions. It establishes optimal-order results in several parameter regimes while identifying unresolved cases and smoothness restrictions.

  • Problem setting: Sampling widths measure approximation from fixed function values, whereas linear widths optimize over linear approximation operators; their relationship is not generally known.The section emphasizes that sampling and linear approximation impose different restrictions, so neither characteristic universally determines the other.
  • Smolyak sampling: Smolyak-based sampling operators use sparse-grid points and are optimal in order for sampling widths in several regimes, including the established cases with p < q.The operators are constructed from univariate sampling operators through tensorization and Smolyak’s algorithm.
  • Optimality: The operators Tn are optimal among linear operators approximating by hyperbolic-cross polynomials in the stated parameter domains.This conclusion is reported for both the Wr and Hr settings under the conditions of Theorems 5.6–5.7 and Proposition 5.8.
  • Known regimes: Sharp sampling-width results are available in selected exponent ranges, including 1 < p < q ≤ 2 and 2 ≤ p < q < ∞ when r > 1/p.The section also gives corresponding theorem statements for uniform-error and mixed-smoothness settings under explicit restrictions on p, q, θ, and r.
  • B-spline sampling: A second construction uses Smolyak grids with tensor products of compactly supported hat functions and B-splines instead of trigonometric-polynomial approximants.The associated Faber-Schauder representations and propositions apply only within specified smoothness ranges.
  • Open problems: Important gaps remain: sampling versus linear widths is unresolved in some regimes, including 1 < p < 2 < q < ∞, and low-smoothness behavior remains conjectural or difficult.The text conjectures that sampling may be worse than approximation in one such regime and identifies open questions for small smoothness.

6 Entropy numbers

This section develops entropy numbers as a volume-like measure of compactness and relates them to approximation widths, nonlinear approximation, and mixed-smoothness classes. It records finite-dimensional estimates, interpolation inequalities, sharp two-dimensional rates, and open higher-dimensional questions.

  • Definitions: Entropy replaces volume for measuring compact sets in infinite-dimensional Banach spaces and is defined through finite coverings.The covering number N_ε(A) counts the minimum number of radius-ε balls needed to cover A; entropy numbers encode equivalent covering information.
  • Finite-dimensional estimates: Volume arguments yield entropy bounds for unit balls of finite-dimensional spaces, including explicit estimates for ℓ_p^d balls.Theorem 6.3 provides bounds for entropy numbers of B_p^d when 0 < p < q ≤ ∞.
  • Widths and nonlinear approximation: Entropy numbers are connected to Kolmogorov widths and nonlinear widths, including approximations that select among multiple subspaces for each function.The nonlinear width d_m(F, X, N) permits a subspace depending on f, while Theorem 6.6 relates entropy numbers to these widths.
  • Widths and nonlinear approximation: Entropy estimates support lower bounds for best m-term approximation and sharp upper bounds for classes with mixed smoothness.Theorem 6.9 is stated as useful for both types of bounds.
  • Operator inequalities: For operators, entropy numbers satisfy an L_p interpolation inequality combining L_1 and L_∞ estimates.Theorem 6.11 gives ε_{n+m}(S : L_p → Y) ≤ 2ε_n(S : L_1 → Y)^{1/p}ε_m(S : L_∞ → Y)^{1−1/p}.

7 Best m-term approximation

Best m-term approximation studies how to construct sparse approximants whose selected dictionary elements depend on the function, with accuracy and algorithm design as central concerns. The survey compares dictionaries and algorithms across mixed-smoothness classes and parameter ranges, identifying optimality results, multivariate logarithmic effects, and remaining open problems.

  • Introduction: Nonlinear approximation seeks constructive algorithms that select m dictionary elements depending on the function, extending basis-based approximation to redundant systems.The survey distinguishes function-dependent m-term selection from the more complicated use of nonminimal dictionaries.
  • Introduction: For any dictionary, σm(F, D)X provides a sharp lower bound for best m-term approximation of a function class.This quantity benchmarks the best achievable class-wide performance across dictionaries.
  • Orthogonal bases: For 1 < p, q < ∞, the wavelet-type dictionary Ud provides optimal upper estimates in several best m-term approximation settings and can be used with a greedy algorithm.The survey reports that near-best approximations in Lq can be realized by the simple greedy algorithm Gq(·, Ud).
  • The case q ≤ p: In 1 < p < q ≤ 2, sparse approximation exhibits a multivariate improvement through the power of log m, an effect absent in the univariate setting.A related result for 1 < p = q < 2 is described as a previously unknown multivariate phenomenon, with sparse trigonometric and Haar wavelet approximation yielding the same rate in the cited example.
  • Orthogonal bases: The trigonometric system is order-optimal among orthonormal systems in several parameter ranges, while Ud performs better in other ranges of 1 < p, q < ∞.The comparison depends on the relation between p and q; the survey attributes the difference possibly to uniform boundedness of the trigonometric system.

8 Numerical integration

The survey develops numerical integration for multivariate functions with mixed smoothness, emphasizing cubature rules, sparse grids, and number-theoretic constructions. Matching lower and upper bounds are established across broad parameter ranges, while several sharpness and high-dimensional questions remain open.

  • Problem formulation: Numerical integration approximates an integral by a weighted sum of finitely many function values, with optimal error defined by minimizing over nodes and weights.The framework uses cubature formulas Λm(·, Xm) and the quantity κm(F).
  • Smolyak grids: Smolyak-grid lower bounds are sharp because cubature formulas on Smolyak grids attain matching upper bounds, although adding 2n−1 arbitrary nodes does not improve the bound in (8.8).The sparse grid SGd(n) has |SGd(n)| ≍ 2^n n^(d−1).
  • Fibonacci cubature: Fibonacci cubature formulas are optimal in order in the stated settings, with upper bounds obtained using these quasi-Monte Carlo rules.For d = 2, they provide particularly simple optimal cubature rules.
  • Open problems: Open problems include sharp bounds for multivariate Frolov cubature, behavior at r = 1/2, and discrepancy bounds whose asymptotic usefulness may require m > e^(d−1).The survey also notes recent progress proving conjectured lower bounds for several point constructions.
  • Frolov cubature: Frolov cubature achieves errors of order a−rd(log a)^(d−1)/2 and a−rd(log a)^(d−1)(1−1/θ) in the stated parameter regimes.For θ = 1, the logarithmic factor disappears, giving a−d/p in the corresponding case.
  • Optimality: Theorems 8.1 and 8.3 provide lower bounds for cubature rules, and Theorem 8.14 supplies matching upper bounds over a large range of function classes.Thus the asymptotic behavior of κm(F) is determined in that range.
  • Digital nets: Higher-order digital-net methods achieve d-dimensional rates for 1/p < r < 2, but the restriction r < 2 remains unsatisfactory compared with Frolov cubature.For kink-functions with regularity r = 2 when p = 1, numerical experiments indicate that the method can exploit this regularity.

9 Related problems

The survey connects hyperbolic cross approximation with mixed-smoothness function classes, cubature, widths, embeddings, and lattice-based sampling. It records universal and optimal constructions in several settings while identifying unresolved parameter ranges and complexity barriers.

  • Motivation: Mixed smoothness classes arise naturally in integral equations and other multivariate problems because products and kernels transfer smoothness into mixed derivatives.The survey presents both a priori and a posteriori reasons for their importance.
  • Universal cubature: Fibonacci cubature formulas are universal for anisotropic Hölder-Nikol’skii classes, providing order-optimal error bounds independently of the smoothness vector and p.For d > 2, universal formulas exist but have a character different from the Fibonacci constructions.
  • m-term approximation: The orthonormal bases Ud are order-optimal for m-term approximation of mixed-smoothness classes and universal for classes with anisotropic smoothness.The result is stated through the approximation behavior summarized in Theorem 9.1.
  • Embeddings: Embedding results characterize boundedness by r ≥ 1/p − 1/q and compactness by the strict condition r > 1/p − 1/q in the stated spaces.The corresponding embeddings for spaces on R^d are never compact in the specified p ≤ q case.
  • Sampling: Sparse grids can be optimal for sampling in some regimes, but optimal sampling remains unknown for q ≤ p except in the case d = 2 and p = q = ∞.Lattice methods offer FFT acceleration and better numerical stability with oversampling, yet are not optimal in information complexity.
  • Complexity: Randomized sampling recovery exhibits a curse of dimensionality exactly when M ≥ 2r r!, whereas complexity is polynomial in the complementary regime.A deterministic Halton-point construction has L∞ error ≲ C(r,d)N−r, with C(d,r) scaling like d^(dr).
  • Applications: Mixed and isotropic Sobolev regularity occurs for broad classes of electronic Schrödinger solutions, and sampling recovery can attain the correct order of the sampling widths.The survey states corresponding results under explicit conditions on r, β, and γ.

10 High-dimensional approximation

High-dimensional hyperbolic cross approximation is governed by dimension-sensitive logarithmic factors and difficult preasymptotic behavior. Anisotropy and infinite-dimensional weighted settings offer routes toward tractability, while several sharp bounds and constructions remain technically challenging.

  • High-dimensional approximation: For fixed smoothness parameters, typical errors behave like m^-r(log m)^(d−1)ξ, but the logarithmic factor can dominate when d is large.The survey identifies this as a major obstacle for practical high-dimensional approximation.
  • Anisotropic approximation: Anisotropic mixed-smoothness classes replace the dimension-dependent logarithmic factor by (log m)^(ν−1)ξ when ν variables have the smallest smoothness.For upper bounds, the hyperbolic cross must be adapted to the class’s smoothness; numerical integration methods may detect anisotropy without adaptation.
  • Asymptotics and preasymptotics: In large dimensions, asymptotic constants may decay super-exponentially, yet the asymptotic regime can begin only after exponentially many terms.The survey therefore distinguishes asymptotic behavior from the preasymptotic range, including m below 2^d.
  • Asymptotics and preasymptotics: The preasymptotic upper bound for 2 ≤ m ≤ 2^d has no hidden constant and reflects quasi-polynomial tractability.This result is based on a refined estimate for the cardinality of the hyperbolic cross.
  • Explicit bounds: The survey reports explicit dimension-dependent upper and lower bounds for several approximation problems, including thresholds m > λ(r)^d for 1 < r ≤ 2.For these results, the constants C_r and C′_r depend only on r, while the dependence on d is explicit.
  • Infinite dimensions: Infinite-dimensional approximation is motivated by uncertainty quantification, computational finance, computational physics, and stochastic or parametric PDEs.Recent work studies linear hyperbolic cross approximation and ε-dimensions for mixed Sobolev-type spaces under summability conditions on smoothness.

11 Appendix

The appendix collects notation and standard analytic tools used throughout the survey. It introduces function and sequence spaces, Fourier coefficients, duality, interpolation, multiplier, and convolution inequalities.

  • Function spaces: The appendix defines vector duality exponents and the spaces Lq(Td), including the distinction between norms and quasi-norms.For 0 < q < 1, the Lq quantity is a quasi-norm; C(Td) is used as a continuous periodic replacement for L∞(Td).
  • Basic inequalities: It records Hölder-type inequalities for functions, vectors, sums, and products, together with interpolation inequalities and the Young convolution inequality.These results provide routine estimates for later approximation arguments.
  • Functional and Fourier analysis: The appendix introduces sequence spaces lp, dual spaces, Fourier coefficients, and standard duality results such as Nikol’skii duality.It also states Parseval, Hausdorff–Young, and Riesz–Fischer results for Fourier analysis.
  • Harmonic-analysis tools: Littlewood–Paley, Marcinkiewicz multiplier, and Hardy–Littlewood–Sobolev theorems are listed as standard tools for multivariate harmonic analysis.The stated operator bounds apply under the corresponding exponent conditions.
Loading 1601.03978v3…