Some of the simplest models in signal processing correspond to linear subspaces of the ambient signal space. Bandlimited signals are one such example. Supposing, for example, that a 2π2π-periodic signal ff has Fourier transform F(ω)=0F(ω)=0 for |ω|>B|ω|>B, the Shannon/Nyquist sampling theorem [12] states that such signals can be reconstructed from 2B2B samples. Because the space of BB-bandlimited signals is closed under addition and scalar multiplication, it follows that the set of such signals forms a 2B2B-dimensional linear subspace of L2([0,2π))L2([0,2π)).

Linear signal models also appear in cases where a model dictates a linear constraint on a signal. Considering a discrete length-NN signal xx, for example, such a constraint can be written in matrix form as

A very similar class of models concerns signals living in an affine space, which can be represented for a discrete signal using

Revisiting the dictionary setting (see Signal Dictionaries and Representations), one last important linear model arises in cases where we select KK specific elements from the dictionary ΨΨ and then construct signals using linear combinations of only these KK elements; in this case the set of possible signals forms a KK-dimensional hyperplane in the ambient signal space (see Figure 1(a)).

Figure 1: Simple models for signals in R2R2. (a) The linear space spanned by one element of the dictionary ΨΨ. The bold vectors denote the elements of the dictionary, while the dashed line (plus the corresponding dictionary element) denotes the subspace spanned by that dictionary element. (b) The nonlinear set of 1-sparse signals that can be built using ΨΨ. (c) A manifold MM.

(a) (b) (c)

For example, we may construct low-frequency signals using combinations of only the lowest frequency sinusoids from the Fourier dictionary. Similar subsets may be chosen from the wavelet dictionary; in particular, one may choose only elements that span a particular scaling space VjVj. As we have mentioned previously, harmonic dictionaries such as sinusoids and wavelets are well-suited to representing smooth1 signals. This can be seen in the decay of their transform coefficients. For example, we can relate the smoothness of a continuous 1-D function ff to the decay of its Fourier coefficients F(ω)F(ω); in particular, if ∫|F(ω)|(1+|ω|H)dω<∞∫|F(ω)|(1+|ω|H)dω<∞, then f∈CHf∈CH [12]. In order to satisfy ∫|F(ω)|(1+|ω|H)dω<∞∫|F(ω)|(1+|ω|H)dω<∞, a signal must have a sufficiently fast decay of the Fourier transform coefficients |F(ω)||F(ω)| as ωω grows. Wavelet coefficients exhibit a similar decay for smooth signals: supposing f∈CHf∈CH and the wavelet basis function has at least HH vanishing moments, then as the scale j→∞j→∞, the magnitudes of the wavelet coefficients decay as 2-j(H+1/2)2-j(H+1/2) [12]. (Recall that f∈CHf∈CH implies ff is well-approximated by a polynomial, and so due the vanishing moments this polynomial will have zero contribution to the wavelet coefficients.)

Indeed, these results suggest that the largest Fourier or wavelet coefficients of smooth signals tend to concentrate at the coarsest scales (lowest-frequencies). In Linear Approximation from Approximation , we see that linear approximations formed from just the lowest frequency elements of the Fourier or wavelet dictionaries (i.e., the truncation of the Fourier or wavelet representation to only the lowest frequency terms) provide very accurate approximations to smooth signals. Put differently, smooth signals live near the subspace spanned by just the lowest frequency Fourier or wavelet basis functions.

Sparse signal models can be viewed as a generalization of linear models. The notion of sparsity comes from the fact that, by the proper choice of dictionary ΨΨ, many real-world signals x=Ψαx=Ψα have coefficient vectors αα containing few large entries, but across different signals the locations (indices in αα) of the large entries may change. We say a signal is strictly sparse (or “KK-sparse”) if all but KK entries of αα are zero.

Some examples of real-world signals for which sparse models have been proposed include neural spike trains (in time), music and other audio recordings (in time and frequency), natural images (in the wavelet or curvelet dictionaries [12], [8], [14], [11], [17], [10], [6], [5]), video sequences (in a 3-D wavelet dictionary [13], [15]), and sonar or radar pulses (in a chirplet dictionary [1]). In each of these cases, the relevant information in a sparse representation of a signal is encoded in both the locations (indices) of the significant coefficients and the values to which they are assigned. This type of uncertainty is an appropriate model for many natural signals with punctuated phenomena.

Sparsity is a nonlinear model. In particular, let ΣKΣK denote the set of all KK-sparse signals for a given dictionary. It is easy to see that the set ΣKΣK is not closed under addition. (In fact, ΣK+ΣK=Σ2KΣK+ΣK=Σ2K.) From a geometric perspective, the set of all KK-sparse signals from the dictionary ΨΨ forms not a hyperplane but rather a union of KK-dimensional hyperplanes, each spanned by KK vectors of ΨΨ (see Figure 1(b)). For a dictionary ΨΨ with ZZ entries, there are ZKZK such hyperplanes. (The geometry of sparse signal collections has also been described in terms of orthosymmetric sets; see [9].)

Signals that are not strictly sparse but rather have a few “large” and many “small” coefficients are known as compressible signals. The notion of compressibility can be made more precise by considering the rate at which the sorted magnitudes of the coefficients αα decay, and this decay rate can in turn be related to the ℓpℓp norm of the coefficient vector αα. Letting α˜α˜ denote a rearrangement of the vector αα with the coefficients ordered in terms of decreasing magnitude, then the reordered coefficients satisfy [7]

We recall from Section 1 that for a smooth signal ff, the largest Fourier and wavelet coefficients tend to cluster at coarse scales (low frequencies). Suppose, however, that the function ff is piecewise smooth; i.e., it is CHCH at every point t∈Rt∈R except for one point t0t0, at which it is discontinuous. Naturally, this phenomenon will be reflected in the transform coefficients. In the Fourier domain, this discontinuity will have a global effect, as the overall smoothness of the function ff has been reduced dramatically from HH to 0. Wavelet coefficients, however, depend only on local signal properties, and so the wavelet basis functions whose supports do not include t0t0 will be unaffected by the discontinuity. Coefficients surrounding the singularity will decay only as 2-j/22-j/2, but there are relatively few such coefficients. Indeed, at each scale there are only O(1)O(1) wavelets that include t0t0 in their supports, but these locations are highly signal-dependent. (For modeling purposes, these significant coefficients will persist through scale down the parent-child tree structure.) After reordering by magnitude, the wavelet coefficients of piecewise smooth signals will have the same general decay rate as those of smooth signals. In Nonlinear Approximation from Approximation, we see that the quality of nonlinear approximations offered by wavelets for smooth 1-D signals is not hampered by the addition of a finite number of discontinuities.

Manifold models generalize the conciseness of sparsity-based signal models. In particular, in many situations where a signal is believed to have a concise description or “few degrees of freedom,” the result is that the signal will live on or near a particular submanifold of the ambient signal space.