stringtranslate.com

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

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 .

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 .

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.

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]

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

o ponerlo en forma lagrangiana,

¿Dónde está el reemplazo ?

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

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]

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]

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]

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]

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:

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

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]

Véase también

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. ^ ab 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 )