Greedy multiscale kernel algorithms
Abstract
Multiscale kernel approximation and greedy kernel algorithms are two established tools for scattered data approximation. We combine them into greedy multiscale kernel algorithms, in which every level of a multiscale residual correction is constructed by a greedy kernel algorithm. For the multiscale f-greedy algorithm we prove convergence rates in the number of selected centres which coincide (up to an arbitrarily small loss in the exponent) with the rates of the single-scale f-greedy algorithm. The gain of the multiscale construction is in the stability, and we make this precise by a two-sided estimate for the condition number of kernel matrices with rescaled kernels. The lower bound shows that any single-scale method, and in particular the f-greedy algorithm, pays for its convergence rate with condition numbers growing at least like a power of the number of centres. In contrast, the multiscale scaling of the kernel keeps this lower bound fixed on every level without changing the rate. The upper bound identifies the separation of the centres at the scale of the kernel as the quantity to control. We give the operation counts of all the methods considered and compare the greedy multiscale algorithms numerically with single-scale greedy and classical multiscale methods, in terms of error, time and conditioning.
Related
- High-order smoothness and high-order collocation approximation for Volterra integral equation with multiscale and nonlinear exponent kernel
- Compressed Multiscale Kernel Collocation and Physics-Informed Kernel Learning for Elliptic BVPs
- Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms
- The Frame Kernel Method for Multiscale Operator Learning
- On the Sequentially Semiseparable Structure of SDE-Induced Kernels and Efficient Algorithms for Kernel-Based Estimation Problems
BibTeX
@misc{avesani2026greedy,
title = {{Greedy multiscale kernel algorithms}},
author = {Sara Avesani and Armin Iske and Michael Multerer and Tizian Wenzel},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21615},
eprint = {2610.21615},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21615},
}
RIS
TY - UNPB
TI - Greedy multiscale kernel algorithms
AU - Sara Avesani
AU - Armin Iske
AU - Michael Multerer
AU - Tizian Wenzel
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21615
UR - https://arxiv.org/abs/2610.21615
AB - Multiscale kernel approximation and greedy kernel algorithms are two established tools for scattered data approximation. We combine them into greedy multiscale kernel algorithms, in which every level of a multiscale residual correction is constructed by a greedy kernel algorithm. For the multiscale f-greedy algorithm we prove convergence rates in the number of selected centres which coincide (up to an arbitrarily small loss in the exponent) with the rates of the single-scale f-greedy algorithm. The gain of the multiscale construction is in the stability, and we make this precise by a two-sided estimate for the condition number of kernel matrices with rescaled kernels. The lower bound shows that any single-scale method, and in particular the f-greedy algorithm, pays for its convergence rate with condition numbers growing at least like a power of the number of centres. In contrast, the multiscale scaling of the kernel keeps this lower bound fixed on every level without changing the rate. The upper bound identifies the separation of the centres at the scale of the kernel as the quantity to control. We give the operation counts of all the methods considered and compare the greedy multiscale algorithms numerically with single-scale greedy and classical multiscale methods, in terms of error, time and conditioning.
ER -