PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation of Functions: Optimal Sampling and Complexity

David Krieg, Mario Ullrich

arXiv:2602.02066v2math.NAcs.IT

TL;DR

The paper addresses how to approximate functions when only finitely many costly measurements are available, and how this limitation compares with idealized approximation benchmarks. It surveys general sampling algorithms, complexity bounds, and broader measurement models, reporting sharp sampling-number bounds while identifying important scope limits for some constructions.

  • Problem

    The central question is how finite available measurements limit approximation and how much data different admissible measurement classes require relative to idealized approximation benchmarks.

  • Method

    The paper provides a systematic survey of general sampling algorithms, error bounds, sampling strategies, and relations among linear, nonlinear, adaptive, randomized, and other measurement settings.

  • Results

    The survey obtains several sharp bounds on sampling numbers and presents sampling strategies that can approach theoretical error bounds across multiple settings.

  • Takeaways & Limitations

    The results clarify the capabilities and limitations of optimal sampling algorithms and connect numerical analysis, approximation theory, and theoretical data science through admissible information.

  • Takeaways & Limitations

    Some entropy- and Hilbert-number bounds are nonconstructive, with no known explicit algorithm achieving them.

Abstract

from arXiv · show

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.

1. Introduction and overview

The article surveys how finite, costly measurements limit function approximation and how sampling algorithms can approach theoretical benchmarks. It develops general results on sampling complexity, algorithms, and broader measurement settings across model classes.

  • Motivation: Finite measurements make problem information incomplete, creating a fundamental limit on achievable reconstruction accuracy.Measurements may come from physical experiments, simulations, or questionnaires, and each carries a cost.
  • Motivation: The survey studies how sampling schemes and algorithms can approach approximation benchmarks while also deriving lower bounds on the data required.The benchmarks may use information that is unrealistic or unavailable in practice, such as best approximation from a linear space or manifold.
  • Framework: The paper formulates algorithms through a measurement map and reconstruction map, using n measurements together with prior knowledge that f∈F.The measurement map acts as an encoder and the reconstruction map as a decoder; function values are a central measurement model.
  • Framework: Sampling numbers quantify the smallest worst-case Y-error achievable by algorithms using at most n samples.Typical target spaces include Lp spaces and bounded functions equipped with the sup-norm.
  • Scope: The survey emphasizes general results for broad model classes and minimal assumptions rather than a collection of results for specific classes.Examples are used mainly to illustrate the power and weaknesses of the general theory.
  • Scope: Its analysis covers least squares, sparse approximation, entropy and Hilbert benchmarks, probabilistic methods, randomized sampling, and constructive strategies.The entropy- and Hilbert-number bounds discussed are not constructive, whereas later sections include i.i.d., subsampling, greedy, volume, and hierarchical Christoffel sampling designs.
  • Results: The paper reports several sharp bounds on sampling numbers, meaning examples show that the general bounds cannot be substantially improved.These results are collected among six main results in Appendix A.1.

2. An easy example and some basic concepts

The section formalizes function approximation from finite function evaluations and develops optimality notions for reconstruction and sampling. In the Lipschitz example, equidistant sampling and feasible interpolation methods achieve sharp or near-sharp guarantees.

  • Basic concepts: A model class specifies admissible functions, while measurement and reconstruction maps form a sampling algorithm whose error is measured in a target norm.The framework allows approximation in a space larger than the model class, such as L2.
  • Basic concepts: For fixed sampling points, the radius of information is the smallest worst-case error achievable by any reconstruction using those function values.Exact optimal reconstruction maps may be difficult to obtain, so constant- or logarithmic-factor near-optimality is often accepted.
  • Lipschitz example: Any interpolatory reconstruction for the Lipschitz class is instance and worst-case optimal up to a factor of two.The factor-two guarantee follows from the triangle inequality, whereas exact instance optimality need not hold for the spline reconstruction.
  • Lipschitz example: For the Lipschitz example, the distance function to the sampling set is a fooling function, and zero data are the least informative observations.No algorithm using the same sampling points can distinguish the fooling function from its negative.
  • Lipschitz example: The worst-case error is bounded by 1/(4n) ≤ g_n(F_Lip,Lp) ≤ 1/(2n), and equidistant sampling points are optimal in the periodic example.The optimal reconstruction and sampling points are described as feasible for computer implementation.
  • Generalizations: For Sobolev-type classes, the minimal worst-case error has order n^(-s+(1/q−1/p)+), with point-set optimality characterized by fill distance when p≥q.A fill distance of order O(1/n) means that no hole in the sampling set exceeds that order; for p<q, fill distance alone is insufficient.

