Poszukiwanie dopasowujące

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Rekonstrukcja przykładowego sygnału algorytmem matching pursuit za pomoca programu mp4

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[edytuj]

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ł: .
  2. Wyjście: Lista współczynników: .
  3. Inicjalizacja: ;
  4. Powtarzaj:
    1. znajdź z maksymalną wartością bezwzględną iloczynu skalarnego ;
    2. ;
    3. ;
    4. ;
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[edytuj]

  • Dla każdego tspełniona jest zasada zachowania energii:
  • Błąd maleje monotonicznie (jego zanik jest wykładniczy).

Zobacz też[edytuj]

Przypisy

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

Linki zewnętrzne[edytuj]