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 ${\displaystyle D}$ do wielowymiarowych danych. Podstawowa idea polega na reprezentacji sygnału ${\displaystyle f}$ z przestrzeni Hilberta ${\displaystyle H}$ jako ważonej sumy funkcji ${\displaystyle g_{\gamma _{n}}}$ (zwanych atomami) ze słownika ${\displaystyle D{:}}$

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

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

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

${\displaystyle 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 ${\displaystyle m}$ spełniona jest zasada zachowania energii:

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

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

Zobacz też

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

Przypisy

1. S.G. Mallat and Z. Zhang, Matching Pursuits with Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, December 1993, s. 3397–3415.

Linki zewnętrzne

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