Aproximación escasa

La teoría de la 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 se han utilizado ampliamente 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 escasa

Observaciones silenciosas

Considere un sistema lineal de ecuaciones , donde es una matriz indeterminada y . La matriz (normalmente se supone que tiene 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 escasa 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 menos valores distintos de 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 ,}$

¿Dónde está la pseudonorma, 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 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 de como una combinación lineal de la menor cantidad posible de columnas de , también conocidos como átomos. Como tal, la señal puede verse como una molécula compuesta de 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, obtenida usando la norma -en lugar de , donde simplemente suma los valores absolutos de las entradas en . Esto se conoce como algoritmo de búsqueda de bases (BP), que se puede manejar utilizando cualquier solucionador de programación lineal . Un método de aproximación alternativo es una técnica codiciosa, como la búsqueda de coincidencias (MP), que encuentra la ubicación de los distintos de ceros uno a la vez. ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle \|\alpha \|_{1}}$ ${\displaystyle \alpha }$

Sorprendentemente, en condiciones suaves (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 Estamos 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 - al término de ajuste de datos, el problema de descomposición dispersa se vuelve ${\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 puesto 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 sin ruido, estos dos problemas son NP-Difíciles en general, pero pueden aproximarse utilizando algoritmos de seguimiento. Más específicamente, cambiando el 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 de búsqueda de base . De manera similar, la búsqueda de coincidencias se puede utilizar para aproximar la solución de los problemas anteriores, encontrando las ubicaciones de los distintos de ceros una a la vez hasta que se alcance el umbral de error. También en este caso, 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 se trata de 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.

Escasez estructurada : en la versión original del problema, se puede seleccionar cualquiera de los átomos del diccionario. En el modelo de dispersión estructurado (en bloques), 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 representarlo de manera que sea escaso y al mismo tiempo forzar 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 de codificación dispersa colaborativa (conjunta), está disponible un conjunto de señales, cada una de las cuales se cree que emerge de (casi) el 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 y al mismo tiempo los obligue a compartir el mismo (o cercano) soporte. ^[8] ${\displaystyle x}$ ${\displaystyle D}$

Otras estructuras : en términos más generales, el problema de aproximación escasa se puede resolver mientras se fuerza una estructura deseada específica en el patrón de ubicaciones distintas de cero en . Dos casos de interés que han sido ampliamente estudiados 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 conocidos como búsqueda ) 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 distintos de ceros, uno a la vez. La idea central es encontrar en cada paso la columna (átomo) que mejor se correlaciona con el residual actual (inicializado en ) y luego actualizar este residual para tener en cuenta el nuevo átomo y su coeficiente. La búsqueda coincidente podría seleccionar 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 mínimos cuadrados . Como consecuencia, el residuo es ortogonal a los átomos ya elegidos y, por tanto, un átomo no se puede seleccionar más de una vez.
• Métodos codiciosos por etapas: las variaciones mejoradas con respecto a lo anterior son algoritmos que operan con avidez al tiempo que agregan dos características críticas: (i) la capacidad de agregar grupos de distintos de ceros a la vez (en lugar de uno distinto de cero por ronda); e (ii) incluir un paso de poda en cada ronda en el que varios de los átomos se descartan del soporte. Los 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. Tenga en cuenta que esto sólo 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}}$

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

Aplicaciones

Las ideas y algoritmos de aproximación dispersa se han utilizado ampliamente en 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 determinado, 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 adaptarse para que el modelo coincida mejor con los datos proporcionados. El uso de modelos inspirados en la escasez ha dado lugar 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}$

Ver también

• Detección comprimida
• Aprendizaje escaso del diccionario
• K-SVD
• Lazo (estadísticas)
• Regularización (matemáticas) y problemas inversos.

Referencias

1. Donoho, DL y Elad, M. (2003). "Representación óptimamente escasa en diccionarios generales (no ortogonales) mediante minimización L1" (PDF) . Procedimientos de la Academia Nacional de Ciencias . 100 (5): 2197–2202. Código Bib : 2003PNAS..100.2197D. doi : 10.1073/pnas.0437847100 . PMC  153464 . PMID  16576749.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
2. Tropp, JA (2004). "La codicia es buena: resultados algorítmicos para una 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. 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 escasa" (PDF) . Comunicaciones sobre Matemática Pura y Aplicada . 56 (6): 797–829. doi :10.1002/cpa.20132. S2CID  8510060.
4. Elad, M. (2010). Representaciones escasas 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 representaciones escasas y sobrecompletas 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. S2CID  14813938. {{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
6. Tropp, JA (2006). "Simplemente relájese: métodos de programación convexa 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. S2CID  6496872. 
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 Bib : 2010ITSP...58.3042E. doi :10.1109/TSP.2010.2044837. S2CID  335122.{{cite journal}}: Mantenimiento CS1: 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 codiciosa". Procesamiento de la señal . 86 (3): 572–588. doi :10.1016/j.sigpro.2005.05.030.{{cite journal}}: Mantenimiento CS1: 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". Transacciones IEEE sobre procesamiento de señales . 60 (5): 2286–2303. arXiv : 1010.5734 . Código Bib : 2012ITSP...60.2286P. doi :10.1109/TSP.2012.2188520. S2CID  3179803.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
10. Needell, D. y Tropp, JA (2009). "CoSaMP: recuperación iterativa de señales de muestras incompletas e inexactas". Análisis Armónico Aplicado y Computacional . 26 (3): 301–321. arXiv : 0803.2392 . doi :10.1016/j.acha.2008.07.002.{{cite journal}}: Mantenimiento CS1: 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 de procesamiento de señales IEEE . 27 (3): 76–88. Código Bib : 2010 ISPM...27...76Z. doi :10.1109/MSP.2010.936023. S2CID  2783691.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
12. Baraniuk, RG Candes, E. Elad, M. y Ma, Y. (2010). "Aplicaciones de representación escasa y detección de compresión". Actas del IEEE . 98 (6): 906–909. doi :10.1109/JPROC.2010.2047424.{{cite journal}}: Mantenimiento CS1: 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}}: Mantenimiento CS1: 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}}: Mantenimiento CS1: 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) . Revista de investigación sobre aprendizaje automático . 18 (83): 1–52. arXiv : 1607.08194 . Código Bib : 2016arXiv160708194P.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )