  Approximation/interpolation from spaces of positive definite or conditionally
positive definite kernels is an increasingly popular tool for the analysis and
synthesis of scattered data, and is central to many meshless methods. For a set
of $N$ scattered sites, the standard basis for such a space utilizes $N$
\emph{globally} supported kernels; computing with it is prohibitively expensive
for large $N$. Easily computable, well-localized bases, with "small-footprint"
basis elements - i.e., elements using only a small number of kernels -- have
been unavailable. Working on $\sphere$, with focus on the restricted surface
spline kernels (e.g. the thin-plate splines restricted to the sphere), we
construct easily computable, spatially well-localized, small-footprint, robust
bases for the associated kernel spaces. Our theory predicts that each element
of the local basis is constructed by using a combination of only
$\mathcal{O}((\log N)^2)$ kernels, which makes the construction computationally
cheap. We prove that the new basis is $L_p$ stable and satisfies polynomial
decay estimates that are stationary with respect to the density of the data
sites, and we present a quasi-interpolation scheme that provides optimal $L_p$
approximation orders. Although our focus is on $\mathbb{S}^2$, much of the
theory applies to other manifolds - $\mathbb{S}^d$, the rotation group, and so
on. Finally, we construct algorithms to implement these schemes and use them to
conduct numerical experiments, which validate our theory for interpolation
problems on $\mathbb{S}^2$ involving over one hundred fifty thousand data
sites.
