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).^[1][2] k -SVD es pot trobar àmpliament utilitzat en aplicacions com el processament d'imatges, processament d'àudio, biologia i anàlisi de documents.^[3]

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 ${\displaystyle \{y_{i}\}_{i=1}^{M}}$ pel veí més proper, per resolució

${\displaystyle \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

${\displaystyle \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 ${\displaystyle x_{i}=e_{k}}$ imposa l'algorisme k -significa per utilitzar només un àtom (columna) al diccionari ${\displaystyle D}$. Per relaxar aquesta restricció, l'objectiu de l'algorisme k -SVD és representar el senyal com una combinació lineal d'àtoms en ${\displaystyle 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.^[4] Tanmateix, això és comú a altres algorismes per a aquest propòsit, i k -SVD funciona bastant bé a la pràctica.^[4]

Referències

1. Michal Aharon; Michael Elad & Alfred Bruckstein (2006), "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation", IEEE Transactions on Signal Processing 54 (11): 4311–4322, doi:10.1109/TSP.2006.881199, <https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/32_KSVD_IEEE_TSP.pdf>
2. Rubinstein, R., Bruckstein, A.M., and Elad, M. (2010), "Dictionaries for Sparse Representation Modeling", Proceedings of the IEEE 98 (6): 1045–1057, DOI 10.1109/JPROC.2010.2040551
3. Aharon, M.; Elad, M.; Bruckstein, A. «K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation». IEEE Transactions on Signal Processing, 54, 11, 11-2006, pàg. 4311–4322. DOI: 10.1109/TSP.2006.881199. ISSN: 1941-0476.
4. Rubinstein, R., Bruckstein, A.M., and Elad, M. (2010), "Dictionaries for Sparse Representation Modeling", Proceedings of the IEEE 98 (6): 1045–1057, DOI 10.1109/JPROC.2010.2040551