3. Least squares and best linear approximation

The section develops sampling algorithms whose errors can be controlled by best approximation, while showing how oversampling, model assumptions, and function-space geometry affect achievable bounds. It also identifies settings where optimal rates are attainable and where direct comparison with best L2-approximation is impossible.

  • Least squares and best linear approximation: Deterministic sampling can be fundamentally unstable relative to best L2-approximation because changing a function at sample points leaves its L2 norm unchanged but can drastically alter the algorithm’s output.This obstruction persists even for continuous or smooth functions.
  • Bounds by best uniform approximation: For uniform approximation, n sampling points can achieve an error factor of at most n+1+ε relative to best approximation, and the factor n+1 is optimal in general.The corresponding result is expressed through an interpolatory algorithm and the Lebesgue constant.
  • Oversampling: Oversampling improves the uniform-norm factor from order n to order √m, while Lp bounds contain the sharp factor n^(1/2−1/p)+.With n=2m samples, the factor n+1 is reduced to 4√n; improving √m to a constant generally requires exponentially many samples.
  • Construction and limitations: Constructive sampling points can achieve optimal rates in polynomial time, although explicit formulas or simpler geometric constructions may still be unknown.The section also notes that finding the relevant optimal measure is usually problematic.
  • Bounds by best L2-approximation: For nested approximation spaces, 4m weighted samples and weights can yield optimal convergence rates across entire families of function classes without knowing the smoothness rate α.The points and weights depend on the approximation spaces, error measure, and ε, but not on α.
  • Hilbert and non-Hilbert settings: The framework extends from RKHS results to general model classes and error norms through embeddings and estimates, but direct comparison with best L2-approximation remains generally unavailable.Some non-Hilbert classes can have sampling numbers with no decay even when their linear widths decay logarithmically.

4. Construction of sampling points

This section develops constructive procedures for sampling points and weights that support discretization inequalities and least-squares approximation. The approach generalizes earlier results to different spaces, norms, infinite-dimensional settings, and equal-weight sampling, while exposing computational assumptions and acceptance rates.

  • The construction targets discretization inequalities needed for least-squares error bounds and supplies points and weights behind the theoretical results.The section presents numerical procedures for obtaining these points and weights.
  • The construction generalizes two-sided L2 discretization to different lower and upper spaces, possibly infinite-dimensional upper spaces, norms beyond L2, and equal weights.Equal weights enable unweighted least-squares methods, while dimension-independent bounds address infinite-dimensional spaces.
  • Theorem 4.2 constructs positive-weight sampling points for an m-dimensional function space embedded in an L2 space, with bounds valid for every n≥m.The points and weights can be generated by Algorithm 1 using orthonormal bases and an arbitrary oracle.
  • Algorithm 1 selects points sequentially, accepting oracle-proposed candidates according to spectral tests on Gram matrices and outputting positive weights.The procedure repeatedly updates matrix quantities, tests a proposed point, and returns the accepted points and weights.
  • A finite basis and an oracle that proposes accepted points at a decent rate are required for numerical feasibility, although truncated bases can handle infinite bases.Christoffel-density proposals are accepted with probability at least 0.06/m^2 when n≥2m, or order 1/m after a slight modification; testing then requires an expected O(mn) random points.
  • Theorem 4.4 provides a constructive weighted least-squares result whose polynomial rate becomes α for p≤2, yielding optimal L2 rates for sufficiently smooth functions.For p>2, the quality of the rate depends on the basis and its parameter θ; the construction assumes sampling from the underlying measure and computable basis functions.

