Aproximación dispersa

La teoría de aproximación dispersa (también conocida como representación dispersa ) se ocupa de soluciones dispersas para sistemas de ecuaciones lineales . Las técnicas para encontrar estas soluciones y explotarlas en aplicaciones han encontrado un amplio uso en el procesamiento de imágenes , el procesamiento de señales , el aprendizaje automático , las imágenes médicas y más.

Descomposición dispersa

Observaciones sin ruido

Consideremos un sistema lineal de ecuaciones , donde es una matriz indeterminada y . La matriz (que normalmente se supone que es de rango completo) se conoce como el diccionario y es una señal de interés. El problema central de la representación dispersa se define como la búsqueda de la representación más dispersa posible que satisfaga . Debido a la naturaleza indeterminada de , este sistema lineal admite en general infinitas soluciones posibles, y entre ellas buscamos la que tenga la menor cantidad de números distintos de cero. Dicho formalmente, resolvemos ${\displaystyle x=D\alpha }$ ${\displaystyle D}$ ${\displaystyle m\times p}$ ${\displaystyle (m<p)}$ ${\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}$ ${\displaystyle D}$ ${\displaystyle x}$ ${\displaystyle \alpha }$ ${\displaystyle x=D\alpha }$ ${\displaystyle D}$

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}x=D\alpha ,}$

donde es la pseudonorma, que cuenta el número de componentes distintos de cero de . Se sabe que este problema es NP-completo con una reducción a problemas de selección de subconjuntos NP-completos en optimización combinatoria . ${\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle \alpha }$

La escasez de implica que solo unos pocos ( ) componentes en ella son distintos de cero. La motivación subyacente para una descomposición tan dispersa es el deseo de proporcionar la explicación más simple posible de como una combinación lineal de la menor cantidad posible de columnas de , también denominadas átomos. Como tal, la señal puede verse como una molécula compuesta de unos pocos elementos fundamentales tomados de . ${\displaystyle \alpha }$ ${\displaystyle k\ll m<p}$ ${\displaystyle x}$ ${\displaystyle D}$ ${\displaystyle x}$ ${\displaystyle D}$

Si bien el problema planteado anteriormente es de hecho NP-Hard, su solución a menudo se puede encontrar utilizando algoritmos de aproximación. Una de esas opciones es una relajación convexa del problema, obtenida utilizando la norma en lugar de , donde simplemente suma los valores absolutos de las entradas en . Esto se conoce como el algoritmo de búsqueda de base (BP), que se puede manejar utilizando cualquier solucionador de programación lineal . Un método de aproximación alternativo es una técnica voraz, como la búsqueda de coincidencia (MP), que encuentra la ubicación de los valores distintos de cero de a uno por vez. ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle \|\alpha \|_{1}}$ ${\displaystyle \alpha }$

Sorprendentemente, en condiciones moderadas (utilizando la chispa (matemáticas) , la coherencia mutua o la propiedad de isometría restringida ) y el nivel de escasez en la solución, , se puede demostrar que el problema de representación dispersa tiene una solución única, y se garantiza que BP y MP la encontrarán perfectamente. ^{[1] [2] [3]} ${\displaystyle D}$ ${\displaystyle k}$

Observaciones ruidosas

A menudo, la señal observada es ruidosa. Al relajar la restricción de igualdad e imponer una norma en el término de ajuste de datos, el problema de descomposición dispersa se convierte en ${\displaystyle x}$ ${\displaystyle \ell _{2}}$

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2},}$

o ponerlo en forma lagrangiana,

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{0}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},}$

¿Dónde está el reemplazo ? ${\displaystyle \lambda }$ ${\displaystyle \epsilon }$

Al igual que en el caso sin ruido, estos dos problemas son NP-difíciles en general, pero se pueden aproximar utilizando algoritmos de búsqueda. Más específicamente, cambiando a una norma -, obtenemos ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},}$

que se conoce como eliminación de ruido por búsqueda de base . De manera similar, la búsqueda de coincidencia se puede utilizar para aproximar la solución de los problemas anteriores, encontrando las ubicaciones de los valores distintos de cero uno a la vez hasta que se alcanza el umbral de error. Aquí también, las garantías teóricas sugieren que BP y MP conducen a soluciones casi óptimas dependiendo de las propiedades de y la cardinalidad de la solución . ^{[4] [5] [6]} Otro resultado teórico interesante se refiere al caso en el que es una matriz unitaria . Bajo este supuesto, los problemas planteados anteriormente (con o ) admiten soluciones de forma cerrada en forma de contracción no lineal. ^[4] ${\displaystyle D}$ ${\displaystyle k}$ ${\displaystyle D}$ ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$

Variaciones

Existen varias variaciones del problema básico de aproximación dispersa.

