Constrained Kolmogorov widths
For approximation theorists, this work provides a theoretical framework for understanding how constraints affect linear approximation, with results showing that smoothness constraints often come at no cost.
This paper systematically studies constrained approximation, introducing and comparing several types of constrained Kolmogorov widths. It shows that in classical settings where the constraint imposes a smoothness requirement, the additional constraint typically imposes no loss in approximation efficiency.
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.