k -SVD

W matematyce stosowanej k -SVD jest algorytmem uczenia się słownika służącym do tworzenia słownika dla rzadkich reprezentacji za pomocą metody dekompozycji wartości osobliwych . k -SVD jest uogólnieniem metody grupowania k -średnich i działa poprzez iteracyjne naprzemienne kodowanie danych wejściowych w oparciu o bieżący słownik i aktualizowanie atomów w słowniku w celu lepszego dopasowania do danych. Jest strukturalnie powiązany z maksymalizacją oczekiwań algorytm (EM). k -SVD można znaleźć w wielu zastosowaniach, takich jak przetwarzanie obrazu, przetwarzanie dźwięku, biologia i analiza dokumentów.

Algorytm k -SVD

k -SVD jest rodzajem uogólnienia k -średnich w następujący sposób. Grupowanie k -średnich może być również traktowane jako metoda rzadkiej reprezentacji . $że$ znalezienie najlepszego możliwego próbek przez najbliższego

{\ Displaystyle \ quad \ min \ limity _ {D, X} \ {\| Y-DX \ | _ {F} ^ {2} \} \ qquad {\ tekst {z zastrzeżeniem}} \ forall i, x_ { i}=e_{k}{\text{ dla pewnego }}k.}

co jest prawie równoważne

{\ Displaystyle \ quad \ min \ ograniczenia _ {D, X} \ {\| Y-DX \ |_ {F}^{2}\}\qquad {\text{z zastrzeżeniem}}\quad \forall i,\|x_{i}\|_{0}=1}

czyli k- oznacza, że pozwala na „wagę”.

Litera F oznacza normę Frobeniusa . Rzadki termin reprezentacji wymusza algorytm k-średnich, aby $jednego$ tylko $($ ) Aby złagodzić to ograniczenie, celem algorytmu k -SVD jest przedstawienie sygnału jako liniowej kombinacji $atomów$ .

Algorytm k -SVD podąża za przepływem konstrukcyjnym algorytmu k -średnich. $\ displaystyle x_ {i}}$ w przeciwieństwie do k - oznacza, aby osiągnąć liniową kombinację atomów w $re$ rzadki składnik ograniczenia jest rozluźniony, tak że liczba niezerowych wpisów w każdej kolumnie jest może być większy niż 1, ale mniejszy niż liczba ${\ displaystyle T_ {0}}$ .

Tak więc funkcja celu staje się

{\ Displaystyle \ quad \ min \ limity _ {D, X} \ {\| Y-DX \ | _ {F} ^ {2} \} \ qquad {\ tekst {z zastrzeżeniem}} \ quad \ forall i \ ;,\|x_{i}\|_{0}\równoważnik T_{0}.}

lub w innej obiektywnej formie

{\ Displaystyle \ quad \ min \ limity _ {D, X} \ suma _ {i} \ | x_ {i} \ | _ {0} \ qquad {\ tekst {z zastrzeżeniem}} \ quad \ forall i \; ,\|Y-DX\|_{F}^{2}\równik \epsilon .}

W algorytmie k $ustala się i$ $najpierw$ znajduje najlepszą macierz współczynników Ponieważ znalezienie naprawdę optymalnego $jest$ , używamy metody dążenia do przybliżenia. Do obliczenia współczynników można użyć dowolnego algorytmu, takiego jak OMP, pogoń za dopasowaniem ortogonalnym , o ile może dostarczyć rozwiązanie ze stałą i z góry określoną liczbą niezerowych wpisów. ${\ displaystyle T_ {0}}$ .

$Po$ rzadkim zadaniu kodowania następnym jest poszukiwanie lepszego . $naprawianiu$ znalezienie całego słownika naraz jest niemożliwe, więc proces polega na aktualizacji tylko jednej kolumny słownika za $każdym$ razem, przy . Aktualizacja $przepisanie$ kary jako

{\ Displaystyle \| Y-DX \|_ {F} ^ {2} = \ lewo \| Y- \ suma _ {j = 1} ^ {K} d_ {j} x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\suma _{j\neq k}d_{j}x_{j }^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_ {k}x_{k}^{\text{T}}\|_{F}^{2}}

