Poszukiwanie dopasowujące

Rekonstrukcja przykładowego sygnału algorytmem matching pursuit za pomocą programu mp4

Poszukiwanie dopasowujące (ang. matching pursuit) – rodzaj techniki numerycznej, która polega na znalezieniu „najlepszego dopasowania” funkcji z określonego słownika $D$ do wielowymiarowych danych. Podstawowa idea polega na reprezentacji sygnału $f$ z przestrzeni Hilberta $H$ jako ważonej sumy funkcji $g_{\gamma _{n}}$ (zwanych atomami) ze słownika $D{:}$

$f(t)=\sum _{n=-\infty }^{+\infty }a_{n}g_{\gamma _{n}}(t).$

Przykładem podobnych reprezentacji jest rozwinięcie w szereg Fouriera, gdy słownik jest zbudowany tylko z podstawowych funkcji (najmniejszy możliwy kompletny słownik). Główną wadą analizy Fouriera w cyfrowym przetwarzaniu sygnałów jest to, że mówi nam ona tylko o globalnych cechach sygnałów i nie dostosowuje się do analizowanych sygnałów $f.$ Używając redundantnego słownika możemy szukać w nim funkcji, które najlepiej pasują do sygnału f. Znalezienie takiej reprezentacji, gdzie większość współczynników w sumie jest zbliżone do 0 jest pożądane m.in. do kodowania sygnału i kompresji.

Algorytm

Przeszukiwanie bardzo dużych słowników dla najlepszego dopasowania jest nie do zaakceptowania przy obliczeniach w zastosowaniach praktycznych. W 1993 Mallat i Zhang zaproponowali jako rozwiązanie algorytm zachłanny, znany od tego czasu jako Matching Pursuit. Jest to algorytm rekurencyjny, którego realizacja wygląda następująco:

1. Wejście: Sygnał: $f(t).$
2. Wyjście: Lista współczynników: $\left(a_{n},g_{\gamma _{n}}\right).$
3. Inicjalizacja: $Rf_{1}\leftarrow f(t).$
4. Powtarzaj:
   1. znajdź $g_{\gamma _{n}}\in D$ z maksymalną wartością bezwzględną iloczynu skalarnego $|\langle Rf_{n},g_{\gamma _{n}}\rangle |;$
   2. $a_{n}\leftarrow \langle Rf_{n},g_{\gamma _{n}}\rangle ;$
   3. $Rf_{n+1}\leftarrow Rf_{n}-a_{n}g_{\gamma _{n}};$
   4. $n\leftarrow n+1;$

aż do stanu zatrzymania (na przykład: $\|Rf_{n}\|<{\text{threshold}}$).

Najczęściej używa się słownika składającego się z funkcji Gabora:

$g_{\gamma _{n}}(t)=K(\gamma \phi )e^{-\pi ({\frac {t-u}{s}})^{2}}\sin(\omega (t-u)+\phi ).$

Taki dobór funkcji bazowych minimalizuje zasadę nieoznaczoności w przestrzeni czas-częstość.

Właściwości

• Dla każdego $m$ spełniona jest zasada zachowania energii:

$\|f\|^{2}=\sum _{n=0}^{m-1}{|a_{n}|^{2}}+\lVert Rf_{m}\rVert ^{2}.$

• Błąd $\|Rf_{n}\|$ maleje monotonicznie (jego zanik jest wykładniczy).

Zobacz też

• analiza głównych składowych
• cyfrowe przetwarzanie sygnałów

Linki zewnętrzne

• Opis algorytmu. brain.fuw.edu.pl. [zarchiwizowane z tego adresu (2008-12-01)].