Rareza estructurada : en la versión original del problema, se puede elegir cualquiera de los átomos del diccionario. En el modelo de escasez estructurada (en bloques), en lugar de elegir átomos individualmente, se deben elegir grupos de ellos. Estos grupos pueden superponerse y ser de tamaño variable. El objetivo es representar de forma que sea escasa y al mismo tiempo forzar esta estructura en bloques. ^[7] ${\displaystyle x}$

Codificación dispersa colaborativa (conjunta) : la versión original del problema se define para una sola señal . En el modelo de codificación dispersa colaborativa (conjunta), hay un conjunto de señales disponibles, cada una de las cuales se cree que surge del (casi) mismo conjunto de átomos de . En este caso, la tarea de búsqueda tiene como objetivo recuperar un conjunto de representaciones dispersas que describan mejor los datos mientras se las obliga a compartir el mismo soporte (o uno cercano). ^[8] ${\displaystyle x}$ ${\displaystyle D}$

Otras estructuras : En términos más generales, el problema de aproximación dispersa se puede plantear al mismo tiempo que se fuerza una estructura deseada específica en el patrón de ubicaciones distintas de cero en . Dos casos de interés que se han estudiado ampliamente son la estructura basada en árboles y, de manera más general, un soporte distribuido de Boltzmann. ^[9] ${\displaystyle \alpha }$

Algoritmos

Como ya se mencionó anteriormente, existen varios algoritmos de aproximación (también denominados de búsqueda ) que se han desarrollado para abordar el problema de representación dispersa:

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2}.}$

Mencionamos a continuación algunos de estos métodos principales.

• La búsqueda de coincidencias es un algoritmo iterativo voraz para resolver aproximadamente el problema anterior. Funciona al encontrar gradualmente las ubicaciones de los valores distintos de cero en uno a la vez. La idea central es encontrar en cada paso la columna (átomo) en que mejor se correlaciona con el residuo actual (inicializado a ), y luego actualizar este residuo para tener en cuenta el nuevo átomo y su coeficiente. La búsqueda de coincidencias puede elegir el mismo átomo varias veces. ${\displaystyle \alpha }$ ${\displaystyle D}$ ${\displaystyle x}$
• La búsqueda de coincidencias ortogonales es muy similar a la búsqueda de coincidencias, con una diferencia importante: en cada uno de los pasos del algoritmo, todos los coeficientes distintos de cero se actualizan mediante un método de mínimos cuadrados . Como consecuencia, el residuo es ortogonal a los átomos ya elegidos y, por lo tanto, un átomo no se puede elegir más de una vez.
• Métodos voraces por etapas: variaciones mejoradas de los anteriores son algoritmos que operan vorazmente pero que agregan dos características críticas: (i) la capacidad de agregar grupos de átomos distintos de cero a la vez (en lugar de un átomo distinto de cero por ronda); y (ii) incluir un paso de poda en cada ronda en el que se descartan varios de los átomos del soporte. Representantes de este enfoque son el algoritmo Subspace-Pursuit y el CoSaMP. ^[10]

• La búsqueda de bases resuelve una versión relajada convexa del problema reemplazando por una norma. Nótese que esto solo define un nuevo objetivo, mientras que deja abierta la cuestión del algoritmo a utilizar para obtener la solución deseada. Los algoritmos comúnmente considerados son IRLS , LARS y los métodos iterativos de contracción suave. ^[11] ${\displaystyle \ell _{0}}$ ${\displaystyle \ell _{1}}$

• Existen otros métodos para resolver problemas de descomposición dispersa: el método de homotopía, el descenso de coordenadas , el umbral duro iterativo, los métodos proximales de primer orden , que están relacionados con los algoritmos iterativos de contracción suave mencionados anteriormente, y el selector Dantzig.

Aplicaciones

Las ideas y algoritmos de aproximación dispersa se han utilizado ampliamente en el procesamiento de señales , procesamiento de imágenes , aprendizaje automático , imágenes médicas , procesamiento de matrices , minería de datos y más. En la mayoría de estas aplicaciones, la señal desconocida de interés se modela como una combinación dispersa de unos pocos átomos de un diccionario dado, y esto se utiliza como la regularización del problema. Estos problemas suelen ir acompañados de un mecanismo de aprendizaje de diccionario que tiene como objetivo ajustar lo mejor posible el modelo a los datos dados. El uso de modelos inspirados en la escasez ha llevado a resultados de última generación en un amplio conjunto de aplicaciones. ^{[12] [13] [14]} Trabajos recientes sugieren que existe una estrecha conexión entre el modelado de representación dispersa y el aprendizaje profundo. ^[15] ${\displaystyle D}$

Véase también

• Detección comprimida
• Aprendizaje de diccionarios dispersos
• K-SVD
• Lasso (estadísticas)
• Regularización (matemáticas) y problemas inversos

Referencias

