Lower bounds for the complexity of linear functionals in the randomized setting

DOI10.1016/J.JCO.2010.08.002MaRDI QIDQ617652zbMATH OpenOpenAlexFDO

Authors Erich Novak, H. Woźniakowski

Publication date 21 January 2011

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

Full work available at URL https://doi.org/10.1016/j.jco.2010.08.002

zbMATH Keywords

complexity in the randomized settingsdecomposable kernelsintegration over reproducing kernel Hilbert spacesoptimal Monte Carlo method

Mathematics Subject Classification ID

Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22) Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20)

Review text

The authors establish the sharpness conditions for the exponent in the approximation estimator from \textit{A.~Hinrichs} [J. Complexity 26, No.~2, 125--134 (2010; Zbl 1191.65003)]. In particular it is proved the sharpness of the exponent ``\dots for tensor product Hilbert spaces whose univariate reproducing kernel is decomposable and univariate integration is not trivial for the two parts of the decomposition.

Recommendations

• The power of standard information for multivariate approximation in the randomized setting
• On the power of standard information for \(L_{\infty}\) approximation in the randomized setting
• scientific article; zbMATH DE number 2161076
• Tractability of tensor product linear operators
• scientific article; zbMATH DE number 5286769

Cites work

• Deterministic and stochastic error bounds in numerical analysis
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 45848 (Why is no real title available?)
• Intractability results for integration and discrepancy
• Optimal importance sampling for the approximation of integrals
• The power of standard information for multivariate approximation in the randomized setting
• Theory of Reproducing Kernels
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Variational properties of averaged equations for periodic media

Cited in

(7)

• Lower bound on complexity of optimization of continuous functions
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• Some results on the complexity of numerical integration
• Linear FPT reductions and computational lower bounds
• scientific article; zbMATH DE number 1534573 (Why is no real title available?)
• Lower space bounds for randomized computation
• Probabilistic complexity analysis for linear problems in bounded domains

This page was built for publication: Lower bounds for the complexity of linear functionals in the randomized setting

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