Lower bounds for the complexity of Monte Carlo function approximation

DOI10.1016/0885-064X(92)90027-9zbMath0768.46020OpenAlexW2081771468MaRDI QIDQ1201159

Stefan Heinrich

Publication date: 17 January 1993

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

Full work available at URL: https://doi.org/10.1016/0885-064x(92)90027-9

zbMATH Keywords

Sobolev spaceGaussian measuresembedding operatorinformation operatoraverage Gelfand and approximation numbersMayorov discretisation techniqueMonte Carlo approximations for linear operators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Monte Carlo methods (65C05) Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Riesz operators; eigenvalue distributions; approximation numbers, (s)-numbers, Kolmogorov numbers, entropy numbers, etc. of operators (47B06) Random linear operators (47B80) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Related Items

Kolmogorov and Linear Widths on Generalized Besov Classes in the Monte Carlo Setting ⋮ Exact asymptotic orders of various randomized widths on Besov classes ⋮ Some Results on the Complexity of Numerical Integration ⋮ Bernstein Numbers and Lower Bounds for the Monte Carlo Error ⋮ Randomized approximation numbers on Besov classes with mixed smoothness ⋮ The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods ⋮ Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness ⋮ The recovery of ridge functions on the hypercube suffers from the curse of dimensionality ⋮ Linear widths of a multivariate function space equipped with a Gaussian measure ⋮ Discontinuous information in the worst case and randomized settings ⋮ The randomized information complexity of elliptic PDE ⋮ Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure ⋮ Approximation characteristics for diagonal operators in different computational settings ⋮ Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods ⋮ The information-based complexity of approximation problem by adaptive Monte Carlo methods ⋮ On the power of standard information for \(L_{\infty}\) approximation in the randomized setting ⋮ Linear average and stochastic \(n\)-widths of Besov embeddings on Lipschitz domains ⋮ The power of standard information for multivariate approximation in the randomized setting

Cites Work

• s-numbers in information-based complexity
• Probabilistic complexity analysis for linear problems in bounded domains
• Random approximation of Sobolev embeddings
• Parallel information-based complexity
• Deterministic and stochastic error bounds in numerical analysis
• Gaussian measures in Banach spaces
• Eigenvalue distribution of compact operators
• Invertibility of random fredholm operators
• Mappings of Gaussian Cylindrical Measures in Banach Spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item