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ó

$\min {\mathrm{\backslash limits}}_{D,X}\{\Vert Y-DX{\Vert }_F^2\}\text{subjecte a }\mathrm{\forall }i,x_i=e_k\text{ per algun }k.$

que és gairebé equivalent a

$\min {\mathrm{\backslash limits}}_{D,X}\{\Vert Y-DX{\Vert }_F^2\}\text{subjecte a }\mathrm{\forall }i,\Vert x_i{\Vert }_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.