on best uniform approximation from subspaces

Overview

This post provides a rigorous examination of the 1977 paper by Borosh, Chui, and Smith (Borosh, 1977), which definitively proved a conjecture by G.G. Lorentz. The central result establishes that for approximating the monomial $x^N$ on $[0,1]$ using a $k$-dimensional subspace spanned by lower-order monomials $\{x^{{\lambda }_1},\dots ,x^{{\lambda }_k}\}$, the error is strictly minimized by selecting the exponents closest to $N$. We explore the proof’s reliance on Extended Totally Positive (ETP) kernels and its implications for the theory of Haar spaces.

🏷️ Problem Setup and Lorentz’s Conjecture

Consider the collection of integer exponents ${\Lambda }_k=\{\lambda =({\lambda }_1,\dots ,{\lambda }_k):0\le {\lambda }_1<\cdots <{\lambda }_k<N\}$. For each $\lambda \in {\Lambda }_k$, we define the subspace:

$$S(\lambda )=\mathrm{span}\{x^{{\lambda }_1},\dots ,x^{{\lambda }_k}\}$$

We are interested in the Best Uniform Approximation of $x^N$ from $S(\lambda )$ on the unit interval $[0,1]$. The distance is measured in the supremum norm:

$$d(x^N,S(\lambda ))=\underset{P\in S(\lambda )}{\inf }\Vert x^N-P(x){\Vert }_{\infty }$$

Lorentz conjectured that the “optimal” subspace is spanned by the $k$ monomials immediately preceding $x^N$ [@lorentz1977approximation]:

Lorentz's Conjecture (Theorem 1)

The distance $d(x^N,S(\lambda ))$ is uniquely minimized for ${\lambda }^{\ast }=(N-k,N-k+1,\dots ,N-1)$.

🏷️ Mathematical Foundations: Haar Spaces and Duality

To analyze the distance function, we first characterize it using the properties of Haar Spaces.

Definition: Haar Space

A subspace $S\subset C[a,b]$ of dimension $k$ is a Haar space if every non-zero element in $S$ has at most $k-1$ zeros in $[a,b]$. Equivalently, for any $k$ distinct points $x_i\in [a,b]$, the interpolation matrix $({\varphi }_j(x_i))$ is non-singular.

For any $\lambda \in {\Lambda }_k$, the set $\{x^{{\lambda }_1},\dots ,x^{{\lambda }_k}\}$ forms a Haar space on $(0,1]$. If ${\lambda }_1=0$, it is a Haar space on the closed interval $[0,1]$. Invoking the Duality Theorem for linear approximation, which identifies the $L_{\infty }$ error with a discrete supremum over alternation sets, the authors establish:

Lemma 1: Determinantal Characterization

Let $X=\{\mathbf{x}=(x_1,\dots ,x_{k+1}):0<x_1<\cdots <x_{k+1}<1\}$. Then:

$$d(x^N,S(\lambda ))=\underset{\mathbf{x}\in X}{\sup }|w(\mathbf{x},\lambda )|$$

where $w$ is obtained by solving the linear system representing the Chebyshev equioscillation condition:

$$\left[\begin{array}{cccc}{x}_1^{{\lambda }_1}& \dots & x_1^{{\lambda }_k}& 1\\ x_2^{{\lambda }_1}& \dots & x_2^{{\lambda }_k}& -1\\ ⋮& & ⋮& ⋮\\ x_{k+1}^{{\lambda }_1}& \dots & x_{k+1}^{{\lambda }_k}& (-1{)}^k\end{array}\right]\left[\begin{array}{c}{u}_1\\ ⋮\\ u_k\\ w\end{array}\right]=\left[\begin{array}{c}{x}_1^N\\ x_2^N\\ ⋮\\ x_{k+1}^N\end{array}\right]\text{\hspace{1em}(L1)}$$

Here, $w$ represents the magnitude of the error at the $k+1$ alternation points, with alternating signs ensured by the final column of the matrix $D$.

🏷️ The Engine of the Proof: ETP Kernels

The core of the proof relies on the theory of Extended Totally Positive (ETP) kernels [@karlinsamuelTotalPositivityVol1968].

Definition: ETP Kernel

A kernel $K(x,y)$ is ETP on $(a,b)\times (c,d)$ if for any ordered sets of points $a<x_1<\cdots <x_r<b$ and $c<y_1<\cdots <y_r<d$, the Fredholm determinant is strictly positive:

