Source-linked AI summary
Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm
Sebastian Neumayer, Kateryna Pozharska, Tino Ullrich
TL;DR
The paper studies how accurately functions in RKHSs can be recovered from finite point samples in the uniform norm, addressing the gap between sampling and Gelfand widths. It uses kernel-translate dictionaries and P-greedy sampling designs to establish direct comparisons, including under decay assumptions and through oversampling or square-root bounds.
Problem
Uniform-norm recovery from sample information can lose performance relative to unrestricted information, motivating comparisons between sampling widths and Gelfand widths.
Method
The paper represents widths through kernel translates and uses nested kernel-interpolation designs at weak P-greedy points to transfer reduced-basis comparisons to sampling recovery.
Results
Under polynomial decay, Gelfand-width decay transfers directly to sampling widths; without decay assumptions, direct comparisons follow through logarithmic oversampling or taking square roots, with constructive alternatives for exponential decay.
Takeaways & Limitations
The results provide sampling designs and width comparisons that remove the known square-root gap in bounded-kernel RKHSs without measure or Christoffel-type conditions.
Takeaways & Limitations
The sharpness discussion does not extend to non-Hilbert Besov balls, because the RKHS-based proposition does not apply there.
Abstract
from arXiv · showhide
We study optimal sampling recovery in reproducing kernel Hilbert spaces (RKHS) in the uniform norm. For every RKHS with bounded kernel, we establish new comparisons between linear sampling widths and Gelfand widths that overcome the known square-root gap, without requiring a measure or a Christoffel-type condition. Our bounds rely on nested sampling designs obtained by kernel interpolation at (weak) P-greedy points. Under additional (polynomial) decay assumptions the decay rate of the Gelfand widths directly transfers to the sampling widths. With either a logarithmic oversampling or passing to the square root of the Gelfand widths we obtain a direct comparison (requiring no decay assumption) between them. This is particularly effective for super-polynomial decay, such as in Paley-Wiener spaces. Our results follow from representations of both widths in terms of kernel translates and yield, in the opposite direction, a new existence result for a sharp reduced basis selection. Numerical experiments for Legendre, mixed-Sobolev, and Paley-Wiener kernels illustrate our findings.
1 Introduction
The paper studies uniform-norm recovery in bounded-kernel RKHSs, comparing arbitrary linear information with point-sample information. It develops a kernel-translate and greedy-design framework to relate sampling widths to Gelfand and reduced-basis widths.
- Problem: Uniform-norm recovery asks how accurately functions in an RKHS can be reconstructed from finitely many measurements, especially point evaluations.The comparison concerns arbitrary linear information versus sample information.
- Problem: Gelfand widths benchmark optimal recovery with arbitrary linear information, while linear sampling widths measure recovery using point samples.Gelfand widths are lower bounds for sampling widths, so the converse comparison quantifies the cost of restricting measurements to samples.
- Problem: The central questions are whether Gelfand-width decay transfers to sampling widths for every bounded-kernel RKHS and whether the known √n factor can be removed.The questions target unit balls of RKHSs with bounded kernels.
- Approach: The analysis uses a dictionary of kernel translates and represents sampling widths through kernel power functions and Gelfand widths through Kolmogorov widths of the translate set.This converts sampling-versus-Gelfand comparisons into greedy-versus-Kolmogorov width comparisons.
- Contributions: Greedy reduced-basis selection supplies nested sampling designs, while the resulting theorems address decay transfer, oversampling, and a sharp reduced-basis subset-selection existence result.The introduction identifies Theorem 2.1, Theorem 2.5, and the reversed transfer as the main outcomes.
2 Main results
The paper develops comparisons between sampling and Gelfand widths for bounded-kernel RKHSs, transferring decay rates under assumptions and providing constructive alternatives without decay assumptions.
- Theorem 2.1: Theorem 2.1 gives a Carl-type comparison transferring Gelfand-width decay to linear sampling widths under weighted decay conditions.The framework uses non-decreasing functions satisfying a regular-variation-type condition; polynomial and logarithmic examples are included.
- Corollary 2.3: Polynomial Gelfand-width decay transfers directly to sampling widths through Corollary 2.3.The result covers bounds of the form cn(BHK)∞≤C0(1+n)^−α and more general polynomial-logarithmic rates.
- Theorem 2.4: Theorem 2.4 removes the decay assumption by comparing sampling widths with the square root of Gelfand widths.For exponential decay, the exponent order m^α is preserved, although the exponential constant is reduced by 2^(1+α).
- Theorem 2.4: The results are especially relevant to super-polynomial decay, including Paley–Wiener spaces, where the constructive square-root comparison applies.The comparison is constructive and requires no prescribed decay, unlike the sharper nonconstructive exponential estimate.
- Theorem 2.5: Theorem 2.5 provides a constructive direct comparison using decay-dependent logarithmic oversampling.For cn ≍ n^−α it uses m ≍ n log n, while for cn ≍ exp(−θn^α) it uses m ≍ n^(1+α).
- Theorem 2.6: The paper also reverses the transference principle, proving an existence result for sharp reduced-basis subset selection.Theorem 2.6 connects subset widths with Kolmogorov widths and establishes an absolute-constant bound.
3 The kernel-translates dictionary
The kernel-translates dictionary represents both sampling and Gelfand widths through approximation of kernel sections, enabling a transference principle based on interpolation and reduced-basis geometry.
- Kernel-translates dictionary: The kernel-translate set K={a_x:x∈D} with a_x=K(·,x) converts function-space width questions into approximation of kernel sections in HK.The key identity is cn(BHK)∞=dn(K)HK.
- Kernel interpolation: For a finite sampling set P, VP is the span of its kernel translates, and the power function measures the residual distance from these spans.Orthogonal projection onto VP is the kernel-interpolation operator.
- Kernel interpolation: Kernel interpolation is linear in the samples, interpolates them, and has minimal HK norm among functions matching those samples.The interpolant is obtained from the Gram matrix and its Moore–Penrose inverse.
- Sampling widths: The sampling-width upper bound follows by using kernel interpolation at any set of at most m points.Orthogonality of the interpolation residual yields a bound through the power function.
- Recovery lower bound: A fooling argument gives the matching lower bound for arbitrary recovery algorithms by using h and −h with identical samples.The resulting identity is gm(BHK)∞≥τm(K)HK.
- Transference principle: Proposition 3.3 identifies Gelfand widths of the RKHS unit ball with Kolmogorov widths of the kernel-translate set.Together with the sampling representation, this forms the paper’s transference principle.
4 Greedy sampling designs, Gelfand widths and reduced bases
The section derives sampling guarantees from weak greedy selection in Hilbert spaces, identifying kernel interpolation at selected translates with P-greedy designs. It also establishes sharpness boundaries and constructive, nested-design consequences for the resulting width comparisons.
- Greedy selection: The weak greedy algorithm selects elements of a Hilbert-space subset recursively by maximizing distance from the span of previously selected elements.Approximate maximization is allowed for γ < 1; γ = 1 requires the supremum to be attained.
- Greedy selection: Kernel normalization identifies each selected greedy element with a kernel translate and converts the distance criterion into the power function of the selected sampling nodes.For selected nodes Pj, σj = ∥PowPj∥∞/R, so the greedy construction becomes weak P-greedy point selection followed by kernel interpolation.
- Nested designs: Nested designs add at most one node per budget, allowing previous samples to be reused and interpolants to be updated incrementally.This contrasts with guarantees based on separately drawn or subsampled designs for each budget.
- Reduced-basis connection: The proof framework also transfers a subspace-width inequality from a dictionary to its induced function class through Hahn–Banach extensions.Taking the infimum over subspaces yields dm(F)B(A) ≤ dm(A)X.
- Sharpness: The factor √m in the comparison cannot generally be replaced by o(√m), even with constant oversampling.The sharpness construction uses explicit low-coherence matrices and shows the obstruction through a sequence of finite compact sets.
5 Examples and numerical illustration
The numerical section compares P-greedy sampling estimates with lower Gelfand-width estimates for Legendre, mixed-Sobolev, and Paley–Wiener kernels, while documenting design behavior and computational limitations.
- Experimental setup: For the unit ball of a bounded-kernel RKHS, the experiments compare linear sampling widths with Gelfand widths using P-greedy kernel interpolation.The computed sampling estimate is the maximum kernel power function over the candidate grid for the selected P-greedy set.
- Legendre kernel: Legendre kernels with s = 2, 3 use 20 000 Chebyshev candidate points, and their estimates are compared with computed lower width estimates.For s = 3 and large m, numerical precision is reached and the selected design clusters toward the endpoints.
- Periodic mixed-Sobolev kernel: Mixed-Sobolev experiments use d ∈ {2, 3} and m ∈ {1, 2, 3} except (3, 3), with the rate n^-(m−1/2)(log n)^((d−1)m) shown as an asymptotic guide.Across the illustrated cases, P-greedy estimates remain bounded relative to the computed Gelfand-width estimates.
- Periodic mixed-Sobolev kernel: For the mixed-Sobolev kernel, P-greedy grids contain 120 000 points in d = 2 and 80 000 points in d = 3.The figures show the reported behavior with P-greedy points, while reachable indices have not fully developed the logarithmic factor asymptotically.
- Band-limited Paley–Wiener kernel: For Paley–Wiener kernels, polynomially weighted comparisons do not reproduce the super-exponential cliff because the supremum is governed by the plateau near Neff.The experiment therefore compares the observations with Theorem 2.4 rather than claiming to illustrate that theorem directly.
- Band-limited Paley–Wiener kernel: Paley–Wiener estimates stay approximately flat up to Neff and then decay rapidly, with sampling and width estimates differing by up to about one decade near the cliff.The experiments use Neff ∈ {20, 40, 80}; after n ≈ Neff, computed values approach the double-precision floor.