gdzie ${\ Displaystyle x_ {k} ^ {\ tekst {T}}}$ oznacza k -ty rząd X .

Rozkładając mnożenie na sumę macierzy $rangi$ $1$ , możemy założyć, że inne $K}$ k $k}$ $displaystyle$ -ty pozostaje nieznany. Po ${\ Displaystyle rank-1}$ kroku możemy rozwiązać problem minimalizacji przez przybliżenie $terminu$ z macierz za pomocą $rozkładu$ wartości osobliwe , a następnie zaktualizuj . Jednak nowe rozwiązanie wektora $bardzo prawdopodobne$ że zostanie wypełnione, ponieważ ograniczenie rzadkości nie jest wymuszane

Aby rozwiązać ten problem, zdefiniuj jako ${\ displaystyle \ omega _ {k}}$

{\ Displaystyle \ omega _ {k} = \ {i \ mid 1 \ równoważnik ja \ równoważnik N, x_ {k} ^ { \text{T}}(i)\neq 0\},}

$_$ wskazuje na $_$ _ wpisy $.$ które są niezerowe Następnie zdefiniuj $rozmiarze$ o ${\ Displaystyle N \ razy |\ omega _ {k}|}$ , z jedynkami na ${\ Displaystyle (i, \ omega _ {k} (i)} {\ tekst {th}}}$ wpisy i zera w przeciwnym razie. Podczas mnożenia ${\ Displaystyle {\ tylda {x}} _ {k} ^ {\ tekst {T}} = x_ {k} ^ {\ tekst {T}} \ Omega _ {k}}$ , to zmniejsza wektor wierszy $odrzucając$ zerowe Podobnie mnożenie $jest$ podzbiorem przykładów, które $.$ użyciu $_$ zobaczyć _

Tak więc problem minimalizacji, jak wspomniano wcześniej, staje się

{\ Displaystyle \|E_ {k} \ Omega _ {k} -d_ {k }x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tylda {E}}_{k}-d_{k}{\ tylda {x}}_{k}^{\text{T}}\|_{F}^{2}}

i można to zrobić bezpośrednio za pomocą SVD. SVD rozkłada się na $T}}}$ $Δ$ \ Delta Rozwiązaniem dla jest pierwsza kolumna U, wektor współczynnika ${ x}} _ {k} ^ {$ $tekst {T}}}$ jako pierwsza kolumna ${\ Displaystyle V \ razy \ delta (1,1)}$ . Po zaktualizowaniu całego słownika proces przechodzi następnie do iteracyjnego rozwiązania X, a następnie iteracyjnego rozwiązania D.

Ograniczenia

Wybór odpowiedniego „słownika” dla zbioru danych nie jest problemem wypukłym, a k -SVD działa na zasadzie iteracyjnej aktualizacji, która nie gwarantuje znalezienia globalnego optimum. Jest to jednak wspólne dla innych algorytmów do tego celu, a k -SVD działa całkiem dobrze w praktyce. ^{[ potrzebne lepsze źródło ]}

Zobacz też

Bibliografia _ _ Michał Elad; Alfred Bruckstein (2006), „K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation” (PDF) , IEEE Transactions on Signal Processing , 54 (11): 4311–4322, Bibcode : 2006ITSP ... 54.4311A , doi : 10.1109/TSP.2006.881199 , S2CID 7477309
Referencje ^_^_^_ _ _ _ _ _ _ _ , doi : 10.1109/JPROC.2010.2040551 , S2CID 2176046 {{ cytat }} : CS1 maint: wiele nazw: lista autorów ( link )

[aharon2006-1] Bibliografia _ _ Michał Elad; Alfred Bruckstein (2006), „K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation” (PDF) , IEEE Transactions on Signal Processing , 54 (11): 4311–4322, Bibcode : 2006ITSP ... 54.4311A , doi : 10.1109/TSP.2006.881199 , S2CID 7477309

[rubinstein2010-2] Referencje ^_^_^_ _ _ _ _ _ _ _ , doi : 10.1109/JPROC.2010.2040551 , S2CID 2176046 {{ cytat }} : CS1 maint: wiele nazw: lista autorów ( link )