5. Optimal sampling and nonlinear approximation

This section studies how sampling algorithms can approach nonlinear approximation benchmarks, including sparse approximation, entropy numbers, and Hilbert numbers. It establishes upper bounds, sharpness results, and scope conditions for these comparisons.

  • Section scope: Sampling algorithms can be compared with best sparse approximation, metric entropy, and other nonlinear benchmarks such as manifold approximation.These benchmarks may be substantially smaller than approximation errors from linear spaces.
  • 5.1. Bounds by best sparse approximation: For an m-sparse target in an N-dimensional space, the sampling question is whether comparable accuracy is possible and how many samples are required.The setting uses m-sparse functions in a much larger space V_N, where N≫m.
  • 5.1. Bounds by best sparse approximation: The sparse-approximation guarantee requires restricted-isometry-type discretization, whose measurement-matrix constructions are usually established probabilistically.The stronger discretization condition costs only logarithmic factors in m and N, enabling treatment of N≫m.
  • 5.1. Bounds by best sparse approximation: O(m log^2 m log N) samples suffice to approach the error of best m-sparse uniform approximation in an N-dimensional space.The result applies when V_N is spanned by a bounded orthonormal basis.
  • 5.2. Bounds by entropy numbers: Entropy-number bounds yield convergence for every finite p under weak assumptions, but cannot improve beyond n^-1/(2p) and give no rate for p=∞.For L1-approximation, the sampling-number decay is at least the entropy-number decay when the entropy exponent s lies in (0,1/2).
  • 5.3. Bounds by other benchmarks: The section also bounds sampling numbers using Hilbert numbers and other s-number benchmarks, while noting that indirect conversions among these quantities are weaker than direct bounds.Hilbert numbers are identified as the smallest s-numbers considered in this framework.

6. Almost-optimality of i.i.d. sampling

The section shows when i.i.d. sampling approaches optimal sampling: typically with O(m log m) samples, while some settings need only O(m), and others require logarithmic oversampling.

  • The easy example revisited: i.i.d. sampling is optimal up to constants for L_p-approximation with p<∞ and up to a logarithmic factor for L_∞-approximation of Lipschitz functions.This comparison is made in expectation for uniformly distributed points.
  • Sampling-density construction: The optimal sampling density can be simple for trigonometric monomials or spherical harmonics but complicated and often intractable in other settings.Determining the relevant characteristic may itself require difficult spectral information.
  • General Hilbert-space results: O(m log m) i.i.d. samples with a suitable density achieve error of optimal order σ_m with high probability in broad Hilbert-space settings.The weighted least squares estimator uses the sampling density and inverse-density weights.
  • General Hilbert-space results: The high-probability guarantee can hold uniformly for all functions in the approximation class, allowing one random sample to serve every function.This follows from the order of quantifiers in the theorem’s statement.
  • Examples: For trigonometric polynomials and spherical harmonics, O(m log m) samples give the optimal approximation order with dimension-independent hidden constants.For polynomial spaces associated with lower sets, the corresponding bound becomes O(m^2 log m).
  • When oversampling is necessary: The logarithmic oversampling is necessary in many examples but not in all settings, including certain L_2-approximation problems on RKHSs and approximation classes E_α.For Sobolev-type results, the need for oversampling depends on the relation between the approximation and error norms.

7. Randomized sampling algorithms

