Aproximación escasa

La teoría de la aproximación dispersa (también conocida como representación dispersa ) trata con 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 , procesamiento de señales , aprendizaje automático , imágenes médicas y más.

Descomposición escasa

Observaciones silenciosas

Considere un sistema lineal de ecuaciones , donde es una matriz indeterminada y . La matriz (que normalmente se asume que es de rango completo) se denomina 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 satisfactoria . Debido a la naturaleza indeterminada de , este sistema lineal admite en general un número infinito de soluciones posibles, y entre estas buscamos la que tenga el menor número de no ceros. 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 pseudo-norma, que cuenta el número de componentes distintos de cero de . Se sabe que este problema es NP-difícil con una reducción a problemas de selección de subconjuntos NP-completos en la 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 ( ) son distintos de cero. La motivación subyacente para una descomposición tan escasa es el deseo de proporcionar la explicación más simple posible como una combinación lineal de la menor cantidad posible de columnas de , también denominados átomos. Como tal, la señal puede verse como una molécula compuesta por algunos 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 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, que se obtiene utilizando la -norm en lugar de , donde simplemente suma los valores absolutos de las entradas en . Esto se conoce como el algoritmo de búsqueda de bases (BP), que se puede manejar con cualquier solucionador de programación lineal . Un método de aproximación alternativo es una técnica codiciosa, como la búsqueda de emparejamiento (MP), que encuentra la ubicación de los distintos de ceros de uno en uno.${\displaystyle \ell _{1}}$${\displaystyle \ell _{0}}$${\displaystyle \|\alpha \|_{1}}$${\displaystyle \alpha }$

Sorprendentemente, en condiciones suaves en (usando 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 BP y MP están garantizados para encontrarlo 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 escasa 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},}$

donde está reemplazando el .${\displaystyle \lambda }$${\displaystyle \epsilon }$

Al igual que en el caso silencioso, estos dos problemas son NP-Hard en general, pero pueden aproximarse utilizando algoritmos de seguimiento. Más específicamente, cambiando el a -norm, 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},}$

lo que se conoce como eliminación de ruido de búsqueda de bases . De manera similar, la búsqueda de emparejamiento se puede utilizar para aproximar la solución de los problemas anteriores, encontrando las ubicaciones de los distintos de ceros una por una hasta que se alcance 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 y la cardinalidad de la solución .^{[4] [5] [6]} Otro resultado teórico interesante se refiere al caso en el que es unitario. 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

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

Dispersión estructurada : en la versión original del problema, se puede seleccionar cualquiera de los átomos del diccionario. En el modelo estructurado (bloque) de dispersión, en lugar de seleccionar átomos individualmente, se deben seleccionar grupos de ellos. Estos grupos pueden superponerse y ser de diferente tamaño. El objetivo es representar de tal manera que sea escaso mientras se fuerza esta estructura de 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 colaborativo (conjunto) de codificación dispersa, está disponible un conjunto de señales, cada una de las cuales se cree que surge de (casi) el mismo conjunto de átomos . En este caso, la tarea de seguimiento tiene como objetivo recuperar un conjunto de representaciones escasas que describen mejor los datos mientras los obliga a compartir el mismo soporte (o cercano). ^[8]${\displaystyle x}$${\displaystyle D}$

Otras estructuras : en términos más generales, el problema de la aproximación dispersa se puede lanzar mientras 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 extensamente 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 persecución ) que se han desarrollado para abordar el problema de la 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 codicioso para resolver aproximadamente el problema anterior. Funciona encontrando gradualmente las ubicaciones de los no ceros de uno en uno. La idea central es encontrar en cada paso la columna (átomo) que mejor se correlaciona con el residual actual (inicializado a ), y luego actualizar este residual para tener en cuenta el nuevo átomo y su coeficiente. La búsqueda coincidente puede elegir el mismo átomo varias veces.${\displaystyle \alpha }$${\displaystyle D}$${\displaystyle x}$
• La búsqueda de emparejamiento ortogonal es muy similar a la búsqueda de emparejamiento, con una diferencia importante: en cada uno de los pasos del algoritmo, todos los coeficientes distintos de cero se actualizan por mínimos cuadrados . Como consecuencia, el residuo es ortogonal a los átomos ya elegidos y, por lo tanto, no se puede seleccionar un átomo más de una vez.
• Métodos codiciosos por etapas: las variaciones mejoradas con respecto a los anteriores son algoritmos que operan codiciosamente al tiempo que agregan dos características críticas: (i) la capacidad de agregar grupos de no ceros a la vez (en lugar de uno distinto de cero por ronda); e (ii) incluir una etapa de poda en cada ronda en la que varios de los átomos se descartan del soporte. Representantes de este enfoque son el algoritmo Subspace-Pursuit y CoSaMP. ^[10]

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

