  In this paper, we present a unified approach to function approximation in
reproducing kernel Hilbert spaces (RKHS) that establishes a previously
unrecognized optimality property for several well-known function approximation
techniques, such as minimum-norm interpolation, smoothing splines, and
pseudo-inverses. We consider the problem of approximating a function belonging
to an arbitrary real-valued RKHS on R^d based on approximate observations of
the function. The observations are approximate in the sense that the actual
observations (i.e., the true function values) are known only to belong to a
convex set of admissible observations. We seek a minimax optimal approximation
for the function that minimizes the supremum of the RKHS norm on the error
between the true function and the chosen approximation subject only to the
conditions that the true function belongs to a uniformly bounded uncertainty
set of functions that satisfy the constraints on the observations and that the
approximation is a member of the RKHS. We refer to such a solution as a minimax
robust reconstruction. We characterize the solution to the minimax robust
reconstruction problem and show that it is equivalent to solving a
straightforward convex optimization problem. We demonstrate that a minimax
robust reconstruction will generally be more stable than an approximation based
on interpolation through a nominal set of observations and that, subject to
some mild regularity conditions on the convex set of admissible observations,
the minimax robust reconstruction is unconditionally stable. We motivate our
results by characterizing the minimax robust reconstruction for several
specific convex observational models and discuss relationships with other
approaches to function approximation.
