Poszukiwanie dopasowujące

Rekonstrukcja przykładowego sygnału algorytmem matching pursuit za pomoca programu mp4 (http://eeg.pl/mp).

Poszukiwanie dopasowujące (ang. Matching pursuit), jest rodzajem 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 $|<Rf_n, g_{\gamma_n}>|$;
   2. $a_n \leftarrow <Rf_n, g_{\gamma_n}>$;
   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|| < \mbox{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$ tspełniona jest zasada zachowania energii:

$||f||^2 = \sum_{n=0}^{m-1}{|a_n|^2} + ||Rf_m||^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
• Darmowe oprogramowanie realizujace algorytm matching pursuit