Uno de los principios centrales de procesamiento de señales es la teoría de muestreo de Shannon/Nyquist: el número de muestras necesarias para capturar una señal está dictada por su ancho de banda. Muy recientemente, ha surgido una teoría alternativa de “compresión de muestreo”. Mediante el uso de algoritmos de recuperación no lineales (en base a la optimización convexa), señales e imágenes súper-resueltos pueden ser reconstruidos a partir de lo que parece ser datos muy incompletos. Compresión de muestreo nos muestra cómo la compresión de datos se puede incorporar de manera implícita en el proceso de adquisición de datos, una nos da un nuevo punto de vista para un conjunto diverso de aplicaciones, incluyendo la obtención de imágenes tomográficas acelerado, la conversión de analógico a digital y la fotografía digital.
Ver ejemplos de compresión de muestreo en acción.
Código
L1-MAGIC es un conjunto de rutinas de MATLAB para resolver los programas de optimización convexa centrales de compresión de muestreo. Los algoritmos se basan en métodos de punto interior estándar, y son adecuados para problemas a gran escala.
Descargar el código (incluyendo el Manual del Usuario)
Descargar la Guía del usuario (pdf)
Papeles
Un teorema de muestreo no lineal
“Principios de incertidumbre robusto: la recuperación exacta de información muy incompleta de Fourier”
por: Emmanuel Candès, Justin Romberg, y Terence Tao a aparecer en IEEE Transactions on Information Theory, febrero de 2006.
El resultado central a partir de este trabajo es que un vector disperso puede recuperarse exactamente a partir de un pequeño número de observaciones de dominio de Fourier. Más precisamente, Sea f una señal discreta longitud-N que tiene B distintos de cero los componentes (hacemos hincapié en que el número y la ubicación de los componentes son desconocidos a priori). Nosotros recogemos muestras en K frecuencias diferentes que se seleccionan al azar. Entonces, para K en el orden de registro B N, podemos recuperar f perfectamente (con muy alta probabilidad) a través de la minimización de l1.
Descargar (pdf)
Recuperación de la señal casi óptima y el principio de incertidumbre Uniforme
“Recuperación de la señal casi óptima de las proyecciones aleatorias y estrategias de codificación universal”
por: Emmanuel Candes y Terence Tao Enviado a IEEE Transactions on Information Theory, noviembre de 2004.
En este trabajo se deriva condiciones precisas para cuando una señal de escasa arbitraria f puede ser recuperado a partir de un conjunto fijo de mediciones lineales y = Mf. Si M obedece lo que es términos del Principio Uniforme incertidumbre para conjuntos de tamaño S (que esencialmente significa que todas las submatrices formados mediante la adopción de las columnas S de M son isometrías aproximados), a continuación, cada señal de f con no más de S componentes distintos de cero pueden ser recuperados a partir de su mediciones y = Mf a través de un programa de l1 minimización. Se muestra que si M es generado aleatoriamente, que obedecerá el UUP con alta probabilidad para los conjuntos de tamaño de registro S ~ K (N / K), donde K es el número de filas
de M. Usando este resultado, se demuestra que si f es compresible en lugar de escaso (lo que significa que la ordenada componentes de decaimiento f rápidamente), entonces la recuperación L1 es casi óptima: el error de recuperación tiende a cero cuando se añade más mediciones casi tan rápido como el error de aproximación no lineal de la señal original.
Descargar (pdf)
Estabilidad
“Recuperación de la señal estable a partir de mediciones incompletos e inexactos”
por: Emmanuel Candes, Justin Romberg, y Terence Tao a aparecer en Comunicaciones en matemáticas puras y aplicadas, 2006.
Este artículo demuestra que el procedimiento de recuperación es estable. Dado que la matriz de medición
satisface la UUP, mostramos que podemos recuperar una señal escasa o compresible f a partir de mediciones corruptos y = Mf + e, donde el tamaño de E es menor que epsilon, a error dentro de epsilon. La prueba es corto y limpio, y abarca los resultados de recuperación anteriores para el caso silencioso.
Descargar (pdf)
La estimación estadística
“El selector de Dantzig: Estimación estadística cuando p es mucho menor que n” por: Emmanuel Candes y Terence Tao Sometido a IEEE Transactions on Information Theory, junio de 2005.
Cuando los errores cometidos en el proceso de medición son gaussianas, mucho más se puede decir sobre la precisión de la recuperación. Este trabajo muestra que una señal de escasa puede estimarse a partir de un conjunto incompleto de mediciones corrompidos por ruido aditivo blanco gaussiano igual de bien que de la observación de toda la señal ruidosa por sí mismo (y umbral). El proceso de estimación, que es otra vez un cierto tipo de programa de minimización de L1, se denomina el Selector de Dantzig.
Descargar (pdf)
La decodificación lineal
“La decodificación de programación lineal”
por: Emmanuel Candès y Terence Tao IEEE Transactions on Information Theory, diciembre de 2005.
Este documento demuestra que, además de la recuperación de señales dispersas, la minimización de L1 se puede utilizar para detectar y corregir errores dispersos. Una palabra de código c se genera mediante la aplicación de una matriz de codificación MxN A a un mensaje m: c = Am. Se muestra que si A obedece a un tipo de principio de incertidumbre, a continuación, c puede ser recuperado incluso si m es alterada sinuosamente en lugares desconocidos QM (donde q es una constante).
Descargar (pdf)
Encontrar Escasos Descomposiciones
“Robusta principios de incertidumbre cuantitativos y descomposiciones de manera óptima dispersos”
por: Emmanuel Candes y Justin Romberg a aparecer en Fundamentos de Matemática Computacional, 2006.
Este artículo revisa la aplicación ya clásico de la minimización de L1 a la búsqueda de representaciones dispersas en las uniones de las bases. El sistema de espiga-sinusoide es estudiado en detalle: se demuestra que si una señal se compone de una superposición de ~ N/sqrt (log N) picos y sinusoides, entonces el más dispersa (en el sentido de apoyo mínimo) descomposición puede encontrar a través de la minimización de L1. En este trabajo se hace uso explícito de nuevos principios de incertidumbre entre el tiempo y el dominio de la frecuencia. También se discute la extensión a la búsqueda de descomposiciones dispersas en pares generales de las bases.
Descargar (pdf)
Campo de golf
Publicaciones de David Donoho, incluyendo el trabajo de detección comprimido y escaso de recuperación (con Jared Tanner)
El grupo de la Universidad Rice DSP página de recursos de detección comprimido; véase en particular el trabajo muy reciente en la construcción de una cámara CS
Robert Nowak y papel de Jarvis Haupt sobre la reconstrucción de la señal de las proyecciones aleatorias ruidoso.
Resumen de Terence Tao del estado actual de la teoría de compresión de muestreo
La página web de Joel Tropp en el Instituto de Tecnología de California, véase en particular su trabajo en la reconstrucción utilizando algoritmos codiciosos (con Ana Gilbert).
Martin Strauss y Anna Gilbert, de la Universidad de Michigan, y sus trabajos sobre algoritmos rápidos para la estimación de las transformadas de Fourier dispersas
Martin Vetterli y el trabajo de Irena Maravic en las señales de muestreo con “tasa finita de la innovación”
De David Brady Duke Integrado de Detección y Tratamiento de la página
Recent Comments