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 , mediante un enfoque de descomposición de valores singulares . k -SVD es una generalización del método de agrupamiento k -means y funciona alternando iterativamente entre codificación dispersa de los datos de entrada según el diccionario actual y actualizando 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.

k-Algoritmo SVD

k -SVD es una especie de generalización de k -medias, como sigue. La agrupación de k -medias también puede considerarse 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.}$

que 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 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 lo verdaderamente óptimo 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 escasa tarea de codificación, lo siguiente es buscar un diccionario mejor . Sin embargo, es imposible encontrar todo el diccionario a la vez, por lo que el proceso consiste en actualizar solo una columna del diccionario cada vez, mientras se corrige . La actualización de la -ésima columna 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 asumir que los otros términos se suponen 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 usando descomposición en valores singulares y luego actualizando con ella. Sin embargo, no se garantiza que la nueva solución para el vector sea escasa. ${\displaystyle DX}$ ${\displaystyle K}$ ${\displaystyle K-1}$ ${\displaystyle k}$ ${\displaystyle E_{k}}$ ${\displaystyle rank-1}$ ${\displaystyle d_{k}}$ ${\displaystyle x_{k}^{\text{T}}}$

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

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

lo que apunta a ejemplos que usan átomo (también las entradas de eso son distintas de cero). Luego, defina como una matriz de tamaño , con unos en las entradas y ceros en el resto. Al multiplicar , esto reduce el vector de fila al descartar las entradas cero. De manera similar, la multiplicación es el subconjunto de los ejemplos actuales que utilizan el átomo. El mismo efecto se puede observar 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}}$

Entonces el problema de minimización como se mencionó 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 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 y 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

Elegir un "diccionario" apropiado para un conjunto de datos es un problema no convexo y k -SVD opera 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 k -SVD funciona bastante bien en la práctica. ^{[2] [ se necesita una mejor fuente ]}

Ver también

• Aproximación escasa
• Valor singular de descomposición
• Norma matricial
• k -significa agrupamiento
• Aproximación de rango bajo

Referencias

1. Mical 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)