Detección de compresión

La detección comprimida , también conocida como detección comprimida , muestreo compresivo y muestreo disperso  , es la técnica de adquisición y reconstrucción de una señal utilizando el conocimiento de sus valores previos que son dispersos o comprimidos. Este campo de procesamiento de señales ha existido durante 40 años, pero solo recientemente ganó una amplia aceptación, gracias en parte a varios resultados importantes de David Donoho , Emmanuel Candès , Justin Romberg y Terence Tao .

Historia

Las ideas que describen la detección de compresión [1] comenzaron en 2004 cuando Emanuel Cande, un matemático de Caltech , estaba trabajando en problemas de imágenes por resonancia magnética . Descubrió que la imagen de prueba podía reconstruirse con precisión incluso con datos considerados insuficientes según el criterio de Nyquist-Shannon . Además, se vio un precursor de la detección comprimida en la década de 1970 cuando los sismólogos construyeron imágenes de niveles reflectantes dentro de la tierra basándose en datos que no parecían satisfacer el criterio de Nyquist-Shannon [2] .

Método

La idea básica es que la mayoría de las señales de interés tienen cierta estructura y redundancia, no son puro ruido. En particular, la mayoría de las señales son dispersas , es decir, incluyen muchos coeficientes cercanos o iguales a cero cuando se presentan en alguna base [3] . (Las mismas ideas subyacen en muchas formas de compresión con pérdida ).

La detección comprimida generalmente comienza tomando un número limitado (posiblemente aleatorio) de muestras en una base diferente a aquella en la que la señal es escasa. Dado que el número de muestras es limitado, la tarea de volver a convertir la imagen en el área objetivo implicaría resolver una ecuación matricial indeterminada  , es decir, hay una gran cantidad de imágenes candidatas diferentes que pueden resultar para una muestra dada, ya que el número de muestras es menor que el número de coeficientes en la imagen completa. Por lo tanto, se debe introducir alguna restricción adicional para seleccionar el "mejor" candidato.

La solución clásica a tales problemas es minimizar la norma  , es decir, minimizar la cantidad de energía en el sistema. Por lo general, esto es matemática simple (solo involucra la multiplicación de matrices usando una base de muestreo pseudo- inverso ). Sin embargo, esto conduce a malos resultados para la mayoría de las aplicaciones prácticas, ya que los coeficientes desconocidos (ausentes en la muestra) rara vez tienen energía cero.

Una solución más atractiva sería minimizar la norma o, de manera equivalente, maximizar el número de coeficientes cero en la nueva base. Sin embargo, este es un problema NP-difícil (incluye problemas de suma de subconjuntos ) y también es computacionalmente inviable para todos los conjuntos de datos, excepto los más pequeños. Así, según las ideas de Tao Terence et al., se acostumbra minimizar la norma de aproximación , o suma en términos absolutos. El problema de norma mínima se formula como un problema de programación lineal , para el cual existen métodos de solución eficientes. Esto conduce a resultados comparables utilizando la norma, lo que a menudo genera resultados en los que muchos de los coeficientes son cero.

Enlaces

  1. ↑ Donoho, DL, Compressed Sensing , IEEE Transactions on Information Theory, V. 52(4), 1289-1306, 2006 [1] Archivado el 26 de junio de 2010 en Wayback Machine .
  2. ↑ Hayes, Brian, The Best Bits , American Scientist, julio de 2009 Archivado el 12 de abril de 2010.
  3. ↑ Candès, EJ y Wakin, MB, Introducción al muestreo por compresión , Revista de procesamiento de señales IEEE, V.21, marzo de 2008 [2]

Para leer más