Pasujący pościg

Sygnał i jego reprezentacja falkowa. Każdy piksel na mapie cieplnej (u góry) reprezentuje atom (falkę wyśrodkowaną w czasie zgodnie z położeniem poziomym iz częstotliwością odpowiadającą wysokości). Kolor piksela daje iloczyn wewnętrzny odpowiedniego atomu falkowego z sygnałem (na dole). Dopasowany pościg powinien reprezentować sygnał za pomocą zaledwie kilku atomów, takich jak trzy w środkach wyraźnie widocznych elips.

Dopasowywanie (MP) to rzadki algorytm aproksymacji $,$ który znajduje „najlepiej pasujące” projekcje wielowymiarowych danych na zakres nadmiernie kompletnego (tj. Nadmiarowego) . $($ przybliżone przedstawienie sygnału $z$ Hilberta jako $.$ sumy skończenie wielu funkcji tzw atomy) zaczerpnięte z ${\ Displaystyle D}$ . Przybliżenie z $atomami$ postać

{\ Displaystyle f (t) \ około {\ kapelusz {f}} _ {N} (t): =\suma _{n=1}^{N}a_{n}g_{\gamma _{n}}(t)}

gdzie $}}$ $\ gamma _ {n}$ to kolumna macierzy i $n}}$ $Displaystyle$ $a_ {$ jest skalarnym współczynnikiem ważenia (amplituda) dla atomu ${\ Displaystyle g_ {\ gamma _ {n}}}$ . Zwykle nie każdy atom w ${\ displaystyle D}$ zostanie wykorzystana w tej kwocie. Zamiast tego, pogoń za dopasowaniem wybiera atomy pojedynczo, aby maksymalnie (chciwie) zmniejszyć błąd aproksymacji. Osiąga się to poprzez znalezienie atomu, który ma najwyższy iloczyn wewnętrzny z sygnałem (zakładając, że atomy są znormalizowane), odjęcie od sygnału przybliżenia, które wykorzystuje tylko ten jeden atom, i powtarzanie procesu, aż sygnał zostanie zadowalająco rozłożony, tj. norma reszty jest mała, gdzie reszta po obliczeniu $}$ jest oznaczona przez $\ gamma _ {N}$

{\ Displaystyle R_ {N + 1} = f - {\ kapelusz {f}} _ {N}}

.

Jeśli szybko $do$ $zera$ , to potrzeba tylko kilku atomów, aby uzyskać dobre . Takie rzadkie reprezentacje są pożądane przy kodowaniu i kompresji sygnału. Mówiąc dokładniej, problem rzadkości, który pogoń za dopasowaniem ma w przybliżeniu rozwiązać, jest

{\ Displaystyle \ min _ {x} \ | f-Dx \ | _ {2} ^ {2} \ {\ tekst {z zastrzeżeniem} }\ \|x\|_{0}\równ N,}

gdzie $jest$ $x$ liczbą niezerowych elementów $}$ \ ). W poprzednim zapisie niezerowe wpisy są następujące: $\ displaystyle x_ {\ gamma _ {n}} = a_ {n}$ $}$ . Dokładne rozwiązanie problemu rzadkości jest NP-trudne , dlatego stosuje się metody aproksymacyjne, takie jak MP.

Dla porównania rozważmy reprezentację sygnału z transformatą Fouriera - można to opisać terminami podanymi powyżej, gdzie słownik jest zbudowany z sinusoidalnych funkcji bazowych (najmniejszy możliwy pełny słownik). Główną wadą analizy Fouriera w przetwarzaniu sygnałów jest to, że wyodrębnia ona tylko globalne cechy sygnałów i nie dostosowuje się do analizowanych sygnałów ${\ displaystyle f}$ . Biorąc wyjątkowo nadmiarowy $.$ , możemy w nim szukać atomów (funkcji), które najlepiej pasują do sygnału

Algorytm

Przykład pobrania nieznanego sygnału (linia szara) z kilku pomiarów (czarne kropki) za pomocą algorytmu dopasowywania ortogonalnego (fioletowe kropki pokazują pobrane współczynniki).