• Hay varios otros métodos para resolver problemas de descomposición dispersa: método de homotopía, descenso de coordenadas , umbral rígido iterativo, métodos proximales de primer orden , que están relacionados con los algoritmos iterativos de contracción suave antes mencionados y selector de 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 regularización del problema. Estos problemas suelen ir acompañados de un mecanismo de aprendizaje de diccionario que tiene como objetivo ajustarse para hacer coincidir mejor el modelo con los datos dados. El uso de modelos inspirados en la escasez ha dado lugar a resultados de vanguardia en un amplio conjunto de aplicaciones.${\displaystyle D}$^{[12] [13] [14]} Un trabajo reciente sugiere que existe una estrecha conexión entre el modelado de representación escasa y el aprendizaje profundo. ^[15]

Ver también

• Detección comprimida
• Aprendizaje escaso de diccionario
• 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 la minimización de L1" (PDF) . Actas de la Academia Nacional de Ciencias . 100 (5): 2197–2202. Código bibliográfico : 2003PNAS..100.2197D . doi : 10.1073 / pnas.0437847100 . PMC  153464 . PMID  16576749 .
2. Tropp, JA (2004). "La codicia es buena: resultados algorítmicos para aproximación escasa" (PDF) . Transacciones IEEE sobre teoría de la información . 50 (10): 2231–2242. CiteSeerX 10.1.1.321.1443 . doi : 10.1109 / TIT.2004.834793 .  
3. Donoho, DL (2006). "Para la mayoría de los grandes sistemas indeterminados de ecuaciones lineales, la solución mínima de la norma l1 es también la solución más escasa" (PDF) . Comunicaciones sobre Matemática Pura y Aplicada . 56 (6): 797–829. doi : 10.1002 / cpa.20132 .
4. Elad, M. (2010). Representaciones dispersas y redundantes: de la teoría a las aplicaciones en el procesamiento de señales e imágenes . Saltador. 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 escasas representaciones supercompletas en presencia de ruido" (PDF) . Transacciones IEEE sobre teoría de la información . 52 (1): 6–18. CiteSeerX 10.1.1.125.5610 . doi : 10.1109 / TIT.2005.860430 .  
6. Tropp, JA (2006). "Simplemente relájese: métodos de programación convexos para identificar señales dispersas en ruido" (PDF) . Transacciones IEEE sobre teoría de la información . 52 (3): 1030–1051. CiteSeerX 10.1.1.184.2957 . doi : 10.1109 / TIT.2005.864420 .  
7. Eldar, YC, Kuppinger, P. y Bolcskei, H. (2009). "Señales de bloques dispersos: relaciones de incertidumbre y recuperación eficiente". Transacciones IEEE sobre procesamiento de señales . 58 (6): 3042-3054. arXiv : 0906.3173 . Código Bibliográfico : 2010ITSP ... 58.3042E . doi : 10.1109 / TSP.2010.2044837 .
8. Tropp, JA, Gilbert, AC y Strauss, MJ (2006). "Algoritmos de aproximación escasa simultánea. Parte I: búsqueda codiciosa". Procesamiento de señales . 86 (3): 572–588. doi : 10.1016 / j.sigpro.2005.05.030 .
9. Peleg, T. Eldar, YC y Elad, M. (2012). "Explotación de dependencias estadísticas en representaciones dispersas para la recuperación de la señal". Transacciones IEEE sobre procesamiento de señales . 60 (5): 2286–2303. arXiv : 1010.5734 . Código bibliográfico : 2012ITSP ... 60.2286P . doi : 10.1109 / TSP.2012.2188520 .
10. Needell, D. y Tropp, JA (2009). "CoSaMP: recuperación de señal iterativa 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 .
11. Zibulevsky, M. y Elad, M. (2010). "Optimización L1-L2 en procesamiento de señal e imagen" (PDF) . Revista de procesamiento de señales IEEE . 27 (3): 76–88. Código Bibliográfico : 2010ISPM ... 27 ... 76Z . doi : 10.1109 / MSP.2010.936023 .
12. Baraniuk, RG Candes, E. Elad, M. y Ma, Y. (2010). "Aplicaciones de la representación escasa y la detección compresiva". Actas del IEEE . 98 (6): 906–909. doi : 10.1109 / JPROC.2010.2047424 .
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 . Archivado desde el original (PDF) el 17 de enero de 2018.  
14. Plumbley, MD Blumensath, T. Daudet, L. Gribonval, R. y Davies, ME (2010). "Representaciones escasas 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 . 
15. Papyan, V. Romano, Y. y Elad, M. (2017). "Redes neuronales convolucionales analizadas mediante codificación dispersa convolucional" (PDF) . Revista de investigación sobre aprendizaje automático . 18 (83): 1–52. arXiv : 1607.08194 . Código bibliográfico : 2016arXiv160708194P .