Filter Banks

Motivated by speech compression, in 1976 Croisier, Esteban, and Galand [189] introduced an invertible filter bank, which decomposes a discrete signal f[n] into two signals of half its size using a filtering and subsampling procedure. They showed that f[n] can be recovered from these subsampled signals by canceling the aliasing terms with a particular class of filters called conjugate mirror filters. This breakthrough led to a 10-year research effort to build a complete filter bank theory. Necessary and sufficient conditions for decomposing a signal in subsampled components with a filtering scheme, and recovering the same signal with an inverse transform, were established by Smith and Barnwell [444], Vaidyanathan [469], and Vetterli [471].

The multiresolution theory of Mallat [362] and Meyer [44] proves that any conjugate mirror filter characterizes a wavelet ψ that generates an orthonormal basis of , and that a fast discrete wavelet transform is implemented by cascading these conjugate mirror filters [361]. The equivalence between this continuous time wavelet theory and discrete filter banks led to a new fruitful interface between digital signal processing and harmonic analysis, first creating a culture shock that is now well resolved.

Continuous versus Discrete and Finite

Originally many signal processing engineers were wondering what is the point of considering wavelets and signals as functions, since all computations are performed over discrete signals with conjugate mirror filters. Why bother with the convergence of infinite convolution cascades if in practice we only compute a finite number of convolutions? Answering these important questions is necessary in order to understand why this book alternates between theorems on continuous time functions and discrete algorithms applied to finite sequences.

A short answer would be “simplicity.” In , a wavelet basis is constructed by dilating and translating a single function ψ. Several important theorems relate the amplitude of wavelet coefficients to the local regularity of the signal f. Dilations are not defined over discrete sequences, and discrete wavelet bases are therefore more complex to describe. The regularity of a discrete sequence is not well defined either, which makes it more difficult to interpret the amplitude of wavelet coefficients. A theory of continuous-time functions gives asymptotic results for discrete sequences with sampling intervals decreasing to zero. This theory is useful because these asymptotic results are precise enough to understand the behavior of discrete algorithms.

But continuous time or space models are not sufficient for elaborating discrete signal-processing algorithms. The transition between continuous and discrete signals must be done with great care to maintain important properties such as orthogonality. Restricting the constructions to finite discrete signals adds another layer of complexity because of border problems. How these border issues affect numerical implementations is carefully addressed once the properties of the bases are thoroughly understood.

Wavelets for Images

Wavelet orthonormal bases of images can be constructed from wavelet orthonormal bases of one-dimensional signals. Three mother wavelets ψ¹(x), ψ²(x), and ψ³(x), with x = (x₁, x₂) ∈ ², are dilated by 2^j and translated by 2^j n with n = (n₁, n₂) ∈ ². This yields an orthonormal basis of the space L²(²) of finite energy functions f(x) = f(x₁, x₂):

The support of a wavelet is a square of width proportional to the scale 2^j. Two-dimensional wavelet bases are discretized to define orthonormal bases of images including N pixels. Wavelet coefficients are calculated with the fast O(N) algorithm described in Chapter 7.

Like in one dimension, a wavelet coefficient has a small amplitude if f(x) is regular over the support of . It has a large amplitude near sharp transitions such as edges. Figure 1.1(b) is the array of N wavelet coefficients. Each direction k and scale 2^j corresponds to a subimage, which shows in black the position of the largest coefficients above a threshold:

FIGURE 1.1 (a) Discrete image f[n] of N = 256² pixels. (b) Array of N orthogonal wavelet coefficients 〈f, ψ^k_j,n〉 for k = 1, 2, 3, and 4 scales 2^j; black points correspond to |〈f, ψ^k_j,n〉| >T. (c) Linear approximation from the N/16 wavelet coefficients at the three largest scales. (d) Nonlinear approximation from the M = N/16 wavelet coefficients of largest amplitude shown in (b).

Stochastic versus Deterministic Signal Models

A representation is optimized relative to a signal class, corresponding to all potential signals encountered in an application. This requires building signal models that carry available prior information.

