Technical Summary: Constrained Kolmogorov Widths

Problem Statement

The central problem addressed in this paper is the quantitative analysis of constrained approximation. In classical approximation theory, the goal is to approximate elements of a compact set $K$ (a model class) using functions from a finite-dimensional linear space $V$ of dimension $n$. The efficiency of this process is measured by the Kolmogorov width $d_n(K)_X$.

However, many applications (e.g., numerical PDEs, learning theory, geometric design) require the approximating function to satisfy additional constraints, such as preserving monotonicity, convexity, positivity, or remaining within the model class $K$ itself. This paper investigates how imposing such constraints affects the approximation efficiency. Specifically, it defines and studies constrained Kolmogorov widths, denoted $d_n(K, C)_X$, where the approximating functions must belong to the intersection of a linear space $V$ and a constraining class $C$.

The primary question is whether the imposition of these constraints degrades the asymptotic rate of approximation (i.e., does $d_n(K, C)_X$ decay significantly slower than $d_n(K)_X$ as $n \to \infty$?).

Methodology and Definitions

The paper employs a systematic framework of "widths" to measure approximation capabilities under various restrictions.

1. Standard Widths: The authors recall the definitions of Kolmogorov widths ($d_n$), linear widths ($\delta_n$), and Gelfand widths ($d_n$).
2. Constrained Widths:
   • Constrained Kolmogorov Width ($d_n(K, C)_X$): The infimum over $n$-dimensional spaces $V$ of the worst-case error when approximating $f \in K$ by elements in $V \cap C$.
   • $\gamma$-Constrained Width ($d_n^{c, \gamma}(K)_X$): A relaxation where the approximant must lie in $V \cap K_\gamma$, where $K_\gamma = \bigcup_{0 \le \lambda \le \gamma} \lambda K$. This allows the approximant to be a scaled version of the model class.
3. Related Widths:
   • Greedy Widths ($d_n^g(K)_X$): Approximation spaces spanned by elements of $K$.
   • Restricted Widths ($d_n^r(K)_X$): Approximation spaces spanned by elements of the linear span of $K$.
4. Analytical Tools:
   • Interpolation Theory: The paper utilizes real interpolation methods to relate Besov spaces and approximation classes.
   • K-functional: Used to define interpolation spaces and derive upper bounds for widths.
   • Jackson and Bernstein Inequalities: Employed to characterize approximation spaces and establish equivalence between different width definitions.

Key Contributions and Results

1. General Properties and Comparisons (Sections 2–4)

The paper establishes fundamental relationships between the various widths for general Banach spaces and compact sets.

• Inequalities: It proves a hierarchy of widths:
  $$d_n(K)_X \le d_n^r(K)_X \le d_n^g(K)_X \le \lim_{\gamma \to \infty} d_n^{c, \gamma}(K)_X \le d_n^{c, \gamma}(K)_X \le d_n^c(K)_X$$
• Equivalence in Hilbert Spaces: For convex, centrally symmetric sets $K$ in a Hilbert space, the restricted, greedy, and $\gamma$-constrained widths (as $\gamma \to \infty$) coincide with the standard Kolmogorov width.
• Loss of Efficiency in General Settings: The paper demonstrates that for general Banach spaces and arbitrary compact sets, the constrained widths can be significantly larger than the standard widths.
  • Theorem 4.6: There exist Banach spaces and sets where $d_n^r(K)_X \ge C\sqrt{n} d_n(K)_X$.
  • Theorem 4.7: For Hilbert spaces and convex sets, there is no direct comparison of the form $d_n^c(K)_X \le \lambda_n d_{m_n}(K)_X$ that holds universally; constrained widths can remain large even when standard widths are small.
  • Lemma 4.8: For the unit ball of $\ell_1$ in $\ell_\infty$, the standard width decays as $O(\sqrt{\log(m/n)/n})$, while the constrained width is bounded below by a constant ($1/2$), indicating a severe loss of efficiency for strict constraints ($\gamma=1$).

2. Classical Settings: Interpolation and Approximation Spaces (Sections 5–6)

The paper shifts focus to "classical settings" where $K$ is the unit ball of specific smoothness classes (Besov spaces, approximation classes) in $L_p$ spaces.

• Interpolation Spaces: The authors prove that for interpolation spaces $X_{\theta, q}$, the $\gamma$-constrained width decays at the same rate as the standard width, provided $\gamma$ is sufficiently large. Specifically, if $d_n(U(Y))_X \sim \delta_n$, then $d_n^{c, \tilde{\gamma}}(U(X_{\theta, q}))_X \lesssim \delta_n^\theta$.
• Approximation Classes: For approximation classes $A(\sigma, X)$, the paper shows that the restricted, greedy, and $\gamma$-constrained widths are equal to the standard Kolmogorov width (up to a constant factor in $\gamma$).
  • Theorem 6.2: For approximation classes defined by a sequence $\sigma_n$, $d_n^r(U(\sigma, X))_X = d_n^{c, \gamma_n}(U(\sigma, X))_X = d_n(U(\sigma, X))_X = \sigma_n$, where $\gamma_n$ is a constant depending on the quasi-norm constant.
• Refined Approximation Spaces: The results are extended to refined spaces $A_q^r$, showing that the asymptotic decay rate of the $\gamma$-constrained widths matches the standard widths for sufficiently large $\gamma$.

3. Smoothness Classes and Besov Spaces (Section 7)

The paper applies the previous theoretical machinery to Besov spaces $B_q^s(L_p(\Omega))$ on bounded Lipschitz domains.

• Upper Bounds: Using the fact that Besov spaces are both interpolation and approximation spaces, the authors derive upper bounds for the $\gamma$-constrained widths.
• Main Result (Theorem 7.1): For Besov balls $U(B_q^s(L_\tau(\Omega)))$ in $L_p(\Omega)$, there exists a $\gamma$ (depending on parameters) such that:
  $$d_n^{c, \gamma}(U_s^{\tau, q})_{L_p} \lesssim (n+1)^{-(s/d - (1/\tau - 1/p)_+)}$$
  This rate matches the known asymptotic decay of the standard Kolmogorov widths for these classes.
• Limitations: The authors note that while the upper bounds are established, the lower bounds for constrained widths in the "Kashin regime" (where optimal approximation requires probabilistic methods rather than classical polynomials/splines) remain an open problem.

Significance and Claims

The paper claims to provide a systematic study of constrained approximation, distinguishing between general settings where constraints can severely degrade performance and classical smoothness settings where they do not.

• No Loss in Efficiency for Classical Classes: The primary positive result is that for classical model classes (Besov spaces, approximation classes) in $L_p$ spaces, the imposition of constraints (specifically $\gamma$-constraints where the approximant is allowed to be a scaled version of the model class) does not degrade the asymptotic rate of approximation. The constrained widths decay at the same rate as the unconstrained Kolmogorov widths.
• Role of $\gamma$: The paper highlights that while strict constraints ($\gamma=1$) can lead to significant losses (as seen in the $\ell_1/\ell_\infty$ example), relaxing the constraint to allow a scaling factor $\gamma$ (even a fixed finite one) is often sufficient to recover the optimal approximation rate.
• Tools for Learning Theory: The introduction of $\gamma$-constrained widths is motivated by learning theory, where one seeks approximants that are "close" to the model class. The results suggest that in many practical scenarios involving smoothness, one can enforce these structural constraints without sacrificing the theoretical convergence rates.

The authors remain modest regarding the "Kashin regime," explicitly stating that for certain cases where optimal unconstrained approximation relies on non-constructive probabilistic methods, the behavior of the constrained widths is not yet fully understood.