Ronald DeVore

Andrea Bonito, Albert Cohen, Wolfgang Dahmen et al.

We discuss optimal recovery for classes of multivariate convex functions from given point samples, as well as the sampling numbers of these classes, corresponding to optimal sample choices. Upper and lower bounds for either variant are established when the reconstruction error is measured in $L_p$ for $1\leq p\leq \infty$. These bounds match, sometimes up to logarithmic factors, and therefore characterize the respective optimal rate of decay. For classical smoothness classes such as Sobolev, Hölder or Besov spaces, it is well known that the optimal decay rate of sampling numbers can be achieved by sampling on uniform tensor product grids and using linear methods of reconstruction, such as piecewise polynomial interpolation. One of the main findings in this paper is that for classes of convex functions, these procedures generally produce suboptimal rates, except when $p=1$ and $p=\infty$, and are outperformed by nonlinear reconstruction methods that do not employ tensor product grids.

Ronald DeVore, Guergana Petrova, Jonathan W. Siegel et al.

The main theme of approximation theory is to understand how well a general function $f$ can be approximated by a simpler function $g$ such as a polynomial or spline. In many applications, one wants $g$ to retain known properties of $f$ such as its inherent smoothness or a geometrical property such as monotonicity or convexity. Additional requirements on $g$ of this type are known as constraints. In this paper, we do a systematic study of constrained approximation to understand how the imposition of such constraints limits the efficiency of the approximation. We study constrained approximation in the setting of linear approximation where $g$ is to be taken from a finite dimensional linear space $V$ of a fixed dimension $n$. Kolmogorov widths describe how well one can approximate when using such linear spaces $V$. The first part of this paper introduces and studies several types of constrained widths, including the constrained Kolmogorov widths, and gives comparisons between them. The second part of the paper is restricted to classical settings where the constraint imposes a smoothness requirement on $g$. In this case, our results prove that the additional constraint can typically be imposed with no loss in the efficiency of the approximation.