A signal f can be modeled as a realization of a random process F, the probability distribution of which is known a priori. A Bayesian approach then tries to minimize the expected approximation error. Linear approximations are simpler because they only depend on the covariance. Chapter 9 shows that optimal linear approximations are obtained on the basis of principal components that are the eigenvectors of the covariance matrix. However, the expected error of nonlinear approximations depends on the full probability distribution of F. This distribution is most often not known for complex signals, such as images or sounds, because their transient structures are not adequately modeled as realizations of known processes such as Gaussian ones.

To optimize nonlinear representations, weaker but sufficiently powerful deterministic models can be elaborated. A deterministic model specifies a set Θ, where the signal belongs. This set is defined by any prior information—for example, on the time-frequency localization of transients in musical recordings or on the geometric regularity of edges in images. Simple models can also define Θ as a ball in a functional space, with a specific regularity norm such as a total variation norm. A stochastic model is richer because it provides the probability distribution in Θ. When this distribution is not available, the average error cannot be calculated and is replaced by the maximum error over Θ. Optimizing the representation then amounts to minimizing this maximum error, which is called a minimax optimization.

Sampling Theorems

Let us consider finite energy signals dx of finite support, which is normalized to [0, 1] or [0, 1]² for images. A sampling process implements a filtering of and a uniform sampling to output a discrete signal:

In two dimensions, n = (n₁, n₂) and x = (x₁, x₂). These filtered samples can also be written as inner products:

with . Chapter 3 explains that φ_s is chosen, like in the classic Shannon-Whittaker sampling theorem, so that a family of functions is a basis of an appropriate approximation space U_N. The best linear approximation of in U_N recovered from these samples is the orthogonal projection _N of f in U_N, and if the basis is orthonormal, then

(1.4)

A sampling theorem states that if ∈ U_N then so (1.4) recovers from the measured samples. Most often, does not belong to this approximation space. It is called aliasing in the context of Shannon-Whittaker sampling, where U_N is the space of functions having a frequency support restricted to the N lower frequencies. The approximation error must then be controlled.

Linear Approximation Error

The approximation error is computed by finding an orthogonal basis of the whole analog signal space L²[0, 1]², with the first N vector that defines an orthogonal basis of U_N. Thus, the orthogonal projection on U_N can be rewritten as

Since , the approximation error is the energy of the removed inner products:

This error decreases quickly when N increases if the coefficient amplitudes have a fast decay when the index m increases. The dimension N is adjusted to the desired approximation error.

Figure 1.1(a) shows a discrete image f[n] approximated with N = 256² pixels. Figure 1.1(c) displays a lower-resolution image f_N/16 projected on a space U_N/16 of dimension N/16, generated by N/16 large-scale wavelets. It is calculated by setting all the wavelet coefficients to zero at the first two smaller scales. The approximation error is ‖f – f_N/16‖²/‖f‖² = 14 × 10⁻³. Reducing the resolution introduces more blur and errors. A linear approximation space U_N corresponds to a uniform grid that approximates precisely uniform regular signals. Since images are often not uniformly regular, it is necessary to measure it at a high-resolution N. This is why digital cameras have a resolution that increases as technology improves.

Approximation by Thresholding

For M < N, an approximation f_M is computed by selecting the “best” M < N vectors within B. The orthogonal projection of f on the space V_Λ generated by M vectors {g_m}_m∈Λ in B is

(1.5)

Since , the resulting error is

(1.6)

We write |Λ| the size of the set Λ. The best M = |Λ| term approximation, which minimizes ‖f – f_Λ‖², is thus obtained by selecting the M coefficients of largest amplitude. These coefficients are above a threshold T that depends on M:

(1.7)

This approximation is nonlinear because the approximation set Λ_T changes with f. The resulting approximation error is:

(1.8)

Figure 1.1(b) shows that the approximation support Λ_T of an image in a wavelet orthonormal basis depends on the geometry of edges and textures. Keeping large wavelet coefficients is equivalent to constructing an adaptive approximation grid specified by the scale-space support Λ_T. It increases the approximation resolution where the signal is irregular. The geometry of Λ_T gives the spatial distribution of sharp image transitions and edges, and their propagation across scales. Chapter 6 proves that wavelet coefficients give important information about singularities and local Lipschitz regularity. This example illustrates how approximation support provides “geometric” information on f, relative to a dictionary, that is a wavelet basis in this example.

