Poszukiwanie dopasowujące
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/21/Matching_pursuit.png/350px-Matching_pursuit.png)
Poszukiwanie dopasowujące (ang. matching pursuit) – rodzaj techniki numerycznej, która polega na znalezieniu „najlepszego dopasowania” funkcji z określonego słownika do wielowymiarowych danych. Podstawowa idea polega na reprezentacji sygnału z przestrzeni Hilberta jako ważonej sumy funkcji (zwanych atomami) ze słownika
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 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:
- Wejście: Sygnał:
- Wyjście: Lista współczynników:
- Inicjalizacja:
- Powtarzaj:
- znajdź z maksymalną wartością bezwzględną iloczynu skalarnego
- aż do stanu zatrzymania (na przykład: ).
Najczęściej używa się słownika składającego się z funkcji Gabora:
Taki dobór funkcji bazowych minimalizuje zasadę nieoznaczoności w przestrzeni czas-częstość.
Właściwości
- Dla każdego spełniona jest zasada zachowania energii:
- Błąd maleje monotonicznie (jego zanik jest wykładniczy).
Zobacz też
Przypisy
- ↑ 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)].