Zamieszanie na temat problemu wykrywania skompresowanego

Przeczytałem niektóre odniesienia, w tym to .

Jestem trochę zdezorientowany, co kompilacja wykrywania kompresji wykrywa i próbuje rozwiązać. Czy to jest

albo i

lub / i coś jeszcze?

Brian jest na miejscu. Ale myślę, że warto dodać trochę skompresowanego kontekstu wykrywania.

Po pierwsze, zwróć uwagę, że tak zwana 0 norma - funkcja liczności lub liczba niezerowych wartości w - nie jest normą . Prawdopodobnie najlepiej jest napisać go jako coś w rodzaju w niczym innym, jak w najbardziej przypadkowych kontekstach. Nie zrozum mnie źle, jesteś w dobrym towarzystwie, gdy używasz skrótu , ale myślę, że może to powodować zamieszanie.$\|x\|_0$$x$$\mathop{\textbf{card}}(x)$$\|x\|_0$

Ludzie od dawna wiedzą, że minimalizacja normy prowadzi do rzadkich rozwiązań. Istnieje kilka teoretycznych powodów, które mają związek z komplementarnością liniową. Ale najciekawsze nie było to, że rozwiązania były rzadkie, ale że często były najrzadsze z możliwych . Oznacza to, że minimalizacja naprawdę daje rozwiązanie minimalnej liczności w niektórych przydatnych przypadkach. (Jak to odkryli, kiedy problem minimalnej liczności jest trudny do NP? Konstruując sztuczne problemy ze znanymi rzadkimi rozwiązaniami.) Nie było to coś, co mogłaby przewidzieć liniowa teoria komplementarności.$\ell_1$$\|x\|_1$$\|x\|_1$

Dziedzina wykrywania skompresowanego narodziła się, gdy naukowcy zaczęli identyfikować warunki na macierzy , które pozwoliłyby im z góry zagwarantować, że rozwiązanie było również najrzadsze. Zobacz na przykład najwcześniejsze artykuły Candés, Romberg i Tao oraz inne dyskusje na temat właściwości ograniczonej izometrii lub RIP . Inną przydatną stroną internetową, jeśli naprawdę chcesz zagłębić się w jakąś teorię, jest skompresowana strona wykrywająca Terence Tao .$A$$\ell_1$

Chcielibyśmy być w stanie rozwiązać

$\min \| x \|_{0}$

św

$Ax=b$

ale ten problem jest problemem optymalizacji kombinatorycznej NP-trudny jest to niemożliwe do rozwiązania w praktyce, gdy , i są w rozmiarach typowych ściskanie wykrywania. Możliwe jest skuteczne rozwiązanie$A$$x$$b$

$\min \| x \|_{1}$

św

$Ax=b$

zarówno w teorii (można to zrobić w czasie wielomianowym), jak iw praktyce obliczeniowej nawet w przypadku dość dużych problemów, które pojawiają się w wykrywaniu kompresyjnym. Używamy jako „surogat” dla . Ma to pewne intuicyjne uzasadnienie (minimalizacja jednej normy preferuje rozwiązania z mniejszą liczbą niezerowych wpisów w ), a także znacznie bardziej wyrafinowane uzasadnienia teoretyczne (twierdzenia postaci „Jeśli ma rozwiązanie k-rzadkie, to minimalizuje znajdzie to rozwiązanie z dużym prawdopodobieństwem. ” $\| x \|_{1}$$\| x \|_{0}$$x$$Ax=b$$\| x \|_{1}$

W praktyce, ponieważ dane często są zaszumione, dokładne ograniczenie jest często zastępowane ograniczeniem formy . $Ax=b$$\| Ax - b \|_{2} \leq \delta$

Dość powszechna jest również praca z wariacyjną postacią ograniczonego problemu, gdzie na przykład możemy zminimalizować .$\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$

Nie mam nic do dodania do wyjaśnienia Briansa i Michaelsa o vs. . Ale ponieważ wydaje się, że chodzi o pytanie o skompresowane wykrywanie, chciałbym dodać mój punkt widzenia: w wykrywaniu skompresowanym nie chodzi o rozwiązywanie ani o Kompresyjne wykrywanie jest bardziej paradygmatem , co można z grubsza określić jako$\ell^1$$\ell^0$

Możliwe jest zidentyfikowanie rzadkich sygnałów na podstawie kilku pomiarów.

Kompresyjne wykrywanie polega na wykonaniu jak najmniejszej liczby pomiarów w celu zidentyfikowania sygnału w pewnej klasie sygnałów.

Jedna chwytliwa fraza to:

Dlaczego 5-megapikselowy aparat powinien mierzyć 15 milionów wartości (trzy na każdy piksel), co kosztuje 15 megabajtów danych, gdy przechowuje tylko około 2 megabajtów (po kompresji)?
Czy można od razu zmierzyć 2 megabajty?

Możliwe są całkiem różne ramy:

• pomiary liniowe
• nieliniowe (np. „bezfazowe”)
• dane wektorowe, dane macierzy / tensora
• sparsity jako liczba niezerowa
• rzadkość jako „niskiej rangi” lub nawet „niskiej złożoności”).

I są też bardziej rozrzedzone metod do obliczania rozwiązań takich jak poszukiwanie dopasowujące (warianty jak prostopadłe poszukiwanie dopasowujące (OMP), uregulowany prostopadłe poszukiwanie dopasowujące (ROMP), CoSaMP) lub nowsze metody oparte na przekazywanie komunikatów algorytmów.

Jeśli ktoś rozpoznaje Compressed Sensing ze zwykłą minimalizacją - lub , traci się dużą elastyczność przy rozwiązywaniu praktycznych problemów z pozyskiwaniem danych.$\ell^1$$\ell^0$

Jeśli ktoś jest zainteresowany jedynie uzyskaniem rzadkich rozwiązań dla systemów liniowych, robi coś, co nazwałbym rzadką rekonstrukcją .