On the power of iid information for linear approximation

Abstract

This survey is concerned with the power of random information for approximation in the (deterministic) worst-case setting, with special emphasis on information consisting of functionals selected independently and identically distributed (iid) at random on a class of admissible information functionals. We present a general result based on a weighted least squares method and derive consequences for special cases. Improvements are available if the information is ``Gaussian'' or if we consider iid function values for Sobolev spaces. We include open questions to guide future research on the power of random information in the context of information-based complexity.

arXiv comment63 pages

References in corpus (11)

• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• The Curse of Dimensionality for Numerical Integration of Smooth Functions II
• A Lower Bound for the Discrepancy of a Random Point Set
• Optimal pointwise sampling for $L^2$ approximation
• Random points are good for universal discretization
• On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
• Exponential tractability of $L_2$-approximation with function values
• New lower bounds for the integration of periodic functions
• On the Small Ball Inequality in All Dimensions
• The power of random information for numerical approximation and integration
• Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case

Cited by in corpus (4)

• Sampling projections in the uniform norm
• Sampling recovery in $L_2$ and other norms
• Approximation of Functions: Optimal Sampling and Complexity
• Sampling and entropy numbers in the uniform norm