Matching pursuit

A signal and its wavelet representation. Each pixel in the heat map (top) represents an atom (a wavelet centered in time according to the horizontal position and with frequency corresponding to height). The color of the pixel gives the inner product of the corresponding wavelet atom with the signal (bottom). Matching pursuit should represent the signal by just a few atoms, such as the three at the centers of the clearly visible ellipses.

Matching pursuit (MP) is a sparse approximation algorithm which involves finding the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary $D$ . The basic idea is to approximately represent a signal $f$ from Hilbert space $H$ as a weighted sum of finitely many functions $g_{\gamma _{n}}$ (called atoms) taken from $D$ . An approximation with $N$ atoms has the form

f(t)\approx {\hat {f}}_{N}(t):=\sum _{n=1}^{N}a_{n}g_{\gamma _{n}}(t)

where $a_{n}$ is the scalar weighting factor (amplitude) for the atom $g_{\gamma _{n}}\in D$ . Normally, not every atom in $D$ will be used in this sum. Instead, matching pursuit chooses the atoms one at a time in order to maximally (greedily) reduce the approximation error. This is achieved by finding the atom that has the biggest inner product with the signal (assuming the atoms are normalized), subtracting from the signal an approximation that uses only that one atom, and repeating the process until the signal is satisfactorily decomposed, i.e., the norm of the residual is small, where the residual after calculating $\gamma _{N}$ and $a_{N}$ is denoted by

R_{N+1}=f-{\hat {f}}_{N}

If $R_{n}$ converges quickly to zero, then only a few atoms are needed to get a good approximation to $f$ . Such sparse representations are desirable for signal coding and compression. More precisely, the sparsity problem that matching pursuit is intended to approximately solve is

\min _{x}\|f-Dx\|_{2}^{2}\ {\text{ subject to }}\ \|x\|_{0}\leq N,

with $\|x\|_{0}$ the $L_{0}$ pseudo-norm (i.e. the number of nonzero elements of $x$ ). In the previous notation, the nonzero entries of $x$ are $x_{\gamma _{n}}=a_{n}$ , and the $\gamma _{n}$ th column of the matrix $D$ is $g_{\gamma _{n}}$ . Solving the sparsity problem exactly is NP-hard, which is why approximation methods like MP are used.

For comparison, consider the Fourier series representation of a signal - this can be described in the terms given above, where the dictionary is built from sinusoidal basis functions (the smallest possible complete dictionary). The main disadvantage of Fourier analysis in signal processing is that it extracts only global features of signals and does not adapt to analysed signals $f$ . By taking an extremely redundant dictionary we can look in it for functions that best match a signal $f$ .

The algorithm

If $D$ contains a large number of vectors, searching for the most sparse representation of $f$ is computationally unacceptable for practical applications. In 1993 Mallat and Zhang^[1] proposed a greedy solution that they named "Matching Pursuit." The algorithm iteratively generates for any signal $f$ and any dictionary $D$ a sorted list of atom indices and weighting scalars which represent the sub-optimal solution to the problem of sparse signal representation.

Algorithm Matching Pursuit
 Input: Signal:  $f(t)$ , dictionary  $D$ .
 Output: List of coefficients  $(a_{n})_{n=1}^{N}$  and indices for corresponding atoms  $(\gamma _{n})_{n=1}^{N}$ .
 Initialization:
    $R_{1}\,\leftarrow \,f(t)$ ;
    $n\,\leftarrow \,1$ ;
 Repeat:
   Find  $g_{\gamma _{n}}\in D$  with maximum inner product  $|\langle R_{n},g_{\gamma _{n}}\rangle |$ ;
    $a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle /\|g_{\gamma _{n}}\|^{2}$ ;
    $R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}$ ;
    $n\,\leftarrow \,n+1$ ;
 Until stop condition (for example:  $\|R_{n}\|<\mathrm {threshold}$ )
 return

"←" is a shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
"return" terminates the algorithm and outputs the value that follows.

The concept of matching pursuit in signal processing is related to statistical projection pursuit, in which "interesting" projections were found; ones that deviate more from a normal distribution are considered to be more interesting.

Properties

The algorithm converges (i.e. $R_{n}\to 0$ ) for any $f$ that is in the space spanned by the dictionary.
The error $\|R_{n}\|$ decreases monotonically.
In the case that the vectors in $D$ are orthonormal instead of redundant, then MP is a form of principal component analysis, and the energy conservation equation is satisfied for each $N$ :

\|f\|^{2}=\|R_{N+1}\|^{2}+\sum _{n=1}^{N}{|a_{n}|^{2}}

Applications

Matching pursuit has been applied to signal, image and video coding,^[2]^[3] shape representation and recognition,^[4] 3D objects coding,^[5] and in interdisciplinary applications like structural health monitoring.^[6] It has been shown that it performs better than DCT based coding for low bit rates in both efficiency of coding and quality of image.^[7] The main problem with matching pursuit is the computational complexity of the encoder. In the basic version of an algorithm, the large dictionary has to be searched at each iteration. Improvements include the use of approximate dictionary representations and suboptimal ways of choosing the best match at each iteration (atom extraction).^[8] The matching pursuit algorithm is used in MP/SOFT, a method of simulating quantum dynamics.^[9]

MP is also used in dictionary learning.^[10] In this algorithm, atoms are learned from a database and not chosen among generic dictionaries.

Extensions

A popular extension of Matching Pursuit (MP) is its orthogonal version: Orthogonal Matching Pursuit^[11]^[12] (OMP). The main difference from MP is that after every step, all the coefficients extracted so far are updated, by computing the orthogonal projection of the signal onto the set of atoms selected so far. This can lead to better results than standard MP, but requires more computation.

Extensions such as Multichannel MP^[13] and Multichannel OMP^[14] allow to process multicomponents signals.

Matching pursuit is related to the field of compressed sensing and has been extended by researchers in that community. Notable extensions are Orthogonal Matching Pursuit (OMP),^[15] Stagewise OMP (StOMP),^[16] compressive sampling matching pursuit (CoSaMP),^[17] and Multipath Matching Pursuit (MMP).^[18]

References

↑ S. G. Mallat and Z. Zhang, Matching Pursuits with Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, December 1993, pp. 3397–3415.
↑ F. Bergeaud and S. Mallat. Matching pursuit of images, In Proc. International Conference on Image Processing, volume 1, pages 53–56 vol.1, 1995.
↑ R. Neff and A. Zakhor. Very low bit-rate video coding based on matching pursuits, IEEE Transactions on Circuits and Systems for Video Technology, 7(1):158–171, 1997.
↑ F. Mendels, P. Vandergheynst, and J.P. Thiran. Matching pursuit-based shape representation and recognition using scale-space, 2006.
↑ Tosic, I.; Frossard, P. & Vandergheynst, P. Progressive coding of 3D objects based on over-complete decompositions, 2005.
↑ Debejyo Chakraborty, Narayan Kovvali, Jun Wei, Antonia Papandreou-Suppappola, Douglas Cochran, and Aditi Chattopadhyay, Damage Classification Structural Health Monitoring in Bolted Structures Using Time-frequency Techniques, Journal of Intelligent Material Systems and Structures, special issue on Structural Health Monitoring, Vol. 20(11), pp 1289-1305, July, 2009.
↑ L. U. Perrinet, M. Samuelides and S. Thorpe "Sparse spike coding in an asynchronous feed-forward multi-layer neural network using Matching Pursuit." Neurocomputing, Vol. 57C, 2002, pp. 125–34
↑ Jian-Liang Lin, Wen-Liang Hwang, and Soo-Chang Pei. Fast matching pursuit video coding by combining dictionary approximation and atom extraction. IEEE Transactions on Circuits and Systems for Video Technology, 17(12):1679–1689, 2007.
↑ "Matching-pursuit for simulations of quantum processes", Yinghua Wu and Victor S. Batista, Chem. Phys., Vol. 118, No. 15, 15 April 2003
↑ "The K-SVD: An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation", M. Aharon, M. Elad, and A.M. Bruckstein, IEEE Trans. on Signal Processing, 2006
↑ "Orthogonal Matching Pursuit : recursive function approximation with application to wavelet decomposition", Y. Pati, R. Rezaiifar, P. Krishnaprasad, in Asilomar Conf. on Signals, Systems and Comput., 1993
↑ "Adaptive time-frequency decompositions with matching pursuits", G. Davis, S. Mallat, Z. Zhang, Optical Engineering, 1994
↑ "Piecewise linear source separation", R. Gribonval, Proc. SPIE '03, 2003
↑ "Algorithms for simultaneous sparse approximations ; Part I : Greedy pursuit", Joel Tropp, A. Gilbert, M. Strauss , Signal Proc. – Sparse approximations in signal and image processing, vol.86, pp 572–588, 2006
↑ Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit, Joel A. Tropp and Anna C. Gilbert, IEEE Transactions on Information Theory, Vol. 53, NO. 12, December 2007
↑ "Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit", David L. Donoho , Yaakov Tsaig , Iddo Drori , Jean-luc Starck, 2006
↑ "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples", D. Needell and J.A. Tropp, Applied and Computational Harmonic Analysis, 2009
↑ Multipath Matching Pursuit, S. Kwon, J. Wang, and B. Shim, IEEE Transactions on Information Theory, vol. 60 no. 5, pp. 2986-3001, May, 2014

This article is issued from Wikipedia - version of the 8/20/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.