For much of its history, signal processing has focused on signals produced by physical systems. Many natural and man-made systems can be modeled as linear. Thus, it is natural to consider signal models that complement this kind of linear structure. This notion has been incorporated into modern signal processing by modeling signals as vectors living in an appropriate vector space. This captures the linear structure that we often desire, namely that if we add two signals together then we obtain a new, physically meaningful signal. Moreover, vector spaces allow us to apply intuitions and tools from geometry in R3R3, such as lengths, distances, and angles, to describe and compare signals of interest. This is useful even when our signals live in high-dimensional or infinite-dimensional spaces.

Throughout this course, we will treat signals as real-valued functions having domains that are either continuous or discrete, and either infinite or finite. These assumptions will be made clear as necessary in each chapter. In this course, we will assume that the reader is relatively comfortable with the key concepts in vector spaces. We now provide only a brief review of some of the key concepts in vector spaces that will be required in developing the theory of compressive sensing (CS). For a more thorough review of vector spaces see this introductory course in Digital Signal Processing.

We will typically be concerned with normed vector spaces, i.e., vector spaces endowed with a norm. In the case of a discrete, finite domain, we can view our signals as vectors in an NN-dimensional Euclidean space, denoted by RNRN. When dealing with vectors in RNRN, we will make frequent use of the ℓpℓp norms, which are defined for p∈[1,∞]p∈[1,∞] as

In Euclidean space we can also consider the standard inner product in RNRN, which we denote

This inner product leads to the ℓ2ℓ2 norm: x2=〈x,x〉x2=〈x,x〉.

In some contexts it is useful to extend the notion of ℓpℓp norms to the case where p<1p<1. In this case, the “norm” defined in Equation 1 fails to satisfy the triangle inequality, so it is actually a quasinorm. We will also make frequent use of the notation x0:=| supp (x)|x0:=| supp (x)|, where supp (x)={i:xi≠0} supp (x)={i:xi≠0} denotes the support of xx and | supp (x)|| supp (x)| denotes the cardinality of supp (x) supp (x). Note that ·0·0 is not even a quasinorm, but one can easily show that

justifying this choice of notation. The ℓpℓp (quasi-)norms have notably different properties for different values of pp. To illustrate this, in Figure 1 we show the unit sphere, i.e., {x:xp=1},{x:xp=1}, induced by each of these norms in R2R2. Note that for p<1p<1 the corresponding unit sphere is nonconvex (reflecting the quasinorm's violation of the triangle inequality).

Figure 1: Unit spheres in R2R2 for the ℓpℓp norms with p=1,2,∞p=1,2,∞, and for the ℓpℓp quasinorm with p=12p=12.

(a) Unit sphere for ℓ1ℓ1 norm (b) Unit sphere for ℓ2ℓ2 norm (c) Unit sphere for ℓ∞ℓ∞ norm (d) Unit sphere for ℓpℓp quasinorm

We typically use norms as a measure of the strength of a signal, or the size of an error. For example, suppose we are given a signal x∈R2x∈R2 and wish to approximate it using a point in a one-dimensional affine space AA. If we measure the approximation error using an ℓpℓp norm, then our task is to find the x^∈Ax^∈A that minimizes x-x^px-x^p. The choice of pp will have a significant effect on the properties of the resulting approximation error. An example is illustrated in Figure 2. To compute the closest point in AA to xx using each ℓpℓp norm, we can imagine growing an ℓpℓp sphere centered on xx until it intersects with AA. This will be the point x^∈Ax^∈A that is closest to xx in the corresponding ℓpℓp norm. We observe that larger pp tends to spread out the error more evenly among the two coefficients, while smaller pp leads to an error that is more unevenly distributed and tends to be sparse. This intuition generalizes to higher dimensions, and plays an important role in the development of CS theory.

Figure 2: Best approximation of a point in R2R2 by a a one-dimensional subspace using the ℓpℓp norms for p=1,2,∞p=1,2,∞, and the ℓpℓp quasinorm with p=12p=12.

(a) Approximation in ℓ1ℓ1 norm (b) Approximation in ℓ2ℓ2 norm (c) Approximation in ℓ∞ℓ∞ norm (d) Approximation in ℓpℓp quasinorm

Content actions

Add module to:

My Favorites Login Required (?)

'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 Login Required (?)

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

Footer

This work is licensed by Marco F. Duarte and Mark A. Davenport under a Creative Commons Attribution License (CC-BY 3.0), and is an Open Educational Resource.

Last edited by Mark A. Davenport on Apr 14, 2011 12:18 pm -0500.