This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (June 2023) (Learn how and when to remove this message)

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

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

where ${\displaystyle g_{\gamma _{n}}}$ is the ${\displaystyle \gamma _{n}}$th column of the matrix ${\displaystyle D}$ and ${\displaystyle a_{n}}$ is the scalar weighting factor (amplitude) for the atom ${\displaystyle g_{\gamma _{n}}}$. Normally, not every atom in ${\displaystyle 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 highest 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 ${\displaystyle \gamma _{N}}$ and ${\displaystyle a_{N}}$ is denoted by

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

If ${\displaystyle R_{n}}$ converges quickly to zero, then only a few atoms are needed to get a good approximation to ${\displaystyle 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

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

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

For comparison, consider the Fourier transform representation of a signal - this can be described using 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 the global features of the signals and does not adapt to the analysed signals ${\displaystyle f}$. By taking an extremely redundant dictionary, we can look in it for atoms (functions) that best match a signal ${\displaystyle f}$.

The algorithm

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

Algorithm Matching Pursuit
 Input: Signal: ${\displaystyle f(t)}$, dictionary ${\displaystyle D}$ with normalized columns ${\displaystyle g_{i}}$.
 Output: List of coefficients ${\displaystyle (a_{n})_{n=1}^{N}}$ and indices for corresponding atoms ${\displaystyle (\gamma _{n})_{n=1}^{N}}$.
 Initialization:
   ${\displaystyle R_{1}\,\leftarrow \,f(t)}$;
   ${\displaystyle n\,\leftarrow \,1}$;
 Repeat:
   Find ${\displaystyle g_{\gamma _{n}}\in D}$ with maximum inner product ${\displaystyle |\langle R_{n},g_{\gamma _{n}}\rangle |}$;
   ${\displaystyle a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle }$;
   ${\displaystyle R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}}$;
   ${\displaystyle n\,\leftarrow \,n+1}$;
 Until stop condition (for example: Zdroj:https://en.wikipedia.org?pojem=Matching_pursuit
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk