Rzadkie przybliżenie - Sparse approximation

Teoria rzadkiego przybliżenia (znana również jako rzadka reprezentacja ) zajmuje się rzadkimi rozwiązaniami układów równań liniowych . Techniki znalezienie tych rozwiązań i wykorzystywanie ich w aplikacjach znalazły szerokie zastosowanie w przetwarzaniu obrazu , przetwarzania sygnałów , uczenia maszynowego , obrazowania medycznego i innych.

Rzadki rozkład

Bezgłośne obserwacje

Rozważmy liniowy układ równań , gdzie jest nieoznaczoną macierzą i . Macierz (zwykle przyjmuje się, że jest to pełna ranga) jest określana jako słownik i jest sygnałem zainteresowania. Rdzeń problemu rzadkiej reprezentacji jest zdefiniowany jako poszukiwanie możliwie najrzadszej reprezentacji satysfakcjonującej . Ze względu na niedookreśloną naturę , ten układ liniowy dopuszcza na ogół nieskończenie wiele możliwych rozwiązań, a wśród nich poszukujemy takiego z najmniejszą liczbą niezerów. Mówiąc formalnie, rozwiązujemy ${\displaystyle x=d\alfa}$${\ Displaystyle D}$ ${\displaystyle m\razy p}$ ${\ Displaystyle (m<p)}$${\ Displaystyle x \ w \ mathbb {R} ^ {m} \ alfa \ w \ mathbb {R} ^ {p}}$${\ Displaystyle D}$${\displaystyle x}$${\ Displaystyle \ alfa}$${\displaystyle x=d\alfa}$${\ Displaystyle D}$

${\ Displaystyle \ min _ {\ alfa \ w \ mathbb {R} ^ {p}} \ | \ alfa \ | _ {0}{\ tekst {z zastrzeżeniem}} x = D \ alfa}$

