Discontinuous information in the worst case and randomized settings

DOI10.1002/mana.201100128zbMath1270.65024arXiv1106.2945OpenAlexW3122414092MaRDI QIDQ4925038

Aicke Hinrichs, Erich Novak, Henryk Woźniakowski

Publication date: 11 June 2013

Published in: Mathematische Nachrichten (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmsdiscontinuous information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General theory of numerical analysis in abstract spaces (65J05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Non-Asplund Banach spaces and operators ⋮ ABC on IBC ⋮ Ultrastability of \(n\)th minimal errors ⋮ Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals ⋮ Tractability of multivariate approximation over weighted standard Sobolev spaces ⋮ Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods ⋮ Tractability for Volterra problems of the second kind with convolution kernels ⋮ Nonexistence of certain universal polynomials between Banach spaces

Uses Software

• ShearLab
• Wavelet and Multiscale Library

Cites Work

• Randomized approximation of Sobolev embeddings. II
• Randomized approximation of Sobolev embeddings. III
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• On the relation between linear n-widths and approximation numbers
• Random approximation of Sobolev embeddings
• Optimal linear randomized methods for linear operators in Hilbert spaces
• Lower bounds for the complexity of Monte Carlo function approximation
• A minimax principle for the optimal error of Monte Carlo methods
• Deterministic and stochastic error bounds in numerical analysis
• Sampling numbers and function spaces
• A universal non-compact operator