Figure 1.1(d) gives the nonlinear wavelet approximation f_M recovered from the M = N/16 large-amplitude wavelet coefficients, with an error ‖f – f_M‖²/‖f‖^{2 =} 5 × 10⁻³. This error is nearly three times smaller than the linear approximation error obtained with the same number of wavelet coefficients, and the image quality is much better.

An analog signal can be recovered from the discrete nonlinear approximation f_M:

Since all projections are orthogonal, the overall approximation error on the original analog signal is the sum of the analog sampling error and the discrete nonlinear error:

In practice, N is imposed by the resolution of the signal-acquisition hardware, and M is typically adjusted so that ε_n(M, f) ≥ = ε_l(N, f).

Sparsity with Regularity

Sparse representations are obtained in a basis that takes advantage of some form of regularity of the input signals, creating many small-amplitude coefficients. Since wavelets have localized support, functions with isolated singularities produce few large-amplitude wavelet coefficients in the neighborhood of these singularities. Nonlinear wavelet approximation produces a small error over spaces of functions that do not have “too many” sharp transitions and singularities. Chapter 9 shows that functions having a bounded total variation norm are useful models for images with nonfractal (finite length) edges.

Edges often define regular geometric curves. Wavelets detect the location of edges but their square support cannot take advantage of their potential geometric regularity. More sparse representations are defined in dictionaries of curvelets or bandlets, which have elongated support in multiple directions, that can be adapted to this geometrical regularity. In such dictionaries, the approximation support Λ_T is smaller but provides explicit information about edges’ local geometrical properties such as their orientation. In this context, geometry does not just apply to multidimensional signals. Audio signals, such as musical recordings, also have a complex geometric regularity in time-frequency dictionaries.

Bayes versus Minimax

To optimize the estimation operator D, one must take advantage of prior information available about signal f. In a Bayes framework, f is considered a realization of a random vector F and the Bayes risk is the expected risk calculated with respect to the prior probability distribution π of the random signal model F:

Optimizing D among all possible operators yields the minimum Bayes risk:

In the 1940s, Wald brought in a new perspective on statistics with a decision theory partly imported from the theory of games. This point of view uses deterministic models, where signals are elements of a set Θ, without specifying their probability distribution in this set. To control the risk for any f ∈ Θ, we compute the maximum risk:

The minimax risk is the lower bound computed over all operators D:

In practice, the goal is to find an operator D that is simple to implement and yields a risk close to the minimax lower bound.

Thresholding Estimators

It is tempting to restrict calculations to linear operators D because of their simplicity. Optimal linear Wiener estimators are introduced in Chapter 11. Figure 1.2(a) is an image contaminated by Gaussian white noise. Figure 1.2(b) shows an optimized linear filtering estimation = X h[n], which is therefore diagonal in a Fourier basis B. This convolution operator averages the noise but also blurs the image and keeps low-frequency noise by retaining the image’s low frequencies.

FIGURE 1.2 (a) Noisy image X. (b) Noisy wavelet coefficients above threshold, |〈X, ψ_j,n〈| ≥ T. (c) Linear estimation X h. (d) Nonlinear estimator recovered from thresholded wavelet coefficients over several translated bases.

If f has a sparse representation in a dictionary, then projecting X on the vectors of this sparse support can considerably improve linear estimators. The difficulty is identifying the sparse support of f from the noisy data X. Donoho and Johnstone [221] proved that, in an orthonormal basis, a simple thresholding of noisy coefficients does the trick. Noisy signal coefficients in an orthonormal basis B = {g_m}_m∈Γ are

Thresholding these noisy coefficients yields an orthogonal projection estimator

(1.9)

The set is an estimate of an approximation support of f. It is hopefully close to the optimal approximation support Λ_T = {m ∈ Γ : |〈f, g_m〉| ≥ T}.

