Computing a Quantity of Interest from Observational Data

Scientific problems often feature observational data received in the form $$w_1=l_1(f),\ldots $$ , $$w_m=l_m(f)$$ of known linear functionals applied to an unknown function f from some Banach space $$\mathcal {X}$$ , and it is required to either approximate f (the full approximation problem) or to estimate a quantity of interest Q(f). In typical examples, the quantities of interest can be the maximum/minimum of f or some averaged quantity such as the integral of f, while the observational data consists of point evaluations. To obtain meaningful results about such problems, it is necessary to possess additional information about f, usually as an assumption that f belongs to a certain model class $$\mathcal {K}$$ contained in $$\mathcal {X}$$ . This is precisely the framework of optimal recovery, which produced substantial investigations when the model class is a ball in a smoothness space, e.g., when it is a unit ball in Lipschitz, Sobolev, or Besov spaces. This paper is concerned with other model classes described by approximation processes, as studied in DeVore et al. [Data assimilation in Banach spaces, (To Appear)]. Its main contributions are: (1) designing implementable optimal or near-optimal algorithms for the estimation of quantities of interest, (2) constructing linear optimal or near-optimal algorithms for the full approximation of an unknown function using its point evaluations. While the existence of linear optimal algorithms for the approximation of linear functionals Q(f) is a classical result established by Smolyak, a numerically friendly procedure that performs this approximation is not generally available. In this paper, we show that in classical recovery settings, such linear optimal algorithms can be produced by constrained minimization methods. We illustrate these techniques on several examples involving the computation of integrals using point evaluation data. In addition, we show that linearization of optimal algorithms can be achieved for the full approximation problem in the important situation where the $$l_j$$ are point evaluations and $$\mathcal {X}$$ is a space of continuous functions equipped with the uniform norm. It is also revealed how quasi-interpolation theory enables the construction of linear near-optimal algorithms for the recovery of the underlying function.