K-SVD

En matemàtiques aplicades, k-SVD és un algorisme d'aprenentatge de diccionari per crear un diccionari per a representacions escasses, mitjançant un enfocament de descomposició de valors singular. k-SVD és una generalització del mètode de agrupació k -means i funciona alternant iterativament entre la codificació escassa de les dades d'entrada basades en el diccionari actual i l'actualització dels àtoms del diccionari per adaptar-se millor a les dades. Està estructuralment relacionat amb l'algorisme de maximització de l'expectativa (EM). k -SVD es pot trobar àmpliament utilitzat en aplicacions com el processament d'imatges, processament d'àudio, biologia i anàlisi de documents.

Algorisme k-SVD

k -SVD és una mena de generalització de k -means, de la següent manera. La agrupació de k -means també es pot considerar com un mètode de representació escassa. És a dir, trobar el millor llibre de codis possible per representar les mostres de dades $\{y_{i}\}_{i=1}^{M}$ pel veí més proper, per resolució

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subjecte a }}\forall i,x_{i}=e_{k}{\text{ per algun }}k.$

que és gairebé equivalent a

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subjecte a }}\quad \forall i,\|x_{i}\|_{0}=1$

La lletra F denota la norma Frobenius. El terme de representació escàs $x_{i}=e_{k}$ imposa l'algorisme k -significa per utilitzar només un àtom (columna) al diccionari $D$. Per relaxar aquesta restricció, l'objectiu de l'algorisme k -SVD és representar el senyal com una combinació lineal d'àtoms en $D$.

Limitacions

Escollir un "diccionari" adequat per a un conjunt de dades és un problema no convex, i k -SVD funciona mitjançant una actualització iterativa que no garanteix trobar l'òptim global. Tanmateix, això és comú a altres algorismes per a aquest propòsit, i k -SVD funciona bastant bé a la pràctica.