# OpenStax_CNX

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

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

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

# 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 pp-norms for p0p0. 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 pp norms in R2R2 are depicted below.

We now consider an example of approximating a point in R2R2 with a point in a 1-D subspace while measuring error using the pp 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 pp 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 pp norm. We first illustrate this for the 22 norm below:

In order to calculate x^x^ we can apply the orthogonality principle. Since e,[21]T=0e,[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:

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 11 norm, which is illustrated below:

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 pp 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 pp or LpLp norms for p0p0?

## Example 2

• Filter Design: In some cases we will want the best fit to a specified frequency response in an LL 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 LL 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 LL 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 11 norm.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

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

PDF | EPUB (?)

### What is an EPUB file?

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

#### Collection 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?

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

#### 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?

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