1. Donoho, DL y Elad, M. (2003). "Representación óptimamente dispersa en diccionarios generales (no ortogonales) mediante minimización de L1" (PDF) . Actas de la Academia Nacional de Ciencias . 100 (5): 2197–2202. Bibcode :2003PNAS..100.2197D. doi : 10.1073/pnas.0437847100 . PMC  153464 . PMID  16576749.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
2. Tropp, JA (2004). "La codicia es buena: resultados algorítmicos para la aproximación dispersa" (PDF) . IEEE Transactions on Information Theory . 50 (10): 2231–2242. CiteSeerX 10.1.1.321.1443 . doi :10.1109/TIT.2004.834793. S2CID  675692. 
3. Donoho, DL (2006). "Para la mayoría de los grandes sistemas indeterminados de ecuaciones lineales, la solución mínima de norma l1 es también la solución más dispersa" (PDF) . Communications on Pure and Applied Mathematics . 56 (6): 797–829. doi :10.1002/cpa.20132. S2CID  8510060.
4. Elad, M. (2010). Representaciones dispersas y redundantes: de la teoría a las aplicaciones en el procesamiento de señales e imágenes . Springer. CiteSeerX 10.1.1.331.8963 . doi :10.1007/978-1-4419-7011-4. ISBN .  978-1441970107.
5. Donoho, DL, Elad, M. y Templyakov, V. (2006). "Recuperación estable de representaciones dispersas sobrecompletas en presencia de ruido" (PDF) . IEEE Transactions on Information Theory . 52 (1): 6–18. CiteSeerX 10.1.1.125.5610 . doi :10.1109/TIT.2005.860430. S2CID  14813938. {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
6. Tropp, JA (2006). "Relájate: métodos de programación convexa para identificar señales dispersas en el ruido" (PDF) . IEEE Transactions on Information Theory . 52 (3): 1030–1051. CiteSeerX 10.1.1.184.2957 . doi :10.1109/TIT.2005.864420. S2CID  6496872. 
7. Eldar, YC, Kuppinger, P. y Bolcskei, H. (2009). "Señales con dispersión de bloques: relaciones de incertidumbre y recuperación eficiente". IEEE Transactions on Signal Processing . 58 (6): 3042–3054. arXiv : 0906.3173 . Bibcode :2010ITSP...58.3042E. doi :10.1109/TSP.2010.2044837. S2CID  335122.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
8. Tropp, JA, Gilbert, AC y Strauss, MJ (2006). "Algoritmos para aproximación dispersa simultánea. Parte I: Búsqueda voraz". Procesamiento de señales . 86 (3): 572–588. doi :10.1016/j.sigpro.2005.05.030.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
9. Peleg, T. Eldar, YC y Elad, M. (2012). "Explotación de dependencias estadísticas en representaciones dispersas para la recuperación de señales". IEEE Transactions on Signal Processing . 60 (5): 2286–2303. arXiv : 1010.5734 . Bibcode :2012ITSP...60.2286P. doi :10.1109/TSP.2012.2188520. S2CID  3179803.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
10. Needell, D. y Tropp, JA (2009). "CoSaMP: Recuperación iterativa de señales a partir de muestras incompletas e inexactas". Análisis armónico computacional y aplicado . 26 (3): 301–321. arXiv : 0803.2392 . doi :10.1016/j.acha.2008.07.002.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
11. Zibulevsky, M. y Elad, M. (2010). "Optimización L1-L2 en procesamiento de señales e imágenes" (PDF) . Revista IEEE Signal Processing . 27 (3): 76–88. Bibcode :2010ISPM...27...76Z. doi :10.1109/MSP.2010.936023. S2CID  2783691.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
12. Baraniuk, RG Candes, E. Elad, M. y Ma, Y. (2010). "Aplicaciones de la representación dispersa y la detección compresiva". Actas del IEEE . 98 (6): 906–909. doi :10.1109/JPROC.2010.2047424.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
13. Elad, M. Figueiredo, MAT y Ma, Y. (2010). "Sobre el papel de las representaciones dispersas y redundantes en el procesamiento de imágenes" (PDF) . Actas del IEEE . 98 (6): 972–982. CiteSeerX 10.1.1.160.465 . doi :10.1109/JPROC.2009.2037655. S2CID  10992685. Archivado desde el original (PDF) el 17 de enero de 2018. {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
14. Plumbley, MD Blumensath, T. Daudet, L. Gribonval, R. y Davies, ME (2010). "Representaciones dispersas en audio y música: de la codificación a la separación de fuentes". Actas del IEEE . 98 (6): 995–1005. CiteSeerX 10.1.1.160.1607 . doi :10.1109/JPROC.2009.2030345. S2CID  4461063. {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
15. Papyan, V. Romano, Y. y Elad, M. (2017). "Redes neuronales convolucionales analizadas mediante codificación dispersa convolucional" (PDF) . Journal of Machine Learning Research . 18 (83): 1–52. arXiv : 1607.08194 . Código Bibliográfico :2016arXiv160708194P.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )