It is well-known that non-linear approximation has an advantage over linear
schemes in the sense that it provides comparable approximation rates to those
of the linear schemes, but to a larger class of approximands. This was
established for spline approximations and for wavelet approximations, and more
recently for homogeneous radial basis function (surface spline) approximations.
However, no such results are known for the Gaussian function. The crux of the
difficulty lies in the necessity to vary the tension parameter in the Gaussian
function spatially according to local information about the approximand: error
analysis of Gaussian approximation schemes with varying tension are, by and
large, an elusive target for approximators.

We introduce and analyze in this paper a new algorithm for approximating
functions using translates of Gaussian functions with varying tension
parameters. Our scheme is sophisticated to a degree that it employs even
locally Gaussians with varying tensions, and that it resolves local
singularities in a non-local way. We show that our algorithm is suitably
optimal in the sense that it provides approximation rates similar to other
established nonlinear methodologies like spline and wavelet approximations. As
expected and desired, the approximation rates can be as high as needed and are
essentially saturated only by the smoothness of the approximand.