Jeśli $zawiera$ dużą liczbę wektorów, poszukiwanie najrzadszej reprezentacji jest $nie$ przyjęcia w praktycznych zastosowaniach. W 1993 roku Mallat i Zhang zaproponowali chciwe rozwiązanie, które nazwali „Dopasowanym Pogonią”. Dla dowolnego sygnału i dowolnego słownika $displaystyle$ $D}$ , algorytm iteracyjnie generuje posortowaną listę indeksów atomów i skalarów wagowych, które tworzą suboptymalne rozwiązanie problemu rzadkiej reprezentacji sygnału.

 algorytmu  dopasowywania pościgu: Sygnał: słownik:  re  $displaystyle$  $D}$  znormalizowanymi kolumnami  $}$  .  Lista  $_$  i  ${\ Displaystyle (\ gamma _ {n}) _ {n = 1} ^ {N}}$  . Inicjalizacja:   ${\ Displaystyle R_ {1} \, \ strzałka w lewo \, f (t)}$  ;  ${\ Displaystyle n \ \ strzałka w lewo \, 1}$  ; Powtórz: znajdź   ${\ displaystyle g _ {\ gamma _ {n}} \ in D}$  z maksymalnym iloczynem wewnętrznym  ${\ Displaystyle | \ langle R_ {n}, g _ {\ gamma _ {n}} \ rangle |}$  ;  ${\ Displaystyle a_ {n} \ \ strzałka w lewo \ \ langle R_ {n}, g _ {\ gamma _ {n}} \ rangle$  }  ${\ Displaystyle R_ {n + 1} \ \ strzałka w lewo \, R_ {n} -a_ {n} g_ {\ gamma _ {n}}}$  ;  ${\ Displaystyle n \, \ strzałka w lewo \, n + 1}$  ; Aż do warunku zatrzymania (na przykład:   ${\ Displaystyle \| R_ {n} \| <\ operatorname {próg}})$  powrót

„←” oznacza przypisanie . Na przykład „ największy ← przedmiot ” oznacza, że wartość największego zmienia się na wartość elementu .
„ return ” kończy działanie algorytmu i wyświetla następującą wartość.

W przetwarzaniu sygnałów koncepcja pogoni za dopasowaniem jest związana z pogonią za projekcją statystyczną , w której znajdują się „interesujące” projekcje; te, które bardziej odbiegają od rozkładu normalnego , są uważane za bardziej interesujące.

Nieruchomości

Algorytm jest zbieżny ( $)$ dla dowolnego $.$ słownikiem
Błąd $_$ _
Ponieważ na każdym kroku reszta jest prostopadła do wybranego filtra, równanie zachowania energii jest spełnione dla każdego: ${\ displaystyle N$ }

{\ Displaystyle \ | f \ | ^ {2} = \| R_ {N + 1} \| ^ {2} + \ suma _ {n = 1} ^ {N} {| a_ {n} | ^ { 2}}}

.

W przypadku, gdy wektory w $.$ ortonormalne, a nie redundantne, MP jest formą analizy głównych składowych

Aplikacje

Pogoń za dopasowaniem została zastosowana do kodowania sygnałów, obrazów i wideo, reprezentacji i rozpoznawania kształtów, kodowania obiektów 3D oraz w zastosowaniach interdyscyplinarnych, takich jak monitorowanie stanu konstrukcji. Wykazano, że działa lepiej niż DCT oparte na kodowaniu dla niskich przepływności zarówno pod względem wydajności kodowania, jak i jakości obrazu. Głównym problemem związanym z dopasowywaniem jest złożoność obliczeniowa kodera. W podstawowej wersji algorytmu przy każdej iteracji należy przeszukiwać duży słownik. Ulepszenia obejmują użycie przybliżonych reprezentacji słownikowych i suboptymalne sposoby wybierania najlepszego dopasowania w każdej iteracji (ekstrakcja atomów). Algorytm dopasowywania jest używany w MP/SOFT, metodzie symulacji dynamiki kwantowej.

MP jest również używany w nauce słowników . W tym algorytmie atomy są pobierane z bazy danych (ogólnie z naturalnych scen, takich jak zwykłe obrazy), a nie wybierane z ogólnych słowników.

Bardzo niedawnym zastosowaniem MP jest jego zastosowanie w kodowaniu obliczeń liniowych w celu przyspieszenia obliczeń iloczynów macierzowo-wektorowych.

Rozszerzenia

Popularnym rozszerzeniem Matching Pursuit (MP) jest jego ortogonalna wersja: Orthogonal Matching Pursuit (OMP). Główna różnica w stosunku do MP polega na tym, że po każdym kroku wszystkie współczynniki wyodrębnione do tej pory są aktualizowane poprzez obliczenie ortogonalnego rzutu sygnału na podprzestrzeń rozpiętą przez zestaw wybranych do tej pory atomów. Może to prowadzić do lepszych wyników niż standardowe MP, ale wymaga więcej obliczeń. Wykazano, że OMP ma gwarancje stabilności i wydajności w pewnych ograniczonych warunkach izometrycznych .

Rozszerzenia takie jak Multichannel MP i Multichannel OMP umożliwiają przetwarzanie sygnałów wieloskładnikowych. Oczywiste rozszerzenie Matching Pursuit dotyczy wielu pozycji i skal, poprzez rozszerzenie słownika tak, aby był oparty na falce. Można to zrobić wydajnie za pomocą operatora splotu bez zmiany algorytmu rdzenia.

Pogoń za dopasowaniem jest związana z dziedziną wykrywania skompresowanego i została rozszerzona przez naukowców z tej społeczności. Godne uwagi rozszerzenia to Orthogonal Matching Pursuit (OMP), Stagewise OMP (StOMP), kompresyjne dopasowywanie próbkowania (CoSAMP), Generalized OMP (gOMP) i Multipath Matching Pursuit (MMP).

Zobacz też