Figure 1.2(b) shows the estimated approximation set of noisy-wavelet coefficients, |〈X, ψj,n| ≥ T, that can be compared to the optimal approximation support Λ_T shown in Figure 1.1(b). The estimation in Figure 1.2(d) from wavelet coefficients in has considerably reduced the noise in regular regions while keeping the sharpness of edges by preserving large-wavelet coefficients. This estimation is improved with a translation-invariant procedure that averages this estimator over several translated wavelet bases. Thresholding wavelet coefficients implements an adaptive smoothing, which averages the data X with a kernel that depends on the estimated regularity of the original signal f.

Donoho and Johnstone proved that for Gaussian white noise of variance σ², choosing yields a risk of the order of ‖f – f_ΛT‖², up to a log_e N factor. This spectacular result shows that the estimated support does nearly as well as the optimal unknown support Λ_T. The resulting risk is small if the representation is sparse and precise.

The set in Figure 1.2(b) “looks” different from the Λ_T in Figure 1.1(b) because it has more isolated points. This indicates that some prior information on the geometry of Λ_T could be used to improve the estimation. For audio noise-reduction, thresholding estimators are applied in sparse representations provided by time-frequency bases. Similar isolated time-frequency coefficients produce a highly annoying “musical noise.” Musical noise is removed with a block thresholding that regularizes the geometry of the estimated support and avoids leaving isolated points. Block thresholding also improves wavelet estimators.

If W is a Gaussian noise and signals in Θ have a sparse representation in B, then Chapter 11 proves that thresholding estimators can produce a nearly minimax risk. In particular, wavelet thresholding estimators have a nearly minimax risk for large classes of piecewise smooth signals, including bounded variation images.

Varying Time-Frequency Resolution

As opposed to windowed Fourier atoms, wavelets have a time-frequency resolution that changes. The wavelet ψ_u,s has a time support centered at u and proportional to s. Let us choose a wavelet ψ whose Fourier transform is nonzero in a positive frequency interval centered at η. The Fourier transform is dilated by 1/s and thus is localized in a positive frequency interval centered at ξ = η/s; its size is scaled by 1/s. In the time-frequency plane, the Heisenberg box of a wavelet atom is therefore a rectangle centered at (u, η/s), with time and frequency widths, respectively, proportional to s and 1/s. When s varies, the time and frequency width of this time-frequency resolution cell changes, but its area remains constant, as illustrated by Figure 1.5.

FIGURE 1.5 Heisenberg time-frequency boxes of two wavelets, ψ_u,s and ψ_u0,s0. When the scale s decreases, the time support is reduced but the frequency spread increases and covers an interval that is shifted toward high frequencies.

Large-amplitude wavelet coefficients can detect and measure short high-frequency variations because they have a narrow time localization at high frequencies. At low frequencies their time resolution is lower, but they have a better frequency resolution. This modification of time and frequency resolution is adapted to represent sounds with sharp attacks, or radar signals having a frequency that may vary quickly at high frequencies.

Multiscale Zooming

A wavelet dictionary is also adapted to analyze the scaling evolution of transients with zooming procedures across scales. Suppose now that ψ is real. Since it has a zero average, a wavelet coefficient Wf(u, s) measures the variation of f in a neighborhood of u that has a size proportional to s. Sharp signal transitions create large-amplitude wavelet coefficients.

Signal singularities have specific scaling invariance characterized by Lipschitz exponents. Chapter 6 relates the pointwise regularity of f to the asymptotic decay of the wavelet transform amplitude |Wf(u, s)| when s goes to zero. Singularities are detected by following the local maxima of the wavelet transform across scales.

In images, wavelet local maxima indicate the position of edges, which are sharp variations of image intensity. It defines scale-space approximation support of f from which precise image approximations are reconstructed. At different scales, the geometry of this local maxima support provides contours of image structures of varying sizes. This multiscale edge detection is particularly effective for pattern recognition in computer vision [146].