gdzie jest pseudo-normą, która zlicza liczbę niezerowych składników . Wiadomo, że problem ten jest NP-trudny z redukcją do problemów selekcji podzbiorów NP-kompletnych w optymalizacji kombinatorycznej . ${\ Displaystyle \ | \ alfa \ | _ {0} = \ # \ {i: \ alfa _ {i} \ neq 0 \, i = 1 \ ldots, p \}}$${\displaystyle \ell_{0}}$${\ Displaystyle \ alfa}$

Rzadkość oznacza, że ​​tylko kilka ( ) składników jest niezerowych. Motywacją leżącą u podstaw tak rzadkiego rozkładu jest chęć dostarczenia możliwie najprostszego wyjaśnienia jako liniowej kombinacji jak najmniejszej liczby kolumn z , zwanych również atomami. Jako taki sygnał może być postrzegany jako cząsteczka złożona z kilku podstawowych elementów pobranych z . ${\ Displaystyle \ alfa}$${\displaystyle k\ll m<p}$${\displaystyle x}$${\ Displaystyle D}$${\displaystyle x}$${\ Displaystyle D}$

Chociaż postawiony powyżej problem jest rzeczywiście NP-trudny, jego rozwiązanie często można znaleźć za pomocą algorytmów aproksymacyjnych. Jedną z takich opcji jest wypukłe rozluźnienie problemu, uzyskane za pomocą -normy zamiast , gdzie po prostu sumuje się wartości bezwzględne wpisów w . Jest to znane jako algorytm poszukiwania podstawy (BP), który może być obsługiwany za pomocą dowolnego solwera programowania liniowego . Alternatywną metodą aproksymacji jest technika zachłanna, taka jak pogoń za dopasowywaniem (MP), która znajduje położenie niezerów pojedynczo. ${\displaystyle \ell_{1}}$${\displaystyle \ell_{0}}$${\displaystyle \|\alfa \|_{1}}$${\ Displaystyle \ alfa}$

Co zaskakujące, w łagodnych warunkach (przy użyciu iskry (matematyka) , wzajemnej koherencji lub ograniczonej własności izometrii ) i poziomie rzadkości w rozwiązaniu , można wykazać, że problem rzadkiej reprezentacji ma unikalne rozwiązanie, a BP i MP gwarantujemy, że znajdziesz to doskonale. ${\ Displaystyle D}$${\displaystyle k}$

Zaszumione obserwacje

Często obserwowany sygnał jest zaszumiony. Rozluźniając ograniczenie równości i nakładając normę na termin dopasowania danych, problem rzadkiej dekompozycji staje się ${\displaystyle x}$${\displaystyle \ell_{2}}$

${\ Displaystyle \ min _ {\ alfa \ w \ mathbb {R} ^ {p}} \ | \ alfa \ | _ {0}{\ tekst {z zastrzeżeniem}} \ | xD \ alfa \ | _ {2} ^{2}\leq \epsilon ^{2},}$

lub w formie Lagrange'a,

${\ Displaystyle \ min _ {\ alfa \ w \ mathbb {R} ^ {p}} \ lambda \ | \ alfa \ | _ {0} + {\ Frac {1} {2}} \ | xD \ alfa \ |_{2}^{2},}$

gdzie jest zastąpienie . ${\ Displaystyle \ lambda}$${\displaystyle \epsilon}$

Podobnie jak w przypadku bezszumowym, te dwa problemy są ogólnie NP-Hard, ale można je przybliżyć za pomocą algorytmów pościgowych. Dokładniej, zmieniając do -norm, otrzymujemy ${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

${\ Displaystyle \ min _ {\ alfa \ w \ mathbb {R} ^ {p}} \ lambda \ | \ alfa \ | _ {1} + {\ Frac {1} {2}} \ | xD \ alfa \ |_{2}^{2},}$

który jest znany jako odszumianie podstawy pogoni . Podobnie, poszukiwanie dopasowania może być użyte do aproksymacji rozwiązania powyższych problemów, odnajdując lokalizacje wartości niezerowych pojedynczo, aż do osiągnięcia progu błędu. Również tutaj teoretyczne gwarancje sugerują, że BP i MP prowadzą do prawie optymalnych rozwiązań w zależności od właściwości i kardynalności rozwiązania . Inny interesujący wynik teoretyczny dotyczy przypadku, w którym jest unitarny. Przy tym założeniu problemy postawione powyżej (z albo lub ) dopuszczają rozwiązania w postaci zamkniętej w postaci skurczu nieliniowego. ${\ Displaystyle D}$${\displaystyle k}$${\ Displaystyle D}$${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

Wariacje

Istnieje kilka odmian podstawowego problemu z rzadkimi przybliżeniami.

Ustrukturyzowana rzadkość : W oryginalnej wersji problemu można wybrać dowolny atom ze słownika. W ustrukturyzowanym (blokowym) modelu rzadkości, zamiast pojedynczo wybierać atomy, wybierane są ich grupy. Grupy te mogą zachodzić na siebie i mieć różną wielkość. Celem jest reprezentacja tak, że jest rzadka, jednocześnie wymuszając tę ​​strukturę blokową. ${\displaystyle x}$

Wspólne (wspólne) kodowanie rzadkie : Oryginalna wersja problemu jest zdefiniowana dla pojedynczego sygnału . W kolaboracyjnym (wspólnym) modelu kodowania rzadkiego dostępny jest zestaw sygnałów, z których każdy, jak się uważa, pochodzi z (prawie) tego samego zestawu atomów z . W tym przypadku zadanie pościgu ma na celu odzyskanie zestawu rzadkich reprezentacji, które najlepiej opisują dane, jednocześnie zmuszając je do współdzielenia tego samego (lub bliskiego) wsparcia. ${\displaystyle x}$${\ Displaystyle D}$

Inne struktury : Mówiąc szerzej, problem rzadkich aproksymacji można rzucić, wymuszając określoną pożądaną strukturę na wzorze niezerowych lokalizacji w . Dwa interesujące przypadki, które zostały szeroko zbadane, to struktura oparta na drzewie, a bardziej ogólnie, wsparcie rozproszone Boltzmanna. ${\ Displaystyle \ alfa}$

Algorytmy

Jak już wspomniano powyżej, istnieją różne algorytmy aproksymacji (zwane także pogonią ), które zostały opracowane w celu rozwiązania problemu rzadkiej reprezentacji:

${\ Displaystyle \ min _ {\ alfa \ w \ mathbb {R} ^ {p}} \ | \ alfa \ | _ {0}{\ tekst {z zastrzeżeniem}} \ | xD \ alfa \ | _ {2} ^{2}\leq \epsilon ^{2}.}$

Poniżej wymieniamy kilka z tych głównych metod.

• Pogoń za dopasowaniem to zachłanny algorytm iteracyjny służący do przybliżonego rozwiązania powyższego problemu. Działa poprzez stopniowe znajdowanie lokalizacji niezerowych po jednym na raz. Podstawową ideą jest znalezienie na każdym kroku kolumny (atomu), która najlepiej koreluje z bieżącą resztą (zainicjowaną do ), a następnie zaktualizowanie tej reszty w celu uwzględnienia nowego atomu i jego współczynnika. Pasujące pogoń może wielokrotnie wybrać ten sam atom.${\ Displaystyle \ alfa}$${\ Displaystyle D}$${\displaystyle x}$
• Ortogonalne poszukiwanie dopasowania jest bardzo podobne do poszukiwania dopasowania, z jedną zasadniczą różnicą: w każdym kroku algorytmu wszystkie niezerowe współczynniki są aktualizowane o wartość najmniejszych kwadratów . W konsekwencji reszta jest prostopadła do już wybranych atomów, a zatem atomu nie można wybrać więcej niż raz.
• Metody zachłanne etapowe: ulepszone warianty w stosunku do powyższych to algorytmy, które działają zachłannie, jednocześnie dodając dwie krytyczne cechy: (i) możliwość dodawania grup niezerowych na raz (zamiast jednej wartości niezerowej na rundę); oraz (ii) zawiera etap przycinania w każdej rundzie, w którym kilka atomów jest odrzucanych z nośnika. Reprezentantami tego podejścia są algorytm Subspace-Pursuit oraz CoSaMP.

• Pogoń za podstawą rozwiązuje wypukłą, rozluźnioną wersję problemu, zastępując ją przez -normę. Zauważ, że definiuje to tylko nowy cel, pozostawiając otwartą kwestię algorytmu, który ma zostać użyty do uzyskania pożądanego rozwiązania. Powszechnie uważane za takie algorytmy to IRLS , LARS , i iteracyjne metody miękkiego skurczu.${\displaystyle \ell_{0}}$${\displaystyle \ell_{1}}$

• Istnieje kilka innych metod rozwiązywania rzadkich problemów z rozkładem: metoda homotopii, zejście współrzędnych , iteracyjne hard-thresholding, metody proksymalne pierwszego rzędu , które są powiązane z wyżej wymienionymi iteracyjnymi algorytmami miękkiego kurczenia oraz selektor Dantzig.

Aplikacje

Nieliczne wolne zbliżanie i algorytmy zostały szeroko stosowane w przetwarzaniu sygnałów , przetwarzanie obrazu , uczenia maszynowego , obrazowania medycznego , przetwarzania tablicy , eksploracji danych i wiele innych. W większości tych aplikacji nieznany sygnał będący przedmiotem zainteresowania jest modelowany jako rzadka kombinacja kilku atomów z danego słownika, co jest wykorzystywane jako uregulowanie problemu. Problemom tym zazwyczaj towarzyszy mechanizm uczenia słownikowego , który ma na celu jak najlepsze dopasowanie modelu do danych. Wykorzystanie modeli inspirowanych rzadkością doprowadziło do uzyskania najnowocześniejszych wyników w szerokim zestawie zastosowań. Ostatnie prace sugerują, że istnieje ścisły związek między modelowaniem rzadkiej reprezentacji a uczeniem głębokim. ${\ Displaystyle D}$

Zobacz też

• Skompresowane wykrywanie
• Rzadkie uczenie się słownika
• K-SVD
• Lasso (statystyki)
• Regularyzacja (matematyka) i problemy odwrotne

Bibliografia