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 ΨΨ:

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:

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)

Because the magnitudes of their coefficients decay so rapidly, compressible signals can be represented well by K≪NK≪N 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

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

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)

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

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 ℓpℓp space also decreases. Figure 3 shows various ℓpℓp unit balls (all sequences whose ℓpℓp norm is 1) in 3 dimensions.

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

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