Poszukiwanie dopasowujące

Rekonstrukcja przykładowego sygnału algorytmem matching pursuit za pomocą programu mp4

Poszukiwanie dopasowujące (Szablon:Ang.) – rodzaj 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=-\mathrm{\infty }}^{+\mathrm{\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: $(a_n,g_{{\gamma }_n}).$
3. Inicjalizacja: $R{f}_1\leftarrow f(t).$
4. Powtarzaj:
   1. znajdź $g_{{\gamma }_n}\in D$ z maksymalną wartością bezwzględną iloczynu skalarnego $|⟨R{f}_n,g_{{\gamma }_n}⟩|;$
   2. $a_n\leftarrow ⟨R{f}_n,g_{{\gamma }_n}⟩;$
   3. $R{f}_{n+1}\leftarrow R{f}_n-a_n{g}_{{\gamma }_n};$
   4. $n\leftarrow n+1;$

aż do stanu zatrzymania (na przykład: $\Vert R{f}_n\Vert <\text{threshold}$).

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

$g_{{\gamma }_n}(t)=K(\gamma \varphi )e^{-\pi (\frac{t-u}{s}{)}^2}\sin (\omega (t-u)+\varphi ).$

Taki dobór funkcji bazowych minimalizuje zasadę nieoznaczoności w przestrzeni czas-częstość.

Właściwości

• Dla każdego $m$ spełniona jest zasada zachowania energii:

$\Vert f{\Vert }^2=\sum _{n=0}^{m-1}|a_n{|}^2+\Vert R{f}_m{\Vert }^2.$

• Błąd $\Vert R{f}_n\Vert$ maleje monotonicznie (jego zanik jest wykładniczy).

Zobacz też

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

Linki zewnętrzne

• Szablon:Cytuj stronę