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

α
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 K≪NK≪N coefficients. The best KKterm 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 KKterm 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 KrKr if and only if the sorted coefficients αiαi decay as ir+1/2ir+1/2 [1].
Figure 2 shows an image and its KKterm approximation.