The section develops randomized sampling algorithms, including weighted least squares and multilevel Monte Carlo methods, and compares their approximation guarantees, assumptions, and computational costs.

  • Randomized algorithms: Randomized algorithms draw new random sampling points for each input function, unlike methods that fix one sample set for the whole input class.This distinction separates Monte Carlo algorithms from earlier analyses of randomly generated but fixed sampling sets.
  • Limits of randomization: For Lipschitz-function approximation, the Monte Carlo approach is not superior to deterministic approximation, and general lower bounds limit its possible gain.Equidistant points are optimal for the cited L_p problem.
  • Optimal random samples: Randomized algorithms can remove deterministic tail and decay assumptions, including the condition α>1/2 on polynomial Kolmogorov-number decay.The resulting bounds apply to every individual n and to broad classes of square-integrable functions.
  • Randomized least squares: Theorem 7.6 uses n=10m log(4m) Christoffel samples, while later constructions achieve comparable guarantees with 4(m−1) samples under an oversampling factor r=4.The latter points and weights are generated by a greedy sampling strategy.
  • Alternative sampling designs: Volume sampling matches the individual Christoffel-point distributions while avoiding duplicate-point clustering, but its proven error guarantees remain worse than those of i.i.d. Christoffel sampling.The proposed advantage of filling data-set holes more quickly remains unresolved.
  • Multilevel Monte Carlo: Multilevel Monte Carlo reaches optimal error rates with constant oversampling and lower runtime, but requires a hierarchy of good approximation spaces.Its runtime is O(mt+m^2), compared with O(m^4t) for the cited optimal weighted least squares construction.
  • Extensions: The L_2 error guarantees from weighted least squares and multilevel methods can be transferred to L_p and other norms because both return approximations from V_m.The paper omits the transfer details.

8. The curse of dimensionality

High-dimensional approximation can remain intractable despite smoothness, while randomization, structural assumptions, and suitable width conditions can yield polynomial or strong polynomial tractability. The outcome depends strongly on the approximation norm and precise model class.

  • Lipschitz-function approximation suffers from the curse of dimensionality for every 1 ≤ p ≤ ∞.
  • Classical smoothness assumptions generally do not ensure high-dimensional tractability, although some specially structured infinitely smooth classes are quasi-polynomially tractable.
  • Uniform approximation can remain cursed even for infinitely smooth functions and arbitrary adaptive linear measurements, whereas randomization often helps for L2-approximation.
  • Randomization removes the curse of dimensionality for the discussed mixed-smoothness example, requiring O(d^q) random samples for any fixed error ε>0.
  • Uniform summability conditions on width sequences provide sufficient criteria for polynomial or strong polynomial tractability of sampling recovery.
  • Structural assumptions such as partial separability, variable importance, or symmetry can improve tractability in high dimensions.

9. A general framework for optimal algorithms

The paper places sampling recovery within a general framework of optimal algorithms that compares measurement classes, reconstruction rules, and adaptive or randomized information. This framework connects minimal errors with approximation benchmarks and s-numbers, yielding bounds and equivalences across settings.

  • Optimal algorithms compute an approximation of a solution map S(f) using admissible measurements and a reconstruction map.
  • Adaptivity can improve performance substantially for some problems, but its benefit depends on the problem and admissible information.
  • The framework compares deterministic, randomized, adaptive, non-adaptive, standard, linear, and arbitrary measurement classes.
  • For linear problems, adaptive methods reduce worst-case error by at most a factor of two.
  • Axiomatic s-number properties characterize extremal quantities and yield inequalities relating different minimal errors and approximation benchmarks.
  • Gelfand numbers and widths characterize minimal worst-case error for non-adaptive deterministic algorithms using arbitrary linear measurements up to a factor of two.

10. Comparison of different types of measurements

The survey compares sampling with broader measurement models, showing that adaptivity, randomization, and general linear information usually provide limited gains, while adaptive continuous measurements can yield an exponential speed-up in theory.

  • General comparison: For convex model classes, adaptivity, randomization, and related features change polynomial convergence rates by at most a constant, though exact constants may remain unknown.The maximal gain for adaptivity and randomization is bounded above by 3/2, while no example with gain larger than 1 is known.
  • Function values versus other measurements: For L2- and uniform approximation, arbitrary linear measurements and randomized or adaptive variants provide only limited gains over non-adaptive sampling algorithms.The restriction to non-adaptive sampling can cost at most an order of convergence 1/2, and this bound is sharp for some model classes.
  • Continuous measurements: Adaptive continuous measurements can approximate an m-dimensional vector with arbitrary precision using only O(log m) measurements, producing an exponential theoretical speed-up.The construction uses a coloring of the model class together with bisection; embeddings yield polynomial gains of order one or one half in related examples.
  • Linear measurements: Non-adaptive deterministic sampling is optimal up to a rate loss of at most 1/2 among adaptive randomized algorithms using general linear information.The comparison also includes non-adaptive continuous measurements, whose rates coincide with the corresponding benchmark rates under the stated conditions.
  • Function values versus other measurements: Linear sampling algorithms are optimal up to constants and oversampling among deterministic algorithms using linear information for bounded reproducing kernel Hilbert spaces.Whether the boundedness assumption is necessary for this conclusion remains open.
  • Super-polynomial convergence: For smooth classes with super-polynomial minimal-error decay, randomization, adaptivity, and general linear information do not improve information complexity by more than a constant factor.The survey notes that this conclusion is not known for other target spaces such as Lp when p is neither 2 nor infinity.

