Algorytm w tłumie

Algorytm w tłumie to numeryczna metoda szybkiego odszumiania pościgu za bazą ; szybszy niż jakikolwiek inny algorytm dla dużych, rzadkich problemów. Algorytm ten jest metodą aktywnego zestawu , która iteracyjnie minimalizuje podproblemy globalnego odszumiania bazy:

${\ Displaystyle \ min _ {x} {\ Frac {1} {2}} \| y-Ax \|_ {2} ^ {2} + \ lambda \|x\|_ {1}.}$

gdzie jest obserwowanym sygnałem, $jest$ rzadkim sygnałem do odzyskania, $\lambda }$ oczekiwanym sygnałem pod $displaystyle$$x}$$i za$ x $x$ to parametr regularyzacji handlujący wiernością i prostotą sygnału. Prostota jest tutaj mierzona za pomocą $Displaystyle$ rozwiązania , mierzona przez jego $\ ell _ {1}}$ -norma. Aktywne strategie zestawów są bardzo wydajne w tym kontekście, ponieważ oczekuje się, że tylko kilka współczynników będzie niezerowych. Tak więc, jeśli można je zidentyfikować, rozwiązanie problemu ograniczonego do tych współczynników daje rozwiązanie. Tutaj cechy są wybierane chciwie na podstawie bezwzględnej wartości ich gradientu przy bieżącym oszacowaniu.

Inne metody aktywnego zestawu do odszumiania pogoni za bazą obejmują BLITZ, w której wybór aktywnego zestawu jest wykonywany przy użyciu luki dualności problemu, oraz The Feature Sign Search, gdzie cechy są uwzględniane na podstawie oszacowania ich znaku.

Algorytm

Składa się z następujących elementów:

1. Zadeklaruj ${\ displaystyle x}$ na 0, więc niewyjaśniona reszta ${\ displaystyle r = y}$
2. $jego$ aktywny jest zbiorem pustym, a ${\ displaystyle I ^ {c}}$ (zbiór nieaktywny)
3. Oblicz użyteczność ${\ Displaystyle u_ {j} = | \ langle rA_ {j} \ rangle |}$ dla każdego składnika w ${\ Displaystyle I ^ {c}}$
4. ${\ Displaystyle I ^ {c}}$ do , nie ${\ Displaystyle u_ {j}> \ lambda}$ zakończ
5. W przeciwnym razie dodaj komponenty do $\ około 25}$$Displaystyle$ na podstawie ich użyteczności.
6. Rozwiąż pogoń za bazą dokładnie na $,$ wyrzuć dowolny składnik , którego wartość $osiąga dokładnie 0. Ten problem$ gęsty, więc techniki programowania kwadratowego bardzo dobrze sprawdzają się w przypadku tego podproblemu.
7. Aktualizacja ${\ displaystyle r = y-Ax}$ - nb można obliczyć w podproblemie, ponieważ wszystkie elementy poza ${\ displaystyle I}$ wynoszą 0
8. Przejdź do kroku 3.

Ponieważ za każdym razem, gdy algorytm w tłumie przeprowadza wyszukiwanie globalne, dodaje do aktywnego zestawu do składników, może to być czynnik $displaystyle$ niż najlepsze algorytmy alternatywne, gdy to wyszukiwanie jest $L}$ kosztowny obliczeniowo. Twierdzenie gwarantuje, że globalne optimum zostanie osiągnięte pomimo wielorakiego charakteru algorytmu w tłumie.