Embeddings for infinite-dimensional integration and L₂-approximation with increasing smoothness

DOI10.1016/J.JCO.2019.04.002MaRDI QIDQ2274409zbMATH OpenOpenAlexFDO

Authors Michael Gnewuch, Mario Hefter, Aicke Hinrichs, Klaus Ritter, Grzegorz W. Wasilkowski

Publication date 19 September 2019

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.07103

zbMATH Keywords

embedding theoremshigh-dimensional integrationinfinite-dimensional integrationreproducing kernel Hilbert spacestractability

Mathematics Subject Classification ID

Approximate quadratures (41A55) Multidimensional problems (41A63) Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Numerical integration (65D30)

Abstract: We study integration and $L_2$-approximation on countable tensor products of function spaces of increasing smoothness. We obtain upper and lower bounds for the minimal errors, which are sharp in many cases including, e.g., Korobov, Walsh, Haar, and Sobolev spaces. For the proofs we derive embedding theorems between spaces of increasing smoothness and appropriate weighted function spaces of fixed smoothness.

Review text

The authors consider the problems of integration/approximation of functions depending on an infinite number of variables. Clearly, in order to make this non-trivial, weighted spaces must be considered. Focus is on the information complexity of such problems. It is evident that a rigorous treatment of these problems requires a theoretical backbone. This is established in Section~2 (Tensor products and reproducing kernels) and Section~3 (Increasing smoothness and weights), going beyond the classical setup. The main results are established in Section~4 (Infinite-dimensional approximation and integration) by controlling the associated $n$-th minimal errors, i.e., the best possible accuracy by using algorithms of cost at most~$n$. The framework for this analysis is within the theory of information-based complexity, see the recent monographs [\textit{E. Novak} and \textit{H. Woźniakowski}, Tractability of multivariate problems. Volume I: Linear information. Zürich: European Mathematical Society (EMS) (2008; Zbl 1156.65001); Tractability of multivariate problems. Volume II: Standard information for functionals. Zürich: European Mathematical Society (EMS) (2010; Zbl 1241.65025); Tractability of multivariate problems. Volume III: Standard information for operators. Zürich: European Mathematical Society (EMS) (2012; Zbl 1359.65003)]. Within the `standard setting' (made precise in the study), the major result is Theorem~4.5, upper and lower bounding the decay rates of the $n$-th minimal errors (for both the integration and approximation problem) in terms of the considered weights. Several examples and counter-examples accompany the theoretical analysis. Three appendices provide additional information.

Recommendations

• Tractability of infinite-dimensional integration in the worst case and randomized settings
• Liberating the dimension for \(L_2\)-approximation
• Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
• Exponential convergence of an approximation problem for infinitely differentiable multivariate functions
• scientific article; zbMATH DE number 2161076
• Computational complexity of continuous problems
• Complexity of weighted approximation over \(\mathbb{R}\)
• On the power of standard information for multivariate approximation in the worst case setting
• Probabilistic complexity analysis for linear problems in bounded domains
• Average complexity for linear problems in a model with varying information noise

Cites work

• A note on equivalence of anchored and ANOVA spaces; lower bounds
• Derivative based quasi-Monte Carlo constructions and sensitivity estimations
• Discrepancy theory and quasi-Monte Carlo integration
• Efficient implementations of the multivariate decomposition method for approximating infinite-variate integrals
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• Equivalence of anchored and ANOVA spaces via interpolation
• Equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in \(L_p\)
• High-dimensional integration: The quasi-Monte Carlo way
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3861745 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 1049042 (Why is no real title available?)
• scientific article; zbMATH DE number 3301601 (Why is no real title available?)
• scientific article; zbMATH DE number 3031209 (Why is no real title available?)
• Hyperbolic cross approximation in infinite dimensions
• Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• Jacobi Polynomials, Weighted Sobolev Spaces and Approximation Results of Some Singularities
• Liberating the dimension
• Liberating the dimension for \(L_2\)-approximation
• Liberating the dimension for function approximation and integration
• Liberating the dimension for function approximation: standard information
• Lower error bounds for randomized multilevel and changing dimension algorithms
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Novel results for the anisotropic sparse grid quadrature
• On decompositions of multivariate functions
• On embeddings of weighted tensor product Hilbert spaces
• On equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in \(L_1\) or \(L_\infty\)
• On tractability of linear tensor product problems for \(\infty \)-variate classes of functions
• On weighted Hilbert spaces and integration of functions of infinitely many variables
• Optimal quadrature for Haar wavelet spaces
• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Stable splittings of Hilbert spaces of functions of infinitely many variables
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
• Tractability of infinite-dimensional integration in the worst case and randomized settings
• Tractability of multivariate analytic problems
• Tractability of multivariate approximation defined over Hilbert spaces with exponential weights
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability through increasing smoothness
• Truncation dimension for linear problems on multivariate function spaces
• Uniform weak tractability of multivariate problems with increasing smoothness
• Very low truncation dimension for high dimensional integration under modest error demand
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(8)

• How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
• Countable tensor products of Hermite spaces and spaces of Gaussian kernels
• Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
• \( \varepsilon \)-superposition and truncation dimensions in average and probabilistic settings for \(\infty \)-variate linear problems
• Equivalence between Sobolev spaces of first-order dominating mixed smoothness and unanchored ANOVA spaces on \(\mathbb{R}^d\)
• Infinite-dimensional integration and L²-approximation on Hermite spaces
• A note on compact embeddings of reproducing kernel Hilbert spaces in L^2 and infinite-variate function approximation
• Infinite-variate L^2-approximation with nested subspace sampling

This page was built for publication: Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274409)