A. Collection of some bounds

This appendix collects general bounds and notation for sampling numbers, emphasizing asymptotic comparisons and selected sharp results.

  • Scope: The appendix summarizes general sampling-number bounds from earlier sections and known widths and sampling numbers for univariate Sobolev spaces.It first lists general bounds, then presents results for the running Sobolev examples.
  • Notation: The notation g_n(F,Y) ≍ n^s means that g_n is bounded above and below by positive constant multiples of n^s for sufficiently large n.The constants may depend on F, Y, and s, but not on n.

A.1. General bounds on sampling numbers

The appendix states general sampling-number results under compactness, convexity, measure, and approximation-space assumptions, including selected sharp bounds for Banach-space unit balls.

  • Assumptions: The stated framework assumes compact D, compact convex F contained in C(D), a finite Borel measure μ, and 1 ≤ p ≤ ∞.The appendix records only results known to be sharp for some choices of F and Y.
  • Approximation quantities: The bounds also use nested L2 subspaces V_k of dimension k and the quantity Λ_m measuring the largest Y-norm on L2-unit vectors in V_m.The approximation error d(F,V_k)_2 is defined by the worst-case L2 distance from F to V_k.
  • General bounds: For the unit ball of a Banach space, Theorem 5.15 provides a sampling-number bound for every s > 1.The supplied passage identifies the theorem and its condition but does not include the displayed bound itself.

A.2. Widths of Sobolev spaces 

This appendix organizes widths and sampling numbers for univariate Sobolev spaces, with piecewise formulas by exponent ranges and cautions about exceptional smoothness.

  • Compared quantities: The table compares approximation, Bernstein, Gelfand, Kolmogorov, manifold, entropy, and sampling numbers, with L∞ identified as approximation into B([0,1]).It also defines s_n(X,Y) as the n-th s-number of the identity operator from X to Y.
  • Piecewise bounds: For s ∈ N \ {1}, Theorem A.1 gives piecewise power laws depending on the relative positions of p, q, 2, and q′.The listed exponents include n^-s, n^(-s+1/q-1/p), n^(-s+1/q-1/2), and n^(-s+1/2-1/p) in the stated parameter regimes.
  • References: The appendix points to established references for the different width and sampling-number sequences, including Novak and Triebel for sampling numbers.The cited literature covers approximation, Bernstein, Gelfand, Kolmogorov, manifold, entropy, and sampling numbers.
  • Caveats: Some formulas in the table are not correct at smoothness s = 1, and fractional-smoothness results require separate references.The appendix cites later work identifying an exception for Kolmogorov numbers and directs readers to additional sources for fractional smoothness.

Index

The index covers approximation, sampling, information, reconstruction, complexity, and related mathematical frameworks and techniques.

  • Approximation and reconstruction entries include best m-term approximation, best approximation, hyperinterpolation, and reconstruction.
  • Sampling and measurement entries include leverage score sampling, D-optimal designs, compressive sensing, and measurement maps.
  • Analytical settings and tools include Hilbert spaces, reproducing kernel Hilbert spaces, restricted isometry, bounded orthonormal systems, and universal discretization.
  • Additional indexed topics include noise, normal equations, probabilistic methods, pointwise convergence, and expected reconstruction.
  • The index connects information-based complexity with information, complexity, the radius of information, entropy, covering numbers, and the curse of dimensionality.
Loading 2602.02066v2…