k-SVD

Algoritmo de aprendizaje de diccionario

En matemáticas aplicadas , k -SVD es un algoritmo de aprendizaje de diccionario para crear un diccionario para representaciones dispersas , a través de un enfoque de descomposición en valores singulares . k -SVD es una generalización del método de agrupamiento k -means , y funciona alternando iterativamente entre la codificación dispersa de los datos de entrada según el diccionario actual y la actualización de los átomos en el diccionario para que se ajusten mejor a los datos. Está estructuralmente relacionado con el algoritmo de expectativa-maximización (EM) . ^{[1] [2]} k -SVD se puede encontrar ampliamente en uso en aplicaciones como procesamiento de imágenes, procesamiento de audio, biología y análisis de documentos.

a-Algoritmo SVD

La k -SVD es un tipo de generalización de k -medias, como se indica a continuación. La agrupación de k -medias también se puede considerar como un método de representación dispersa . Es decir, encontrar el mejor libro de códigos posible para representar las muestras de datos por vecino más cercano , resolviendo ${\displaystyle \{y_{i}\}_{i=1}^{M}}$

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.}$

lo cual es casi equivalente a

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

que es k-means que permite "pesos".

La letra F denota la norma de Frobenius . El término de representación dispersa obliga al algoritmo k -means a utilizar solo un átomo (columna) en el diccionario . Para relajar esta restricción, el objetivo del algoritmo k -SVD es representar la señal como una combinación lineal de átomos en . ${\displaystyle x_{i}=e_{k}}$ ${\displaystyle D}$ ${\displaystyle D}$

El algoritmo k -SVD sigue el flujo de construcción del algoritmo k -means. Sin embargo, a diferencia de k -means, para lograr una combinación lineal de átomos en , el término de escasez de la restricción se relaja de modo que el número de entradas distintas de cero de cada columna puede ser mayor que 1, pero menor que un número . ${\displaystyle D}$ ${\displaystyle x_{i}}$ ${\displaystyle T_{0}}$

Entonces, la función objetivo se convierte en

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.}$

o en otra forma objetiva

${\displaystyle \quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .}$

En el algoritmo k -SVD, primero se fija y se encuentra la mejor matriz de coeficientes . Como encontrar la matriz verdaderamente óptima es difícil, utilizamos un método de búsqueda de aproximación. Cualquier algoritmo como OMP, la búsqueda de coincidencia ortogonal , se puede utilizar para el cálculo de los coeficientes, siempre que pueda proporcionar una solución con un número fijo y predeterminado de entradas distintas de cero . ${\displaystyle D}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle T_{0}}$

Después de la tarea de codificación dispersa, el siguiente paso es buscar un diccionario mejor . Sin embargo, encontrar todo el diccionario a la vez es imposible, por lo que el proceso consiste en actualizar solo una columna del diccionario cada vez, mientras se repara . La actualización de la columna -ésima se realiza reescribiendo el término de penalización como ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle X}$ ${\displaystyle k}$

${\displaystyle \|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{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}}$

donde denota la k -ésima fila de X. ${\displaystyle x_{k}^{\text{T}}}$

Al descomponer la multiplicación en la suma de matrices de rango 1, podemos suponer que los demás términos se consideran fijos y que el -ésimo permanece desconocido. Después de este paso, podemos resolver el problema de minimización aproximando el término con una matriz mediante descomposición en valores singulares y luego actualizando con ella. Sin embargo, no se garantiza que la nueva solución para el vector sea dispersa. ${\displaystyle DX}$ ${\displaystyle K}$ ${\displaystyle K-1}$ ${\displaystyle k}$ ${\displaystyle E_{k}}$ ${\displaystyle rank-1}$ ${\displaystyle d_{k}}$ ${\displaystyle x_{k}^{\text{T}}}$

Para solucionar este problema, defina como ${\displaystyle \omega _{k}}$

${\displaystyle \omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},}$

que apunta a ejemplos que usan atom (también las entradas de que no es cero). Luego, defina como una matriz de tamaño , con unos en las entradas y ceros en el resto. Al multiplicar , esto encoge el vector de fila descartando las entradas cero. De manera similar, la multiplicación es el subconjunto de los ejemplos que están en uso actualmente usando el átomo. El mismo efecto se puede ver en . ${\displaystyle \{y_{i}\}_{i=1}^{N}}$ ${\displaystyle d_{k}}$ ${\displaystyle x_{i}}$ ${\displaystyle \Omega _{k}}$ ${\displaystyle N\times |\omega _{k}|}$ ${\displaystyle (i,\omega _{k}(i)){\text{th}}}$ ${\displaystyle {\tilde {x}}_{k}^{\text{T}}=x_{k}^{\text{T}}\Omega _{k}}$ ${\displaystyle x_{k}^{\text{T}}}$ ${\displaystyle {\tilde {Y}}_{k}=Y\Omega _{k}}$ ${\displaystyle d_{k}}$ ${\displaystyle {\tilde {E}}_{k}=E_{k}\Omega _{k}}$

Por lo tanto, el problema de minimización mencionado anteriormente se convierte en

${\displaystyle \|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}}$

y se puede hacer directamente usando SVD. SVD se descompone en . La solución para es la primera columna de U, el vector de coeficientes como la primera columna de . Después de actualizar todo el diccionario, el proceso pasa a resolver iterativamente X, luego a resolver iterativamente D. ${\displaystyle {\tilde {E}}_{k}}$ ${\displaystyle U\Delta V^{\text{T}}}$ ${\displaystyle d_{k}}$ ${\displaystyle {\tilde {x}}_{k}^{\text{T}}}$ ${\displaystyle V\times \Delta (1,1)}$

Limitaciones

La elección de un "diccionario" apropiado para un conjunto de datos es un problema no convexo, y el k -SVD funciona mediante una actualización iterativa que no garantiza encontrar el óptimo global. ^[2] Sin embargo, esto es común a otros algoritmos para este propósito, y el k -SVD funciona bastante bien en la práctica. ^{[2] [ se necesita una mejor fuente ]}

Véase también

• Aproximación dispersa
• Descomposición en valores singulares
• Norma de matriz
• Agrupamiento de k -medias
• Aproximación de bajo rango

Referencias

1. Michal Aharon ; Michael Elad; Alfred Bruckstein (2006), "K-SVD: Un algoritmo para diseñar diccionarios sobrecompletos para representación dispersa" (PDF) , IEEE Transactions on Signal Processing , 54 (11): 4311–4322, Bibcode :2006ITSP...54.4311A, doi :10.1109/TSP.2006.881199, S2CID  7477309
2. Rubinstein, R., Bruckstein, AM y Elad, M. (2010), "Diccionarios para modelado de representación dispersa", Actas del IEEE , 98 (6): 1045–1057, CiteSeerX 10.1.1.160.527 , doi :10.1109/JPROC.2010.2040551, S2CID  2176046 {{citation}}: CS1 maint: multiple names: authors list (link)