The zooming capability of the wavelet transform not only locates isolated singular events, but can also characterize more complex multifractal signals having nonisolated singularities. Mandelbrot [41] was the first to recognize the existence of multifractals in most corners of nature. Scaling one part of a multifractal produces a signal that is statistically similar to the whole. This self-similarity appears in the continuous wavelet transform, which modifies the analyzing scale. From global measurements of the wavelet transform decay, Chapter 6 measures the singularity distribution of multifractals. This is particularly important in analyzing their properties and testing multifractal models in physics or in financial time series.

Wavelet Packet Bases

Wavelet bases divide the frequency axis into intervals of 1 octave bandwidth. Coifman, Meyer, and Wickerhauser [182] have generalized this construction with bases that split the frequency axis in intervals of bandwidth that may be adjusted. Each frequency interval is covered by the Heisenberg time-frequency boxes of wavelet packet functions translated in time, in order to cover the whole plane, as shown by Figure 1.7.

FIGURE 1.7 A wavelet packet basis divides the frequency axis in separate intervals of varying sizes. A tiling is obtained by translating in time the wavelet packets covering each frequency interval.

As for wavelets, wavelet-packet coefficients are obtained with a filter bank of conjugate mirror filters that split the frequency axis in several frequency intervals. Different frequency segmentations correspond to different wavelet packet bases. For images, a filter bank divides the image frequency support in squares of dyadic sizes that can be adjusted.

Local Cosine Bases

Local cosine orthonormal bases are constructed by dividing the time axis instead of the frequency axis. The time axis is segmented in successive intervals [a_p, a_p+1]. The local cosine bases of Malvar [368] are obtained by designing smooth windows g_p(t) that cover each interval [a_p, a_p+1], and by multiplying them by cosine functions cos(ξt + ϕ) of different frequencies. This is yet another idea that has been independently studied in physics, signal processing, and mathematics. Malvar’s original construction was for discrete signals. At the same time, the physicist Wilson [486] was designing a local cosine basis, with smooth windows of infinite support, to analyze the properties of quantum coherent states. Malvar bases were also rediscovered and generalized by the harmonic analysts Coifman and Meyer [181]. These different views of the same bases brought to light mathematical and algorithmic properties that opened new applications.

A multiplication by cos(ξt + ϕ) translates the Fourier transform by ± ξ. Over positive frequencies, the time-frequency box of the modulated window g_p(t) cos(ξt + ϕ) is therefore equal to the time-frequency box of g_p translated by ξ along frequencies. Figure 1.8 shows the time-frequency tiling corresponding to such a local cosine basis. For images, a two-dimensional cosine basis is constructed by dividing the image support in squares of varying sizes.

FIGURE 1.8 A local cosine basis divides the time axis with smooth windows g_p(t) and translates these windows into frequency.

Dictionaries of Orthonormal Bases

To reduce the complexity of optimal approximations, the search can be reduced to subfamilies of orthogonal dictionary vectors. In a dictionary of orthonormal bases, any family of orthogonal dictionary vectors can be complemented to form an orthogonal basis B included in D. As a result, the best approximation of f from orthogonal vectors in B is obtained by thresholding the coefficients of f in a “best basis” in D.

For tree dictionaries of orthonormal bases obtained by a recursive split of orthogonal vector spaces, the fast, dynamic programming algorithm of Coifman and Wickerhauser [182] finds such a best basis with O(P) operations, where P is the dictionary size.

Wavelet packet and local cosine bases are examples of tree dictionaries of time-frequency orthonormal bases of size P = N log₂ N. A best basis is a time-frequency tiling that is the best match to the signal time-frequency structures.

To approximate geometrically regular edges, wavelets are not as efficient as curvelets, but wavelets provide more sparse representations of singularities that are not distributed along geometrically regular curves. Bandlet dictionaries, introduced by Le Pennec, Mallat, and Peyré [342, 365], are dictionaries of orthonormal bases that can adapt to the variability of images’ geometric regularity. Minimax optimal asymptotic rates are derived for compression and denoising.

Matching Pursuit

Matching pursuit algorithms introduced by Mallat and Zhang [366] are greedy algorithms that optimize approximations by selecting dictionary vectors one by one. The vector in φ_p0 ∈ D that best approximates a signal f is

