Tractability of multivariate problems for standard and linear information in the worst case setting. I.
From MaRDI portal
Publication:281550
DOI10.1016/J.JAT.2016.02.017zbMATH Open1404.65010arXiv1511.05803OpenAlexW2964343121MaRDI QIDQ281550FDOQ281550
Publication date: 11 May 2016
Published in: Journal of Approximation Theory (Search for Journal in Brave)
Abstract: We present a lower error bound for approximating linear multivariate operators defined over Hilbert spaces in terms of the error bounds for appropriately constructed linear functionals as long as algorithms use function values. Furthermore, some of these linear functionals have the same norm as the linear operators. We then apply this error bound for linear (unweighted) tensor products. In this way we use negative tractability results known for linear functionals to conclude the same negative results for linear operators. In particular, we prove that -multivariate approximation defined for standard Sobolev space suffers the curse of dimensionality if function values are used although the curse is not present if linear functionals are allowed.
Full work available at URL: https://arxiv.org/abs/1511.05803
Complexity and performance of numerical algorithms (65Y20) Multidimensional problems (41A63) Algorithms for approximation of functions (65D15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- An optimal Poincaré inequality for convex domains
- Quasi-polynomial tractability
- Tractability of multivariate problems. Volume III: Standard information for operators
- Linear information versus function evaluations for \(L_2\)-approximation
- Tractability of multivariate problems. Volume I: Linear information
- Tractability of multivariate problems. Volume II: Standard information for functionals.
- Tractability of multivariate integration for periodic functions
- Weighted tensor product algorithms for linear multivariate problems
- Intractability results for integration and discrepancy
- Tractability of approximating multivariate linear functionals
- Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces
Cited In (14)
- Function values are enough for \(L_2\)-approximation
- Recovery of regular ridge functions on the ball
- Generalized tractability for multivariate problems. II: Linear tensor product problems, linear information, and unrestricted tractability
- Tractability of multivariate problems. Volume I: Linear information
- Lower bounds for the error of quadrature formulas for Hilbert spaces
- Lower bounds for integration and recovery in \(L_2\)
- On recovery of regular ridge functions
- On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting
- Explicit cost bounds of algorithms for multivariate tensor product problems
- Exponential tractability of \(L_2\)-approximation with function values
- A sharp upper bound for sampling numbers in \(L_2\)
- On the power of standard information for tractability for \(L_2\)-approximation in the average case setting
- On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting
- Tractability of Multivariate Problems for Standard and Linear Information in the Worst Case Setting: Part II
This page was built for publication: Tractability of multivariate problems for standard and linear information in the worst case setting. I.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281550)
