Greedy multiscale kernel algorithms

1 Introduction

• Greedy methods select data sites adaptively, whereas multiscale methods approximate across several resolutions by iteratively correcting residuals.The paper situates these as established approaches to efficient kernel approximation from large data sets.Source: §1 · pp. 1–2
• Greedy multiscale algorithms build every level of residual correction with a greedy kernel algorithm, combining adaptive centre selection with a hierarchy of resolutions.P-greedy levels connect the classical quasi-uniform multiscale construction to this framework, whereas target-dependent rules such as f-greedy yield adaptive approximations.Source: §1 · p. 2
• The multiscale f-greedy convergence rate matches the single-scale f-greedy rate up to an arbitrarily small loss in the exponent.The paper also proves a two-sided condition-number estimate for kernel matrices with rescaled kernels.Source: §1 · p. 2
• The paper combines a multiscale contraction lemma with a stability estimate in a theorem where residual reduction determines convergence and scale-relative centre separation determines stability.The theorem recovers the classical multiscale method and multiscale f-greedy as special cases.Source: §1 · p. 2
• The authors give operation counts and compare greedy multiscale methods with single-scale f- and P-greedy algorithms and classical multiscale methods using compactly supported kernels.The numerical comparison considers error, time, and conditioning.Source: §1 · p. 2

2.1 Kernels, native spaces and Sobolev spaces

• The analysis uses translation-invariant rescaled kernels on a bounded Lipschitz domain, with assumptions that identify the native space with a Sobolev space.The paper notes that the assumptions hold for Matérn and compactly supported Wendland kernels.Source: §2.1 · pp. 2–3
• Kernel interpolation is defined as interpolation in the span of kernel translates, and its interpolant is the orthogonal projection in the native space.The native-space norm on the domain is a quotient norm, and interpolation errors and interpolant norms obey the stated norm bounds.Source: §2.1 · p. 3

2.2 Multiscale kernel approximation

• Multiscale approximation successively interpolates each prior residual on finer point sets using kernels whose scales are proportional to the fill distances.Under the stated geometric decrease in fill distances and scale conditions, the L2 error decreases geometrically when α < 1; the construction does not improve approximation order, while scale-to-separation control supports conditioning.Source: §2.2 · p. 4

2.3 Greedy kernel algorithms

• Greedy kernel algorithms add interpolation points by maximizing an error indicator, and f-greedy and P-greedy are unified by β-greedy; in L∞(Ω), f-greedy’s rate is better by exactly factor m^1/2, independently of τ and d.Source: §2.3 · pp. 4–5

3.1 The algorithm

• Each level greedily selects centres for approximating the previous level’s residual, then adds that correction to the approximation.The procedure uses a kernel whose scale decreases across levels; in practice, maxima are taken over a finite candidate set.Source: §3.1 · p. 5

3.2 Relation to the classical multiscale method

• P-greedy can recover the quasi-uniform levels of the classical method, while target-dependent rules such as f-greedy adapt centres to the residual.Nested level sets are not required for the analysis.Source: §3.2 · p. 6

3.3 Computational cost

• Greedy selection costs the same order as single-scale selection, whereas the classical multiscale method has lower level costs; final evaluation costs depend on kernel support.For globally supported kernels, greedy offline time grows like N_n^2; compact support allows evaluation in O(N′n).Source: §3.3 · p. 6

4.1 The f-greedy algorithm with rescaled kernels

• The rescaled-kernel f-greedy analysis tracks constants, and its power-function estimates yield a convergence bound under the stated sufficiently smooth boundary assumption.The boundary smoothness required is that for the entropy-number bounds of [23].Source: §4.1 · pp. 7–8

4.2 The multiscale contraction lemma

• A level contracts when its residual is small in L2 relative to its input’s RKHS norm; the scale-change cost µ^τ is independent of how the level was built.Iterating the contraction lemma yields residual contraction across levels.Source: §4.2 · p. 9

4.3 Error bounds for the classical multiscale method

• Classical multiscale error bounds extend from L2 to Lp for 2 ≤ p ≤ ∞, with rates matching single-scale interpolation up to an arbitrarily small exponent loss.The bounds are expressed using the finest level’s fill distance.Source: §4.3 · p. 10

4.4 Error bounds for multiscale f-greedy

• The multiscale f-greedy algorithm converges in L∞ at rate N^-(1−ε)τ/d, matching the single-scale f-greedy rate up to loss ε; its advantage over classical multiscale is a factor N^1/2.In L2, both methods have order τ/d, so there is no corresponding gain.Source: §4.4 · p. 11

4.5 Stability of the level matrices and the trade-off with convergence