$$\det [K(x_i,y_j){]}_{i,j=1}^r>0$$

The kernel $K(x,\lambda )=x^{\lambda }$ is ETP on $(0,\infty )\times \mathbb{R}$. This property yields two critical identities for the proof:

1. Positivity of Generalized Vandermonde Determinants: $\det (x_i^{{\lambda }_j})>0$.

2. Derivative Determinants: Determinants involving logarithmic derivatives maintain predictable sign patterns:

   $$(-1{)}^{r-j}\left|\begin{array}{cccc}{x}_1^{{\lambda }_1}& \dots & x_1^{{\lambda }_r}& x_1^{{\lambda }_j}\log x_1\\ ⋮& & ⋮& ⋮\\ x_{r+1}^{{\lambda }_1}& \dots & x_{r+1}^{{\lambda }_r}& x_{r+1}^{{\lambda }_j}\log x_{r+1}\end{array}\right|>0\text{\hspace{1em}(ETP2)}$$

🏷️ Rigorous Derivation of Monotonicity

The most elegant part of the paper is proving that the approximation error $w^{\ast }=|w|$ is a strictly decreasing function of each exponent ${\lambda }_j$.

1. Determining the Sign of the Error

Let $D$ be the matrix in $(L1)$ and $B$ be the matrix obtained by replacing the last column of $D$ with $(x_1^N,\dots ,x_{k+1}^N{)}^T$. By Cramer’s rule, $w=\det B/\det D$.

• Numerator $\det B$: This is a generalized Vandermonde determinant with ordered exponents $({\lambda }_1,\dots ,{\lambda }_k,N)$. Since $x^{\lambda }$ is ETP, $\det B>0$.
• Denominator $\det D$: Expanding $\det D$ along the last column gives ${\sum }_{i=1}^{k+1}(-1{)}^{k+i+1}(-1{)}^{i-1}{M}_i$, where $M_i$ is the $k\times k$ minor. Each $M_i>0$ by ETP. The term becomes $(-1{)}^k\sum M_i$, thus $(-1{)}^k\det D>0$.
• Result: $w^{\ast }=|w|=(-1{)}^{k}w$.

2. Implicit Sensitivity Analysis

To find how the error changes with the exponents, we differentiate $(L1)$ implicitly with respect to ${\lambda }_j$:

$$D\left[\begin{array}{c}\frac{\partial u_1}{\partial {\lambda }_j}\\ ⋮\\ \frac{\partial u_k}{\partial {\lambda }_j}\\ \frac{\partial w}{\partial {\lambda }_j}\end{array}\right]=-u_j\left[\begin{array}{c}{x}_1^{{\lambda }_j}\log x_1\\ ⋮\\ x_{k+1}^{{\lambda }_j}\log x_{k+1}\end{array}\right]$$

By Cramer’s rule, the derivative $\frac{\partial w}{\partial {\lambda }_j}$ is:

$$\frac{\partial w}{\partial {\lambda }_j}=-\frac{u_j}{\det D}\left|\begin{array}{cccc}{x}_1^{{\lambda }_1}& \dots & x_1^{{\lambda }_k}& x_1^{{\lambda }_j}\log x_1\\ ⋮& & ⋮& ⋮\\ x_{k+1}^{{\lambda }_1}& \dots & x_{k+1}^{{\lambda }_k}& x_{k+1}^{{\lambda }_j}\log x_{k+1}\end{array}\right|$$

Invoking identity (ETP2), the determinant on the right has the sign $(-1{)}^{k-j+1}$. Let $P_1>0$ be its magnitude. Then:

$$\frac{\partial w}{\partial {\lambda }_j}=\frac{(-1{)}^{k-j+1}}{\det D}{P}_1{u}_j⟹\frac{\partial w^{\ast }}{\partial {\lambda }_j}=\frac{(-1{)}^{j+1}{P}_1}{\det D}{u}_j$$

Further applying Cramer’s rule to the original system $(L1)$ to solve for $u_j$ and expanding via ETP properties shows that $u_j$ has the sign $(-1{)}^j/\det D$. Let $P_2>0$ be the magnitude. Substituting this gives the strict monotonicity result:

$$\frac{\partial w^{\ast }}{\partial {\lambda }_j}=-\frac{P_1{P}_2}{(\det D{)}^2}<0$$

3. Minimax Argument for Global Optimality

The final step bridges the gap between local sensitivities over alternation sets and the global distance minimization. Unlike general minimax theorems, this proof relies on the collapse of the infimum due to strict monotonicity.

Lemma 3: Minimax Interchange

Let $X$ be the space of alternation sets and ${\Lambda }_k$ the set of exponents. Then:

$$\underset{\lambda \in {\Lambda }_k}{\inf }\underset{\mathbf{x}\in X}{\sup }{w}^{\ast }(\mathbf{x},\lambda )=\underset{\mathbf{x}\in X}{\sup }\underset{\lambda \in {\Lambda }_k}{\inf }{w}^{\ast }(\mathbf{x},\lambda )$$

Proof: Lemma 3 (Inf-Sup Interchange)

1. Max-Min Inequality: By the standard weak minimax inequality, we have: $$\underset{\mathbf{x}\in X}{\sup }\underset{\lambda \in {\Lambda }_k}{\inf }{w}^{\ast }(\mathbf{x},\lambda )\le \underset{\lambda \in {\Lambda }_k}{\inf }\underset{\mathbf{x}\in X}{\sup }{w}^{\ast }(\mathbf{x},\lambda )=\underset{\lambda \in {\Lambda }_k}{\inf }d(x^N,S(\lambda ))$$
2. Attaining the Boundary: Since $\frac{\partial w^{\ast }}{\partial {\lambda }_j}<0$, for any fixed $\mathbf{x}\in X$, $w^{\ast }(\mathbf{x},\lambda )$ is minimized when the ${\lambda }_j$ are as large as possible. In the set ${\Lambda }_k$, this unique maximizer is ${\lambda }^{\ast }$. Thus: $$\underset{\lambda \in {\Lambda }_k}{\inf }{w}^{\ast }(\mathbf{x},\lambda )=w^{\ast }(\mathbf{x},{\lambda }^{\ast })$$
3. Interchange Equality: Substituting this into the left side: $$\underset{\mathbf{x}\in X}{\sup }{w}^{\ast }(\mathbf{x},{\lambda }^{\ast })=d(x^N,S({\lambda }^{\ast }))$$
4. Conclusion: Since $d(x^N,S({\lambda }^{\ast }))\le {\inf }_{\lambda \in {\Lambda }_k}d(x^N,S(\lambda ))$ would be a contradiction (as ${\lambda }^{\ast }\in {\Lambda }_k$), the inequalities must collapse to equality. This proves that ${\lambda }^{\ast }$ is the unique minimizer of the global uniform approximation error. ▮

🏷️ Generalizations and the Multivariate Challenge

While Theorem 3 in the paper generalizes the result to any target function $f$ representable as an integral of an ETP kernel (e.g., $f(x)={\int }_N^d{x}^{y}d\mu (y)$), extending these results to multivariate settings (${\mathbb{R}}^d$) poses significant theoretical hurdles.

1. The Breakdown of Haar Spaces

In one dimension, the existence of Haar spaces is guaranteed. However, the Mairhuber-Curtis Theorem states that for $d\ge 2$, there are no Haar spaces of dimension $k>1$ on any compact set with non-empty interior. This implies that the unique “alternation” property used in Lemma 1 does not exist in higher dimensions, making the $L_{\infty }$ distance much harder to characterize determinantally.

2. Loss of Total Positivity

The ETP property is intrinsically tied to the linear ordering of the real line. In ${\mathbb{R}}^d$, there is no natural order that preserves the positivity of minors for general kernels. For a multivariate kernel $K(\mathbf{x},\mathbf{y})={\mathbf{x}}^{\alpha }{\mathbf{y}}^{\beta }$, the positivity of the generalized Vandermonde determinant depends on the configuration of points in space, leading to “ghost singularities” where the matrix becomes singular despite the points being distinct.

3. Potential Directions: Radial and Tensor Products

• Tensor Product Spaces: One can maintain monotonicity if the subspace is a tensor product of univariate ETP spans. In this case, the error can be bounded by the sum of univariate errors.
• Radial Basis Functions (RBFs): Certain classes (like the Gaussian or multiquadric) are Conditionally Positive Definite. While not ETP, they satisfy oscillation properties that might allow for a “radial” version of the Lorentz conjecture.

🔗 See Also

• on improved Nyström bounds --- Explores the $L^2$ version of subspace projection and spectral decay.
• on eigenvalue estimate of kernel --- The ETP property is the fundamental reason for the non-oscillation of kernel eigenfunctions.

📚 References

🐻  Borosh 1977. Best uniform approximation from a collection of subspaces.