4. On the power of random information

DOI10.1515/9783110635461-004OpenAlexW4214639496MaRDI QIDQ3300052

Erich Novak, Mario Ullrich, Aicke Hinrichs, David Krieg, Joscha Prochno

Publication date: 27 July 2020

Published in: Multivariate Algorithms and Information-Based Complexity (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Numerical quadrature and cubature formulas (65D32) Complexity and performance of numerical algorithms (65Y20) Asymptotic theory of convex bodies (52A23) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (13)

Spectral flatness and the volume of intersections of \(p\)-ellipsoids ⋮ Random sections of ellipsoids and the power of random information ⋮ Best and random approximation of a convex body by a polytope ⋮ A new upper bound for sampling numbers ⋮ A sharp upper bound for sampling numbers in \(L_2\) ⋮ Recovery of Sobolev functions restricted to iid sampling ⋮ Random sections of \(\ell_p\)-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators ⋮ On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting ⋮ Function values are enough for \(L_2\)-approximation ⋮ Function values are enough for \(L_2\)-approximation. II ⋮ Worst-case recovery guarantees for least squares approximation using random samples ⋮ A new look at random projections of the cube and general product measures ⋮ Lower bounds for the error of quadrature formulas for Hilbert spaces

This page was built for publication: 4. On the power of random information