• The conditioning estimate has an upper bound controlled by δ/qX and a lower bound that grows with the number of centres at fixed scale, regardless of their distribution.For quasi-uniform sets, the bounds agree up to constants.Source: §4.5 · pp. 12–13
• The f-greedy error bound cgχ^-τ and condition-number lower bound c0χ^(2τ) imply that guaranteed error ϵ requires κ2(Kδ,Xn) ≥ c0(cg/ϵ)^2.Thus the guaranteed error reduction is no better than cg(c0/κ)^(1/2), regardless of τ, d, or centre positions; this concerns the guarantee, not the actual error.Source: §4.5 · p. 14

4.6 A general stability-convergence principle

• Theorem 4.13 gives convergence when level reductions βℓ are uniformly bounded, stability bounds based on level matrices and centre separation, and a rate under additional reduction and centre-count growth assumptions.The L∞ convergence bound uses the final-level reduction γn; the rate result also holds in L∞ when γn ≤ Cγμ^τ.Source: §4.6 · p. 14
• At a fixed single scale, χ grows as centres are added, so the condition number grows at least like c0δ^(2τ)n^(2τ/d) while the f-greedy error bound decays.Both changes arise from increasing χ = δn^(1/d).Source: §4.6 · p. 15
• For quasi-uniform classical multiscale levels with δℓ = νhZℓ,Ω, both sides of the stability bound remain constant, and the method recovers L2 and L∞ orders τ/d and τ/d − 1/2.The rates follow from the sampling inequality and Theorem 4.13(iii).Source: §4.6 · p. 15
• For multiscale f-greedy levels with δℓMℓ^(1/d) = ν, the condition-number lower bound stays fixed and the L∞ guarantee avoids a factor M_n^(1/2), but clustering can still worsen the upper bound.Rejecting candidates within 2cqδℓ of existing centres prevents that clustering and controls conditioning.Source: §4.6 · p. 15

5.1 Experimental setting

• The experiments use 100,000 uniform candidates on the unit square and the 300,000-point Bunny cloud; multiscale levels are nested and generated by greedy selection.The finest level determines the reported multiscale centre count.Source: §5.1 · p. 16

5.2 Multiscale f-greedy approximation on the unit square

• For multiscale f-greedy with exponential kernel, error decreases more rapidly after level 4; δℓ≥0.1118 through level 4 exceeds all localized features; from level 5, it becomes comparable, enabling their resolution.Condition numbers grow by two orders of magnitude over the six levels.Source: §5.2 · p. 17

5.3 Multiscale f-greedy approximation on a surface

• On the Bunny, coarse levels distribute centres across the surface, while finer levels concentrate new centres around the Gaussian bump and mostly along the corner.The example applies the method to a manifold, although the theoretical results are formulated for Euclidean domains.Source: §5.3 · pp. 17–19, Figure 4 · p. 19

5.4 Comparison of the methods

• The multiscale f-greedy reaches ε∞=1.48 · 10^-4 versus 8.27 · 10^-3 for multiscale P-greedy, while its condition numbers remain three orders below single-scale.The conditioning-controlled variant keeps condition numbers below 10^2 on every level.Source: §5.4 · pp. 20, 22, Table 6 · p. 20, Figure 5 · p. 21
• Greedy offline time grows like Nn^2 and is similar for single-scale and multiscale runs; classical multiscale time is linear in centres and has the smallest online cost.The CC P-greedy variant takes twice as long because its certificate requires residual evaluation on the candidates at every step.Source: §5.4 · p. 22

• The multiscale f-greedy algorithm retains the single-scale convergence rate and selection cost while changing stability.Source: §6 · p. 22
• Keeping χ fixed at each level avoids condition numbers that grow with centre count, while each level gives only a bounded error reduction.Theorem 4.13 applies to any construction of the levels; level reduction determines convergence, and centre separation determines stability.Source: §6 · pp. 22, 25
• The numerical experiments confirm the proposed picture in error, time, and conditioning.The figures plot condition numbers, ε∞ and ε2 decay, and offline time; Table 8 reports final-level method statistics including the largest condition number across levels.Source: Figure 7 · p. 23, Figure 8 · p. 24, Figure 9 · p. 24
• The multiscale f-greedy analysis assumes the target lies in the native space; extending it beyond that setting depends on an open single-scale result.An experiment with a kink suggests good performance outside the native space, but does not resolve the analysis.Source: §6 · p. 25
• Evaluating selection criteria at every candidate on every level costs O(NM 2 n); restricting candidates to adaptive samplet-tree cells is proposed to reduce this to linear in N, up to logarithmic factors.Source: §6 · p. 25