thumb|350px|Rekonstrukcja przykładowego sygnału algorytmem matching pursuit za pomocą programu mp4 Poszukiwanie dopasowujące () – 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 ZhangS.G. Mallat and Z. Zhang, Matching Pursuits with Time-Frequency Dictionaries, IEEE Transactions on Signal Processing, December 1993, s. 3397–3415. 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ż analiza głównych składowych cyfrowe przetwarzanie sygnałów

Przypisy

Linki zewnętrzne

Kategoria:Cyfrowe przetwarzanie sygnałów Kategoria:Aproksymacja