Odszumianie pogoni za podstawą

W matematyce stosowanej i statystyce odszumianie pościgu za bazą (BPDN) odnosi się do matematycznego problemu optymalizacji formy

${\ Displaystyle \ min _ {x} \ lewo ({\ Frac {1} {2}} \ | y-Ax \ | _{2}^{2}+\lambda \|x\|_{1}\right),}$

gdzie jest $,$ który kontroluje kompromis między rzadkością a wiernością rekonstrukcji, wektorem $x$$displaystyle x}$ \ ${\ displaystyle \ lambda} }$ jest wektorem obserwacji, $i$$Displaystyle M \$ transformacji jest $N}$${\ Displaystyle M <N}$ . Jest to przykład optymalizacji wypukłej , a także programowania kwadratowego .

Niektórzy autorzy odnoszą się do odszumiania pogoni za bazą jako do następującego ściśle powiązanego problemu:

${\ Displaystyle \ min _ {x} \ | x \ | _ {1} {\ tekst {z zastrzeżeniem}} \ | y-Ax \|_{2}^{2}\równik \delta ,}$

co dla dowolnej danej $równoważne$ nieograniczonemu sformułowaniu dla pewnej (zwykle nieznanej a priori ) wartości ${\ displaystyle \ delta}$ . Te dwa problemy są dość podobne. W praktyce zwykle preferowane jest sformułowanie nieograniczone, dla którego opracowuje się najbardziej wyspecjalizowane i wydajne algorytmy obliczeniowe.

Oba rodzaje odszumiania pogoni za bazą rozwiązują $x}$ regularyzacji z kompromisem między posiadaniem małej reszty ( $)$ się do $\ displaystyle y}$ i czyniąc ${$$-normowym$ w . $daje$ to traktować jako matematyczne stwierdzenie brzytwy Ockhama najprostszego możliwego wyjaśnienia (tj. takiego ) uwzględnienia obserwacji ${\ displaystyle y}$ .

Dokładne rozwiązania odszumowania w poszukiwaniu bazy są często najlepszym możliwym do obliczenia przybliżeniem niedookreślonego układu równań. Odszumianie w poszukiwaniu podstaw ma potencjalne zastosowania w statystyce (patrz metoda regularyzacji LASSO ), kompresji obrazu i wykrywaniu skompresowanych danych .

Kiedy $dążenia$ problem ten staje podstawą .

Odszumianie w poszukiwaniu podstaw zostało wprowadzone przez Chena i Donoho w 1994 roku w dziedzinie przetwarzania sygnałów. W statystykach jest dobrze znany pod nazwą LASSO , po tym jak został wprowadzony przez Tibshiraniego w 1996 roku.

Rozwiązywanie podstaw do odszumiania

Problem jest wypukłym problemem kwadratowym, więc można go rozwiązać za pomocą wielu ogólnych rozwiązań, takich jak metody punktów wewnętrznych . W przypadku bardzo dużych problemów zaproponowano wiele specjalistycznych metod, które są szybsze niż metody punktów wewnętrznych.

Kilka popularnych metod rozwiązywania odszumiania pościgu za bazą obejmuje algorytm in-crowd (szybkie rozwiązanie dużych, rzadkich problemów), kontynuację homotopii , kontynuację punktu stałego (specjalny przypadek algorytmu przód-tył) i przewidywany gradient widmowy dla minimalizacji L1 (co faktycznie rozwiązuje LASSO , powiązany problem).

Linki zewnętrzne

• Lista solwerów BPDN na wiki przybliżenia rzadkiego i niskiego rzędu .