Error saturation in Gaussian radial basis functions on a finite interval

摘要

Radial basis function (RBF) interpolation is a “meshless” strategy with great promise for adaptive approximation. One restriction is “error saturation” which occurs for many types of RBFs including Gaussian RBFs of the form ϕ(x;α,h)=exp(−α2(x/h)2): in the limit h→0 for fixed α, the error does not converge to zero, but rather to ES(α). Previous studies have theoretically determined the saturation error for Gaussian RBF on an infinite, uniform interval and for the same with a single point omitted. (The gap enormously increases ES(α).) We show experimentally that the saturation error on the unit interval, x∈[−1,1], is about 0.06exp(−0.47/α2)‖f‖∞ — huge compared to the O(2π/α2)exp(−π2/[4α2]) saturation error for a grid with one point omitted. We show that the reason the saturation is so large on a finite interval is that it is equivalent to an infinite grid which is uniform except for a gap of many points. The saturation error can be avoided by choosing α≪1, the “flat limit”, but the condition number of the interpolation matrix explodes as O(exp(π2/[4α2])). The best strategy is to choose the largest α which yields an acceptably small saturation error: If the user chooses an error tolerance δ, then αoptimum(δ)=1/−2log(δ/0.06).