Approximation of Functions: Optimal Sampling and Complexity

Abstract

We consider approximation or recovery of functions based on a finite number of function evaluations. This is a well-studied problem in optimal recovery, machine learning, and numerical analysis in general, but many fundamental insights were obtained only recently. We discuss different aspects of the information-theoretic limit that appears because of the limited amount of data available, as well as algorithms and sampling strategies that come as close to it as possible. We also discuss (optimal) sampling in a broader sense, allowing other types of measurements that may be nonlinear, adaptive and random, and present several relations between the different settings in the spirit of information-based complexity. We hope that this article provides both, a basic introduction to the subject and a contemporary summary of the current state of research.

This is a preliminary version of an article to appear in Acta Numerica

References in corpus (35)

• User-friendly tail bounds for sums of random matrices
• Determinantal point processes for machine learning
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• Determinantal point process models and statistical inference : Extended version
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• The Numerics of Phase Retrieval
• Optimal experimental design: Formulations and computations
• Integral norm discretization and related problems
• Rate of Convergence and Tractability of the Radial Function Approximation Problem
• Adaptive Finite Element Methods
• The Curse of Dimensionality for Numerical Integration of Smooth Functions II
• Optimal pointwise sampling for $L^2$ approximation
• The curse of dimensionality for numerical integration on general domains
• The Curse of Dimensionality for Numerical Integration of Smooth Functions
• Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces
• Random points are good for universal discretization
• On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
• A note on sampling recovery of multivariate functions in the uniform norm
• On Weak Tractability of the Clenshaw-Curtis Smolyak Algorithm
• Exponential tractability of $L_2$-approximation with function values
• Product rules are optimal for numerical integration in classical smoothness spaces
• New lower bounds for the integration of periodic functions
• The Complexity of Linear Tensor Product Problems in (Anti-) Symmetric Hilbert Spaces
• On the power of iid information for linear approximation
• Discontinuous information in the worst case and randomized settings
• Optimal polynomial meshes exist on any multivariate convex domain
• Sampling projections in the uniform norm
• Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions: Error bounds and tractability
• Monte Carlo Methods for Uniform Approximation on Periodic Sobolev Spaces with Mixed Smoothness
• Inequalities between s-numbers
• Sampling recovery in $L_2$ and other norms
• On the power of adaption and randomization
• Function recovery on manifolds using scattered data
• Random sections of ${\ell }_p$-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators
• Sampling and entropy numbers in the uniform norm