Lower bounds for the complexity of Monte Carlo function approximation

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

Stefan Heinrich

Publication date: 17 January 1993

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

zbMATH Keywords

Sobolev space; Gaussian measures; embedding operator; information operator; average Gelfand and approximation numbers; Mayorov discretisation technique; Monte Carlo approximations for linear operators

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65C05: Monte Carlo methods

46E35: Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems

47B06: Riesz operators; eigenvalue distributions; approximation numbers, (s)-numbers, Kolmogorov numbers, entropy numbers, etc. of operators

47B80: Random linear operators

41A46: Approximation by arbitrary nonlinear expressions; widths and entropy

Related Items

Discontinuous information in the worst case and randomized settings, Probabilistic and average widths of multivariate Sobolev spaces with mixed derivative equipped with the Gaussian measure, The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear 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, Linear widths of a multivariate function space equipped with a Gaussian measure, The randomized information complexity of elliptic PDE, Approximation characteristics for diagonal operators in different computational settings, The information-based complexity of approximation problem by adaptive Monte Carlo methods, Kolmogorov and Linear Widths on Generalized Besov Classes in the Monte Carlo Setting, Some Results on the Complexity of Numerical Integration, Bernstein Numbers and Lower Bounds for the Monte Carlo Error, The power of standard information for multivariate approximation in the randomized setting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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