OpenStax_CNX

You are here: Home » Content » Compressible signals

Recently Viewed

This feature requires Javascript to be enabled.

Compressible signals

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.

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.

Compressibility and ℓpℓp 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.

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

PDF | EPUB (?)

What is an EPUB file?

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

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