Skip to content Skip to navigation

Connexions

You are here: Home » Content » Approximation in ℓ_p Norms

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Approximation in ℓ_p Norms

Module by: Mark A. Davenport. E-mail the author

So far, our approximation problem has been posed in an inner product space, and we have thus measured our approximation error using norms that are induced by an inner product such as the L2/ℓ2L2/ℓ2 norms (or weighted L2/ℓ2L2/ℓ2 norms). Sometimes this is a natural choice – it can be interpreted as the “energy” in the error and arises often in the case of signals corrupted by Gaussian noise. However, more often than not, it is used simply because it is easy to deal with.

In some cases we might be interested in approximating with respect to other norms – in particular we will consider approximation with respect to ℓpℓp-norms for p≠0p≠0. First, we introduce the concept of a “unit ball”. Any norm gives us rise to a unit ball, i.e., x:x=1.x:x=1. Some important examples of unit balls for the ℓpℓp norms in R2R2 are depicted below.

Figure 1
(a) (b) (c)
Illustrations of the ell_p balls for p=1,2,infinity. For p=2, the ball is a circle. For p=infinity, it is a square. For p=1, it is a diamond.Figure 1(b) (10_2.png)Figure 1(c) (10_3.png)

We now consider an example of approximating a point in R2R2 with a point in a 1-D subspace while measuring error using the ℓpℓp norm for p=1,2,∞p=1,2,∞.

Example 1

Suppose V=R2V=R2,

A = span 2 - 1 , and x = 2 1 . A = span 2 - 1 , and x = 2 1 .
(1)

We will want to find x^∈Ax^∈A that minimizes x-x^px-x^p. Since x^∈Ax^∈A, we can write

x ^ = 2 α - α x ^ = 2 α - α
(2)

and thus

e = x - x ^ = 2 - 2 α 1 + α . e = x - x ^ = 2 - 2 α 1 + α .
(3)

While we can solve for α∈Rα∈R to minimize epep directly in some cases, a geometric interpretation is also useful. In each case, on can imagine growing an ℓpℓp ball centered on xx until the ball intersects with AA. This will be the point x^∈Ax^∈A. that is closest to xx in the ℓpℓp norm. We first illustrate this for the ℓ2ℓ2 norm below:

Figure 2
An illustration of approximation to a 1-D subspace in R2 using the ell_2 norm. The subspace is tangent to the sphere at the point where the radius of the sphere is just large enough to touch the line. This provides another 'proof' of the orthogonality principle.

In order to calculate x^x^ we can apply the orthogonality principle. Since 〈e,[21]T〉=0〈e,[21]T〉=0 we obtain a solution defined by α=35α=35.

We now observe that in the case of the ℓ∞ℓ∞ norm the picture changes somewhat. The closest point in ℓ∞ℓ∞ is illustrated below:

Figure 3
An illustration of approximation to a 1-D subspace in R2 using the ell_infinity norm. The square first touches the line at a different point than the sphere. In this case both entries of the error vector have equal magnitude.

Note that the error is no longer orthogonal to the subspace AA. In this case we can still calculate x^x^ from the observation that the two terms in the error should be equal, which yields α=13α=13.

The situation is even more different for the case of the ℓ1ℓ1 norm, which is illustrated below:

Figure 4
An illustration of approximation to a 1-D subspace in R2 using the ell_1 norm. The diamond first touches the line at yet another point. In this case the error vector has only one non-zero value.

We now observe that x^x^ corresponds to α=1α=1. Note that in this case the error term is [02]T[02]T. This punctuates a general trend: for large values of pp, the ℓpℓp norm tends to spread error evenly across all terms, while for small values of pp the error is more highly concentrated.

When is it useful to approximate in ℓpℓp or LpLp norms for p≠0p≠0?

Example 2

  • Filter Design: In some cases we will want the best fit to a specified frequency response in an L∞L∞ sense rather than the L2L2 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∞L∞ norm of the error is small, then we are guaranteed that the approximation to our desired frequency response will lie within the illustrated bounds.
    Figure 5
    An illustration depicting a desired frequency response (low-pass) and maximum bounds by which we will allow other the actual frequency response to deviate from the desired one.
  • Geometry representation: In compressing 3D geometry, can be useful to bound the L∞L∞ 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 ℓ1ℓ1 norm.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks