Hispanopedia Wiki
Articulo de referencia

aproximación dispersa

La teoría de la aproximación dispersa (también conocida como representación dispersa ) se ocupa de las soluciones dispersas para sistemas de ecuaciones lineales . Las técnicas p...

Hispanopedia WikiContenido en espanolLectura gratuita

La teoría de la aproximación dispersa (también conocida como representación dispersa ) se ocupa de las soluciones dispersas para sistemas de ecuaciones lineales . Las técnicas para encontrar estas soluciones y aprovecharlas en diversas aplicaciones se han utilizado ampliamente en el procesamiento de imágenes , el procesamiento de señales , el aprendizaje automático , la imagenología médica y otros campos.

Descomposición dispersa

Observaciones sin ruido

Consideremos un sistema lineal de ecuacionesincógnita=Dα{\displaystyle x=D\alpha }, dóndeD{\displaystyle D}es un valor subdeterminadometro×pag{\displaystyle m\times p}matriz(metro<pag){\displaystyle (m<p)}yincógnita∈Rmetro,α∈Rpag{\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}La matrizD{\displaystyle D}(que normalmente se asume que es de rango completo) se denomina diccionario, yincógnita{\displaystyle x}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.α{\displaystyle \alpha }satisfactorioincógnita=Dα{\displaystyle x=D\alpha }Debido a la naturaleza indeterminada deD{\displaystyle D}Este sistema lineal admite, en general, infinitas soluciones posibles, y entre ellas buscamos la que tenga el menor número de términos distintos de cero. Dicho formalmente, resolvemos

minα∈Rpag‖α‖0 sujeto a incógnita=Dα,{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ sujeto a }}x=D\alpha ,}

dónde‖α‖0=#{i:αi≠0,i=1,…,pag}{\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}es elℓ0{\displaystyle \ell _{0}}pseudonorma, que cuenta el número de componentes no nulos deα{\displaystyle \alpha }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 .

Escasez deα{\displaystyle \alpha }implica que solo unos pocos (k≪metro<pag{\displaystyle k\ll m<p}) componentes en ella no son cero. La motivación subyacente para una descomposición tan dispersa es el deseo de proporcionar la explicación más simple posible deincógnita{\displaystyle x}como una combinación lineal de la menor cantidad posible de columnas deD{\displaystyle D}, también denominados átomos. Como tal, la señalincógnita{\displaystyle x}puede ser visto como una molécula compuesta de unos pocos elementos fundamentales tomados deD{\displaystyle D}.

Si bien el problema planteado anteriormente es de hecho NP-difícil, su solución a menudo se puede encontrar utilizando algoritmos de aproximación. Una de estas opciones es una relajación convexa del problema, obtenida mediante el uso deℓ1{\displaystyle \ell _{1}}-norma en lugar deℓ0{\displaystyle \ell _{0}}, dónde‖α‖1{\displaystyle \|\alpha \|_{1}}simplemente suma los valores absolutos de las entradas enα{\displaystyle \alpha }Este método se conoce como algoritmo de búsqueda de base (BP), que puede implementarse con cualquier solucionador de programación lineal . Un método de aproximación alternativo es una técnica voraz, como la búsqueda por coincidencia (MP), que encuentra la ubicación de los elementos distintos de cero uno a uno.

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

Observaciones ruidosas

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

minα∈Rpag‖α‖0 sujeto a ‖incógnita−Dα‖22≤ϵ2,{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ sujeto a }}\|xD\alpha \|_{2}^{2}\leq \epsilon ^{2},}

o expresado en forma lagrangiana,

minα∈Rpagλ‖α‖0+12‖incógnita−Dα‖22,{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{0}+{\frac {1}{2}}\|xD\alpha \|_{2}^{2},}

dóndeλ{\displaystyle \lambda }está reemplazando elϵ{\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 búsqueda. Más específicamente, cambiando elℓ0{\displaystyle \ell _{0}}a unℓ1{\displaystyle \ell _{1}}norma -obtenemos

minα∈Rpagλ‖α‖1+12‖incógnita−Dα‖22,{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|xD\alpha \|_{2}^{2},}

lo cual 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 no ceros uno por uno hasta que se cumpla 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 deD{\displaystyle D}y la cardinalidad de la soluciónk{\displaystyle k}. [ 4 ] [ 5 ] [ 6 ] Otro resultado teórico interesante se refiere al caso en el queD{\displaystyle D}es una matriz unitaria . Bajo esta suposición, los problemas planteados anteriormente (con cualquiera de las dosℓ0{\displaystyle \ell _{0}}oℓ1{\displaystyle \ell _{1}}) admiten soluciones de forma cerrada en forma de contracción no lineal. [ 4 ]

Variaciones

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

Escasez estructurada : En la versión original del problema, se puede elegir cualquiera de los átomos del diccionario. En el modelo de escasez estructurada (por 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 representarincógnita{\displaystyle x}de tal manera que sea escaso al tiempo que se fuerza esta estructura de bloques. [ 7 ]

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

Otras estructuras : De manera más amplia, el problema de aproximación dispersa se puede plantear forzando una estructura deseada específica en el patrón de ubicaciones distintas de cero enα{\displaystyle \alpha }Dos casos de interés que han sido ampliamente estudiados son la estructura basada en árboles y, más generalmente, un soporte distribuido de Boltzmann. [ 9 ]

Algoritmos

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

minα∈Rpag‖α‖0 sujeto a ‖incógnita−Dα‖22≤ϵ2.{\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ sujeto a }}\|xD\alpha \|_{2}^{2}\leq \epsilon ^{2}.}

A continuación mencionamos algunos de estos métodos principales.

  • La búsqueda de coincidencia es un algoritmo iterativo voraz para resolver aproximadamente el problema anterior. Funciona encontrando gradualmente las ubicaciones de los elementos distintos de cero enα{\displaystyle \alpha }uno a la vez. La idea principal es encontrar en cada paso la columna (átomo) enD{\displaystyle D}que mejor se correlaciona con el residuo actual (inicializado aincógnita{\displaystyle x}), y luego actualizando este residuo para tener en cuenta el nuevo átomo y su coeficiente. La búsqueda de coincidencia podría seleccionar el mismo átomo varias veces.
  • La búsqueda de coincidencia ortogonal es muy similar a la búsqueda de coincidencia, con una diferencia importante: en cada paso del algoritmo, todos los coeficientes distintos de cero se actualizan mediante mínimos cuadrados . Como consecuencia, el residuo es ortogonal a los átomos ya seleccionados, por lo que un átomo no puede ser seleccionado más de una vez.
  • Métodos voraces por etapas: Las variaciones mejoradas de los métodos anteriores son algoritmos que operan de forma voraz y que incorporan dos características cruciales: (i) la capacidad de añadir grupos de elementos distintos de cero a la vez (en lugar de un elemento distinto de cero por ronda); y (ii) la inclusión de un paso de poda en cada ronda en el que se descartan varios átomos del soporte. Ejemplos de este enfoque son el algoritmo Subspace-Pursuit y el CoSaMP. [ 10 ]
  • La búsqueda de base resuelve una versión relajada convexa del problema reemplazando laℓ0{\displaystyle \ell _{0}}por unℓ1{\displaystyle \ell _{1}}-norma. Nótese que esto solo define un nuevo objetivo, dejando abierta la cuestión del algoritmo a utilizar para obtener la solución deseada. Los algoritmos comúnmente considerados para este fin son IRLS , LARS y los métodos iterativos de contracción suave. [ 11 ]
  • 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 de contracción suave iterativos mencionados anteriormente, y el selector de Dantzig.

Aplicaciones

Las ideas y algoritmos de aproximación dispersa se han utilizado ampliamente en el procesamiento de señales , el procesamiento de imágenes , el aprendizaje automático , las imágenes médicas , el procesamiento de matrices , la 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 ajustarD{\displaystyle D}para que el modelo se ajuste mejor a los datos proporcionados. El uso de modelos inspirados en la escasez ha dado lugar a resultados de vanguardia en una amplia gama 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 ]

Véase también

Referencias

  1. ↑ Donoho, DL y Elad, M. (2003). "Representación óptimamente dispersa en diccionarios generales (no ortogonales) mediante minimización 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 sistemas subdeterminados grandes 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. 1 2 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 sobrecompletas dispersas 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 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 dispersas en 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". Applied and Computational Harmonic Analysis . 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 el procesamiento de señales e imágenes" (PDF) . IEEE Signal Processing Magazine . 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 del 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 . Bibcode : 2016arXiv160708194P .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )