2.3 Compressible signals

Compressibility and $K$ -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 $\Psi$ . 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 $\Psi$ decay rapidly. To consider this mathematically, let $x$ be a signal which is compressible in the basis $\Psi$ :

where $\alpha$ are the coefficients of $x$ in the basis $\Psi$ . If $x$ is compressible, then the magnitudes of the sorted coefficients ${\alpha }_s$ observe a power law decay:

We define a signal as being compressible if it obeys this power law decay. The larger $q$ is, the faster the magnitudes decay, and the more compressible a signal is. [link] shows images that are compressible in different bases.

Because the magnitudes of their coefficients decay so rapidly, compressible signals can be represented well by $K\ll N$ coefficients. The best $K$ -term approximation of a signal is the one in which the $K$ largest coefficients are kept, with the rest being zero. The error between the true signal and its $K$ term approximation is denoted the $K$ -term approximation error ${\sigma }_K\left(x\right)$ , defined as

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

In fact, one can show that ${\sigma }_K{\left(x\right)}_2$ will decay as $K^{-r}$ if and only if the sorted coefficients ${\alpha }_i$ decay as $i^{-r+1/2}$   [link] . [link] shows an image and its $K$ -term approximation.

Compressibility and ${\ell }_p$ Spaces

A signal's compressibility is related to the ${\ell }_p$ space to which the signal belongs. An infinite sequence $x\left(n\right)$ is an element of an ${\ell }_p$ space for a particular value of $p$ if and only if its ${\ell }_p$ norm is finite:

The smaller $p$ 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=0$ , the “norm” is actually a pseudo-norm and counts the number of non-zero values. As $p$ decreases, the size of its corresponding ${\ell }_p$ space also decreases. [link] shows various ${\ell }_p$ unit balls (all sequences whose ${\ell }_p$ norm is 1) in 3 dimensions.

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