Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Compressible signals

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Compressible signals

Module by: Marco F. Duarte, Mark A. Davenport. E-mail the authors

Summary: This module describes compressible signals, i.e., signals that can be well-approximated by sparse signals.

Compressibility and KK-term approximation

An important assumption used in the context of compressive sensing (CS) is that signals exhibit a degree of structure. So far the only structure we have considered is sparsity, i.e., the number of non-zero values the signal has when representation in an orthonormal basis ΨΨ. The signal is considered sparse if it has only a few nonzero values in comparison with its overall length.

Few structured signals are truly sparse; rather they are compressible. A signal is compressible if its sorted coefficient magnitudes in ΨΨ decay rapidly. To consider this mathematically, let xx be a signal which is compressible in the basis ΨΨ:

x = Ψ α , x = Ψ α ,
(1)

where αα are the coefficients of xx in the basis ΨΨ. If xx is compressible, then the magnitudes of the sorted coefficients αsαs observe a power law decay:

| α s | C 1 s - q , s = 1 , 2 , . . . . | α s | C 1 s - q , s = 1 , 2 , . . . .
(2)

We define a signal as being compressible if it obeys this power law decay. The larger qq is, the faster the magnitudes decay, and the more compressible a signal is. Figure 1 shows images that are compressible in different bases.

Figure 1: The image in the upper left is a signal that is compressible in space. When the pixel values are sorted from largest to smallest, there is a sharp descent. The image in the lower left is not compressible in space, but it is compressible in wavelets since its wavelet coefficients exhibit a power law decay.
(a) (b) (c) (d)
Figure 1(a) (bigdipper.png)Figure 1(b) (bigdippersorted.png)Figure 1(c) (cman.png)Figure 1(d) (cmansorted.png)

Because the magnitudes of their coefficients decay so rapidly, compressible signals can be represented well by KNKN coefficients. The best KK-term approximation of a signal is the one in which the KK largest coefficients are kept, with the rest being zero. The error between the true signal and its KK term approximation is denoted the KK-term approximation error σK(x)σK(x), defined as

σ K ( x ) = arg min α Σ K x - Ψ α 2 . σ K ( x ) = arg min α Σ K x - Ψ α 2 .
(3)

For compressible signals, we can establish a bound with power law decay as follows:

σ K ( x ) C 2 K 1 / 2 - s . σ K ( x ) C 2 K 1 / 2 - s .
(4)

In fact, one can show that σK(x)2σK(x)2 will decay as K-rK-r if and only if the sorted coefficients αiαi decay as i-r+1/2i-r+1/2 [1]. Figure 2 shows an image and its KK-term approximation.

Figure 2: Sparse approximation of a natural image. (a) Original image. (b) Approximation of image obtained by keeping only the largest 10% of the wavelet coefficients. Because natural images are compressible in a wavelet domain, approximating this image it in terms of its largest wavelet coefficients maintains good fidelity.
(a) (b)
Figure 2(a) (Cameraman.png)Figure 2(b) (cman10per.png)

Compressibility and pp spaces

A signal's compressibility is related to the pp space to which the signal belongs. An infinite sequence x(n)x(n) is an element of an pp space for a particular value of pp if and only if its pp norm is finite:

x p = i | x i | p 1 p < . x p = i | x i | p 1 p < .
(5)

The smaller pp is, the faster the sequence's values must decay in order to converge so that the norm is bounded. In the limiting case of p=0p=0, the “norm” is actually a pseudo-norm and counts the number of non-zero values. As pp decreases, the size of its corresponding pp space also decreases. Figure 3 shows various pp unit balls (all sequences whose pp norm is 1) in 3 dimensions.

Figure 3: As the value of pp decreases, the size of the corresponding pp space also decreases. This can be seen visually when comparing the the size of the spaces of signals, in three dimensions, for which the pp norm is less than or equal to one. The volume of these pp “balls” decreases with pp.
Figure 3 (pballs.png)

Suppose that a signal is sampled infinitely finely, and call it x[n]x[n]. In order for this sequence to have a bounded pp norm, its coefficients must have a power-law rate of decay with q>1/pq>1/p. Therefore a signal which is in an pp space with p1p1 obeys a power law decay, and is therefore compressible.

References

  1. DeVore, R. (1998). Nonlinear Approximation. Acta Numerica, 7, 51–150.

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