0.5 Sparsity in redundant dictionaries  (Page 3/3)

Pursuit in dictionaries

Approximating signals only from orthogonal vectors brings rigidity that limits the ability tooptimize the representation. Pursuit algorithms remove this constraint with flexible proceduresthat search for sparse, although not necessarily optimal, dictionary approximations. Such approximations are computed by optimizingthe choice of dictionary vectors ${\left\{{\phi }_p\right\}}_{p\in \Lambda }$ .

Matching pursuit

Matching pursuit algorithms introduced by Mallat and Zhang (MallatZ:93) are greedy algorithms that optimize approximations by selectingdictionary vectors one by one. The vector in ${\phi }_{p_0}\in \mathcal{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 ${\phi }_{p_1}$ from the dictionary and continues this process over next-order residues $R^{m}f$ , which produces a signal decomposition:

The approximation from the M -selected vectors ${\left\{{\phi }_{p_m}\right\}}_{0\le 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 ${\phi }_{p_m}$ 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\left[p\right]$ in a dictionary $\mathcal{D}$ is equivalent to minimizing the $1^0$ norm ${\parallel a\parallel }_0$ , which gives the number of nonzero coefficients.This $1^0$ norm is highly nonconvex, which explains why the resulting minimization is NP-hard.Donoho and Chen (DonohoC:95) thus proposed replacing the $1^0$ norm by the $1^1$ norm ${\parallel a\parallel }_1={\sum }_{p\in \gamma }\left|a\left[p\right]\right|$ , which is convex. The resultingbasis pursuit algorithm computes a synthesis operator

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 optimizationthat yields representations that can be moresparse.

In approximation, compression, or denoising applications, $f$ is recovered with an error bounded by a precision parameter ϵ . The optimization [link] is thus relaxed by finding a synthesis such that

This is a convex minimization problem, with a solution calculated by minimizing the corresponding $1^1$ Lagrangian

where T is a Lagrange multiplier that depends on ϵ . This is called an $1^1$ Lagrangian pursuit in this book. A solution $\tilde{a}\left[p\right]$ is computed with iterative algorithms that are guaranteed to converge.The number of nonzero coordinates of $\tilde{a}$ typically decrea-ses as T increases.

Incoherence for support recovery

Matching pursuit and $1^1$ Lagrangian pursuits are optimal if they recover the approx-imation support λ _T , which minimizes the approximation Lagrangian

where $f_{\lambda }$ is the orthogonal projection of $f$ in the space V _λ generated by ${\left\{{\phi }_p\right\}}_{p\in \Lambda }$ . This is not always true and depends on λ _T . An Exact Recovery Criteria proved byTropp (tropp-multi-omp) guarantees that pursuit algorithms do recover the optimalsupport λ _T if

where ${\left\{{\tilde{\phi }}_p\right\}}_{p\in {\Lambda }_T}$ is the biorthogonal basis of ${\left\{{\phi }_p\right\}}_{p\in {\Lambda }_T}$ in ${\mathbf{V}}_{{\Lambda }_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 ${\left\{{\phi }_p\right\}}_{p\in \Lambda }$ has Riesz bounds that are not too far from 1. These vectors should be nearly orthogonal and hence havesmall 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 incoherentbetween themselves. It depends on the geometric configuration of λ _T in γ .