1.21 Approximation in ℓ_p norms

Suppose $V={\mathbb{R}}^2$ ,

We will want to find $\widehat{x}\in A$ that minimizes ${∥x,-,\widehat{x}∥}_p$ . Since $\widehat{x}\in A$ , we can write

and thus

While we can solve for $\alpha \in \mathbb{R}$ to minimize ${∥e∥}_p$ directly in some cases, a geometric interpretation is also useful. In each case, on can imagine growing an ${\ell }_p$ ball centered on $x$ until the ball intersects with $A$ . This will be the point $\widehat{x}\in A$ . that is closest to $x$ in the ${\ell }_p$ norm. We first illustrate this for the ${\ell }_2$ norm below:

In order to calculate $\widehat{x}$ we can apply the orthogonality principle. Since $⟨e,{\left[21\right]}^T⟩=0$ we obtain a solution defined by $\alpha =\frac{3}{5}$ .

We now observe that in the case of the ${\ell }_{\infty }$ norm the picture changes somewhat. The closest point in ${\ell }_{\infty }$ is illustrated below:

Note that the error is no longer orthogonal to the subspace $A$ . In this case we can still calculate $\widehat{x}$ from the observation that the two terms in the error should be equal, which yields $\alpha =\frac{1}{3}$ .

The situation is even more different for the case of the ${\ell }_1$ norm, which is illustrated below:

We now observe that $\widehat{x}$ corresponds to $\alpha =1$ . Note that in this case the error term is ${\left[02\right]}^T$ . This punctuates a general trend: for large values of $p$ , the ${\ell }_p$ norm tends to spread error evenly across all terms, while for small values of $p$ the error is more highly concentrated.

• Filter Design In some cases we will want the best fit to a specified frequency response in an $L_{\infty }$ sense rather than the $L_2$ sense. This minimizes the maximum error rather than total energy in the error. In the figure below we illustrate a desired frequency response. If the $L_{\infty }$ norm of the error is small, then we are guaranteed that the approximation to our desired frequency response will lie within the illustrated bounds.

  

• Geometry representation In compressing 3D geometry, can be useful to bound the $L_{\infty }$ error to ensure that basic shapes of narrow features (like poles, power lines, etc.) are preserved.
• Sparsity In the case where the error is known to be sparse (i.e., zero on most indices) it can be useful to measure the error in the ${\ell }_1$ norm.