and the residual approximation error is

A matching pursuit further approximates the residue Rf by selecting another best vector φ_p1 from the dictionary and continues this process over next-order residues R^mf, which produces a signal decomposition:

The approximation from the M-selected vectors {φ_pm}_0≤m<m can be refined with an orthogonal back projection on the space generated by these vectors. An orthogonal matching pursuit further improves this decomposition by orthogonalizing progressively the projection directions φ_pm during the decompositon. The resulting decompositions are applied to compression, denoising, and pattern recognition of various types of signals, images, and videos.

Basis Pursuit

Approximating f with a minimum number of nonzero coefficients a[p] in a dictionary D is equivalent to minimizing the l⁰ norm ‖a‖₀, which gives the number of nonzero coefficients. This l⁰ norm is highly nonconvex, which explains why the resulting minimization is NP-hard. Donoho and Chen [158] thus proposed replacing the l⁰ norm by the l¹ norm ‖a‖₁ = σ_p∈Γ |a[p]|, which is convex. The resulting basis pursuit algorithm computes a synthesis operator

(1.17)

This optimal solution is calculated with a linear programming algorithm. A basis pursuit is computationally more intense than a matching pursuit, but it is a more global optimization that yields representations that can be more sparse.

In approximation, compression, or denoising applications, f is recovered with an error bounded by a precision parameter ε. The optimization (1.18) is thus relaxed by finding a synthesis such that

(1.18)

This is a convex minimization problem, with a solution calculated by minimizing the corresponding l¹ Lagrangian

where T is a Lagrange multiplier that depends on ε. This is called an l¹ Lagrangian pursuit in this book. A solution is computed with iterative algorithms that are guaranteed to converge. The number of nonzero coordinates of typically decreases as T increases.

Incoherence for Support Recovery

Matching pursuit and l¹ Lagrangian pursuits are optimal if they recover the approximation support Λ_T, which minimizes the approximation Lagrangian

where f_Λ is the orthogonal projection of f in the space V_Λ generated by {φ_p}p_∈Λ. This is not always true and depends on Λ_T. An Exact Recovery Criteria proved by Tropp [464] guarantees that pursuit algorithms do recover the optimal support Λ_T if

(1.19)

where is the biorthogonal basis of {φ_p}_p∈ΛT in V_ΛT. This criterion implies that dictionary vectors φ_q outside Λ_T should have a small inner product with vectors in Λ_T.

This recovery is stable relative to noise perturbations if {φ_p}_p∈Λ has Riesz bounds that are not too far from 1. These vectors should be nearly orthogonal and hence have small inner products. These small inner-product conditions are interpreted as a form of incoherence. A stable recovery of Λ_T is possible if vectors in Λ_T are incoherent with respect to other dictionary vectors and are incoherent between themselves. It depends on the geometric configuration of Λ_T in Γ.

Singular Value Decompositions

Let f = σ_m∈Γ a[m]g_m be the representation of f in an orthonormal basis B = {g_m}_m∈Γ. An approximation must be recovered from

A basis B of singular vectors diagonalizes U*U. Then U transforms a subset of Q vectors {g_m}_m∈ΓQ of B into an orthogonal basis {Ug_m}_m∈ΓQ of ImU and sets all other vectors to zero. A singular value decomposition estimates the coefficients a[m] of f by projecting Y on this singular basis and by renormalizing the resulting coefficients

where h²_m are regularization parameters.

Such estimators recover nonzero coefficients in a space of dimension Q and thus bring no super-resolution. If U is a convolution operator, then B is the Fourier basis and a singular value estimation implements a regularized inverse convolution.

Diagonal Thresholding Estimation

The basis that diagonalizes U*U rarely provides a sparse signal representation. For example, a Fourier basis that diagonalizes convolution operators does not efficiently approximate signals including singularities.

Donoho [214] introduced more flexibility by looking for a basis B providing a sparse signal representation, where a subset of Q vectors {g_m}_m∈ΓQ are transformed by U in a Riesz basis {Ug_m}_m∈ΓQ of ImU, while the others are set to zero. With an appropriate renormalization, has a biorthogonal basis that is normalized . The sparse coefficients of f in B can then be estimated with a thresholding

