Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods

DOI10.1016/j.jco.2018.04.002zbMath1473.65009arXiv1712.03843OpenAlexW2962851123MaRDI QIDQ722763

Robert J. Kunsch

Publication date: 27 July 2018

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

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

zbMATH Keywords

Hilbert spacescurse of dimensionalityinformation-based complexitylinear informationMonte Carlo approximationpolynomial tractability

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Concentration inequalities for cross-validation in scattered data approximation ⋮ A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm

Uses Software

• DLMF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal approximation of multivariate periodic Sobolev functions in the sup-norm
• Product rules are optimal for numerical integration in classical smoothness spaces
• A mathematical introduction to compressive sensing
• The randomized complexity of indefinite integration
• Tractability of multivariate problems. Volume III: Standard information for operators
• Multivariate \(L_{\infty}\) approximation in the worst case setting over reproducing kernel Hilbert spaces
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Random approximation of Sobolev embeddings
• Lower bounds for the complexity of Monte Carlo function approximation
• Deterministic and stochastic error bounds in numerical analysis
• Gaussian measures in Banach spaces
• Average-case analysis of numerical problems
• Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness
• Ismagilov type theorems for linear, Gel'fand and Bernstein \(n\)-widths
• On the approximate calculation of multiple integrals
• The information-based complexity of approximation problem by adaptive Monte Carlo methods
• Sample functions of the Gaussian process
• Bernstein Numbers and Lower Bounds for the Monte Carlo Error
• s-Numbers of operators in Banach spaces
• DIAMETERS OF SOME FINITE-DIMENSIONAL SETS AND CLASSES OF SMOOTH FUNCTIONS
• Discontinuous information in the worst case and randomized settings
• Theory of Reproducing Kernels