Greedy adaptive local recovery of functions in Sobolev spaces

Abstract There are many ways to upsample functions from multivariate scattered data locally, using only a few neighbouring data points of the evaluation point. The position and number of the actually used data points is not trivial, and many cases like Moving Least Squares require point selections that guarantee local recovery of polynomials up to a specified order. This paper suggests a kernel-based greedy local algorithm for point selection that has no such constraints. It realizes the optimal $$L_\infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>∞</mml:mi> </mml:msub> </mml:math> convergence rates in Sobolev spaces using the minimal number of points necessary for that purpose. On the downside, it does not care for smoothness, relying on fast $$L_\infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>L</mml:mi> <mml:mi>∞</mml:mi> </mml:msub> </mml:math> convergence to a smooth function. The algorithm ignores near-duplicate points automatically and works for quite irregularly distributed point sets by proper selection of points. Its computational complexity is constant for each evaluation point, being dependent only on smoothness and scale parameters of the kernel. Various numerical examples are provided. As a byproduct, it turns out that the well-known instability of global kernel-based interpolation in the standard basis of kernel translates arises already locally, independent of global kernel matrices and small separation distances.