Lecture 18: Best Approximant

1.Best approximants

Interpolation of data $𝒟=\{(x_i,y_i=f\left(x_i\right)),i=0,\dots ,n\}$ by an approximant $p\left(t\right)$ corresponds to the minimization problem

in the discrete one-norm at the sample points $x_i$

Different approximants are obtained upon changing the norm.

Theorem (Existence of best approximant. For any element $f\in F$ in a normed vector space $ℱ=(F,S,+,\cdot )$, there exists a best approximant $g\in G$ within a finite dimensional subspace $G\subset F$ that is a solution of

The argument underlying the above theorem is based upon constructing the closed and bounded subset of $G$

Since $G$ is finite dimensional, $K$ is compact, and the continuous mapping $g\to ||g-f||$ attains is extrema.

The two main classes of approximants $g$ of real functions $f:[a,b]\to ℝ$ that arise are:

Approximants based upon sampling

The vectors $𝒇=f\left(𝒙\right),𝒈=g\left(𝒙\right)$ are constructed at sample points $𝒙\in {ℝ}^m$ and the best approximant solves the problem

${\displaystyle {min}_{g\in G}||𝒇-𝒈||.}$

Note that the minimization is carried out over the members of the subset $G$, not over the vectors $𝒈$. The norm can include information on derivatives as in the norm

${\displaystyle {||f||}_H={||𝒇||}_1+{||{𝒇}^{\text{'}}||}_1,}$

arising in Hermite interpolation.

Approximants over the function domain

The norm is now expressed through an integral such as the $p$-norms

${\displaystyle {||f||}_p={(\underset{a}{\overset{b}{\int }}{\left|f\left(t\right)\right|}^{p}dt)}^{1/p}.}$

In general, the best approximant in a normed space is not unique. However, the best approximant is unique in a Hilbert space, and is further characterized by orthogonality of the residual to the approximation subspace.

Theorem (Best Approximant in Hilbert space). For any element $f\in F$ in a Hilbert space $ℱ=(F,S,+,\cdot )$, there exists a unique approximant $g\in G$ within a finite dimensional subspace $G\subset F$ that is a solution of

and the residual $f-g$ is orthogonal to $G$, $\forall h\in G$

Note that orthogonality of the residual $(f-g,h)=0$ implies $(f,h)=(g,h)$ or that the best approximant is the projection of $f$ onto $G$.

2.Two-norm approximants in Hilbert spaces

For Hilbert spaces with a norm is induced by the scalar product

finding the best approximant reduces to a problem within ${ℝ}^m$ (or ${ℂ}^m$). Introduce a basis $ℬ=\{b_1,b_2,\dots \}$ for $ℱ$ such that any $f\in F$ has an expansion

Since $G$ is finite dimensional, say $n=\dim \left(G\right)$, an approximant has expansion

Note that the approximation may lie in an arbitrary finite-dimensional subspace of $ℱ$. Choosing the appropriate subset through the function $s:\mathbb{N}\to \mathbb{N}$ is an interesting problem in itself, leading to the goal of selecting those basis functions that capture the largest components of $f$, i.e., the solution of

Approximate solutions of the basis component selection are obtained by processes such as greedy approximation or clustering algorithms. The approach typically adopted is to exploit the Bessel inequality

and select

eliminate $s\left(1\right)$ from $S$, and search again. The $k^{\mathrm{th}}$-step is

with $S_k=S-\{s\left(1\right),\dots ,s(k-1)\}$.

Assuming $s\left(j\right)=j$, the orthogonality relation $f-g\perp G$ leads to a linear system

If the basis is orthonormal, then $𝑩=𝑰$, and the best approximant is simply given by the projection of $f$ onto the basis elements. Note that the scalar product need not be the Euclidean discrete or continuous versions

A weighting function may be present as in

discrete and continuous versions, respectively. In essense the appropriate measure $\mu \left(t\right)$ for some specific problem

arises and might not be the Euclidean measure $w\left(t\right)=1$.

3.Inf-norm approximants

In the vector space of continuous functions defined on a topological space $X$ (e.g., a closed and bounded set in ${ℝ}^n$), a norm can be defined by

and the best approximant is found by solving the problem

The fact that $g$ is the best approximant of $f$ can be restated as $0$ being the approximant of $f-g$ since

A key role is played by the points where $f\left(x\right)=g\left(x\right)$ leading to the definition of a critical set as

When $G=P_{n-1}$, the space of polynomials of degree at most $n-1$, with $\dim P_{n-1}=n$, the best approximant can be charaterized by the number of sign changes of $f\left(x\right)-g\left(x\right)$.

Theorem (Chebyshev Alternation). The polynomial $p\in P_{n-1}$ is the best approximant of $f:[a,b]\to ℝ$ in the inf-norm

if and only if there exist $n+1$ points $a⩽x_0<x_1<\cdots <x_n⩽b$ such that

where $\left|s\right|=1$.

Recall that choosing $x_i=\cos [(2i-1)\pi /\left(2n\right)]$, the roots of the $T_n\left(\theta \right)=\cos (n\theta )$ Chebyshev polynomial (with $x=\cos \theta$, $a=-1$, $b=1$), leads to the optimal error bound in polynomial interpolation

The error bound came about from consideration of the alternation of signs of $p\left(x_j\right)-q\left(x_j\right)$ at the extrema of the Chebyshev polynomial $T_n,$ $x_i=\cos (i\pi /n)$, $i=0,1,\dots n$, with $p,q$ monic polynomials. The Cebyshev alternation theorem generalizes this observation and allows the formulation of a general approach to finding the best inf-norm approximant known as the Remez algorithm. The idea is that rather than seeking to satisfy the interpolation conditions

in the monomial basis

attempt to find $n$ alternating-sign extrema points by considering the basis set

with $\pm 𝟏=\left[\begin{array}{llll}+1& -1& +1& \dots \end{array}\right]$.