Approximation 2: Appoximation spaces and norms

Previously, we described approximation as finding some funtion $\hat{\varphi} \in \Phi$ such that $\lVert f - \hat{\varphi} \rVert \leq \lVert f - \varphi \rVert$ for all $\varphi \in \Phi$. This leaves us with two major factors to consider in practice: the choice of the norm $\lVert \cdot \rVert$ and the choice of the family of functions that gives us the function space $\Phi$.

Choice of Norm

In general, norms induced by an inner product make for easier computation. This makes a complete function space equipped with such a norm a Hilbert space.

So what norms are most common to see in practice? Given an error function $u$ over a closed interval $[a,b]$, we commonly see:

1. The Uniform Norm aka the L$^\infty$ Norm: $\lVert u \rVert_{\infty} = \max\limits_{a \leq t \leq b} \lvert u(t) \rvert$
2. The L$^2$ Norm: $\lVert u \rVert_2 = \left( \int\limits_a^b \lvert u(t) \rvert^2 dt \right)^\frac{1}{2}$. This is the norm associated with the familiar least squares error, and is the one we'll encounter most often.
3. The weighted L$^2$ Norm: $\lVert u \rVert_{2,w} = \left( \int\limits_a^b \lvert u(t) \rvert^2 w(t) dt \right)^\frac{1}{2}$, where $w(t)$ is a weighting function of some kind, with $w(t)\geq 0$ over the interval $[a,b]$. (There is a way to express this weight in terms of the measure of integration, but it's sufficient here to consider it as given in this expression.)

(See: L$^p$ spaces, more generally, for a more thorough treatment.) Note that in most practical cases we will have some finite collection of data points to determine our approximant, so instead of integration, we will be doing summation. However, it is just as reasonable in theory to find an approximant for a defined function, especially if $f \not\in \Phi$, so this covers the general case.

Linear Spaces

Most approximation spaces we'll encounter will be at least linear spaces, if not Hilbert spaces. Linearity gives us some structure that helps with computation, as we can decompose the space into a basis. The desired property associated with real linear spaces is as follows: given any $\phi_1 \in \Phi$ and $\phi_2 \in \Phi$, then for any real value $c \in \mathbb{R}$, $\phi_1 + c \phi_2 \in \Phi$ also.

Restricting consideration to linear spaces allows us to flip the problem of the choice of space - instead we can consider the basis of the space. The basis of a function space is a collection of functions that spans the space, just like the basis of a vector space is a spanning set of vectors. Formally, given $n$ basis functions $\pi_j \in \Phi$, with $j = 1, \dots, n$, we can describe the space as:

$\Phi = \Phi_n = \left\{ \varphi : \varphi(t) = \sum\limits_{j=1}^n c_j \pi_j(t), c_j \in \mathbb{R} \right\}$

Some Linear Approximation Spaces

As mentioned previously, we often want Hilbert spaces for our approximation spaces, since computation is easier. (The structure they're imbued with is very convenient.) It is worth noting that because we only see data over a certain range $[a,b]$, we often have the benefit of only considering these on a restricted domain. This makes all of these cases integrable over such the compact set.

1. $\mathbb{P}_m$: Polynomials of degree up to $m$. The simple choice of basis is $\pi_j(t) = t^j$ for $j = 0, \dots,m$, but we will see how to construct orthogonal bases later. Weierstrass's theorem guarantees any continuous function over a finite interval can be approximated by polynomials.
2. $\mathbb{S}_m^k(\Delta)$: (Polynomial) Spline functions of degree $m$ and smoothness $k$ given a partition $\Delta$ on $[a,b]$. The partition is usually based on the data points given. The use case for these will generally be for interpolation tasks.
3. $\mathbb{T}_{2m+1}$: Trigonometric polynomials of degree up to $m$ on $[0,2\pi]$. Similar to case (i), these are dense in the L$^2$ space over $[0, 2\pi]$ and as such can obtain as close an approximation as one desires.

Exercises

Exercise 1.1: FILLER TEXT?

Image credits:

Background: Mathematics 3D Blender Illustration
Credit: MasterTux
Source: creazilla
License: CC0-1.0
Modifications: Rotated and darkened