Worst case tractability of linear problems in the presence of noise: linear information

DOI10.1016/j.jco.2023.101782arXiv2303.16328OpenAlexW4385269550MaRDI QIDQ6062169

Paweł Siedlecki, Leszek Plaskota

Publication date: 30 November 2023

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

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

zbMATH Keywords

information-based complexitytractabilitynoisy information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity and performance of numerical algorithms (65Y20) Numerical approximation of high-dimensional functions; sparse grids (65D40)

Cites Work

• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Statistical estimation and optimal recovery
• Complexity of approximating Hölder classes from information with varying Gaussian noise
• Worst case complexity of problems with random information noise
• How to benefit from noise
• Noisy Information and Computational Complexity