for thresholds T_m appropriately defined.

For classes of signals that are sparse in B, such thresholding estimators may yield a nearly minimax risk, but they provide no super-resolution since this nonlinear projector remains in a space of dimension Q. This result applies to classes of convolution operators U in wavelet or wavelet packet bases. Diagonal inverse estimators are computationally efficient and potentially optimal in cases where super-resolution is not possible.

Geometric Conditions for Super-resolution

Let w_Λ = f – f_Λ. be the approximation error of a sparse representation f_Λ = σ_p∈Λ a[p]g_p of f. The observed signal can be written as

If the support Λ can be identified by finding a sparse approximation of Y inD_U

then we can recover a super-resolution estimation of f

This shows that super-resolution is possible if the approximation support Λ can be identified by decomposing Y in the redundant transformed dictionary D_U. If the exact recovery criteria is satisfy ERC(Λ) < 1 and if {Ug_p}_p∈Λ is a Riesz basis, then Λ can be recovered using pursuit algorithms with controlled error bounds.

For most operator U, not all sparse approximation sets can be recovered. It is necessary to impose some further geometric conditions on Λ in Γ, which makes super-resolution difficult and often unstable. Numerical applications to sparse spike deconvolution, tomography, super-resolution zooming, and inpainting illustrate these results.

Compressive Sensing with Randomness

Candès and Tao [139], and Donoho [217] proved that stable super-resolution is possible for any sufficiently sparse signal f if U is an operator with random coefficients. Compressive sensing then becomes possible by recovering a close approximation of f ∈ ^N from Q N linear measurements [133].

A recovery is stable for a sparse approximation set |Λ| ≤ M only if the corresponding dictionary family {Ug_m}_m∈Λ is a Riesz basis of the space it generates. The M-restricted isometry conditions of Candès, Tao, and Donoho [217] imposes uniform Riesz bounds for all sets Λ ⊂ Γ with |Λ| ≤ M:

(1.20)

This is a strong incoherence condition on the P vectors of {Ug_m}_m∈Γ, which supposes that any subset of less than M vectors is nearly uniformly distributed on the unit sphere of ImU.

For an orthogonal basis D = {g_m}_m∈Γ, this is possible for M ≤ C Q(log N)⁻¹ if U is a matrix with independent Gaussian random coefficients. A pursuit algorithm then provides a stable approximation of any f ∈ C^N having a sparse approximation from vectors in D.

These results open a new compressive-sensing approach to signal acquisition and representation. Instead of first discretizing linearly the signal at a high-resolution N and then computing a nonlinear representation over M coefficients in some dictionary, compressive-sensing measures directly M randomized linear coefficients. A reconstructed signal is then recovered by a nonlinear algorithm, producing an error that can be of the same order of magnitude as the error obtained by the more classic two-step approximation process, with a more economic acquisiton process. These results remain valid for several types of random matrices U. Examples of applications to single-pixel cameras, video super-resolution, new analog-to-digital converters, and MRI imaging are described.

Blind Source Separation

Sparsity in redundant dictionaries also provides efficient strategies to separate a family of signals {f_s}_0≤s<S that are linearly mixed in K ≤ S observed signals with noise:

From a stereo recording, separating the sounds of S musical instruments is an example of source separation with k = 2. Most often the mixing matrix U = {u_k,s}_{0≤k<K,0≤s<S} is unknown. Source separation is a super-resolution problem since S N data values must be recovered from Q = K N ≤ S N measurements. Not knowing the operator U makes it even more complicated.

If each source f_s has a sparse approximation support Λ_s in a dictionary D, with Σ ^S–1_s=0|Λ_s| N, then it is likely that the sets {Λ_s}_{0≤s < s} are nearly disjoint. In this case, the operator U, the supports Λ_s, and the sources f_s are approximated by computing sparse approximations of the observed data Y_k in D. The distribution of these coefficients identifies the coefficients of the mixing matrix U and the nearly disjoint source supports. Time-frequency separation of sounds illustrate these results.