¿Cuáles son los documentos fundamentales sobre detección comprimida? La tecnología cambia la vida futura

La detección comprimida (o muestreo compresivo) es la idea de que puede escapar con menos mediciones lineales de lo habitual si sabe que su objetivo es escaso. Esta idea se originó a partir de una serie de documentos fundamentales de Candes, Romberg, Tao y Donoho en la segunda mitad de 2004:

Principios sólidos de incertidumbre: recuperación exacta de información de frecuencia altamente incompleta, Candes, Romberg y Tao ( originalmente en junio de 2004 ): muestra que puede recuperar señales k-dispersas n-dimensionales de k log (n) muestras de frecuencia elegidas al azar.
Para la mayoría de los sistemas de ecuaciones subdeterminados más grandes, la solución cercana a la norma mínima l1 se aproxima al Donoho de solución cercana más escasa ( agosto de 2004 )
Recuperación de señal casi óptima de proyecciones aleatorias: ¿Estrategias de codificación universal? Candes, Tao ( octubre de 2004 ):
Donoho de detección comprimida ( septiembre de 2004 ):
Decodificación por Linear Programming Candes, Tao ( diciembre de 2004 )
Politopes vecinos y solución dispersa de ecuaciones lineales subdeterminadas Donoho ( diciembre de 2004 )
Recuperación estable de la señal de mediciones incompletas e inexactas Candes, Romberg, Tao ( febrero de 2005 ):
Candes de muestreo compresivo ( 2006 )

Desde el punto de vista pedagógico, ahora hay formas mucho mejores de aprender sobre la detección comprimida y no lo recomendaría a estos documentos fundamentales a menos que desee rastrear la evolución de estas ideas.

Primero, hablemos un poco sobre por qué podemos hacer con pocas mediciones lineales. Suponga que [math] x [/ math] es un vector dimensional [math] d [/ math]. Si observamos mediciones lineales independientes, necesitaremos mediciones independientes [matemáticas] d [/ matemáticas] para precisar [matemáticas] x [/ matemáticas] con precisión. Sin embargo, si [math] x [/ math] es escaso, de modo que solo [math] k \ ll d [/ math] de las entradas son realmente distintas de cero, puede recuperar [math] x [/ math] con muchas menos mediciones que [matemáticas] d [/ matemáticas]. De hecho, las mediciones [matemáticas] 2k [/ matemáticas] (desde un marco de chispa completo) serán suficientes para la recuperación de todos los vectores dispersos [matemáticas] k [/ matemáticas], pero este es un problema NP difícil (ver Soluciones aproximadas dispersas para Sistemas lineales para una prueba). Ahora, la constatación de que puede recuperar vectores dispersos con menos mediciones usando relajación convexa usando la norma l1, tiene una larga e interesante historia. Entonces, en cierto sentido, estos documentos son realmente una adición al trabajo previo sobre recuperación escasa utilizando la minimización de l1. Si la idea ha existido por mucho tiempo, ¿por qué estos son los documentos fundamentales? Bueno, la novedad en los documentos anteriores se puede atribuir a lo siguiente:

Se necesitan límites mucho mejores en cuanto al número de mediciones: estos documentos derivaron los límites más estrictos y determinaron el número de mediciones mejorando drásticamente los límites en la literatura anterior. Por lo tanto, estableció l1 como una teoría con garantías sobre la optimización más que simplemente como una heurística.
Matrices de mediciones aleatorias: los documentos mostraron que las mediciones lineales “aleatorias” son suficientes para operadores de medición con alta probabilidad. Esto facilita dar una estrategia de adquisición universal. La cámara de detección comprimida de 1 bit es una excelente prueba del concepto de esta idea.
Comercialización: El método convencional en el procesamiento de señales es adquirir una señal completamente y luego comprimirla. El hecho de que pueda comprimirlo significa que es escaso o aproximadamente escaso con respecto a algún diccionario. Estos documentos preguntaban por qué deberíamos molestarnos en adquirir tantas mediciones, cuando bastarían con menos (si usa la minimización de l1 para recuperarla de unas pocas mediciones lineales). es decir, por qué sentir y comprimir, si puedes hacer una detección comprimida. Al final, si me preguntas, “detección comprimida” es un término de marketing que enfatiza una posible aplicación de la minimización de l1.

Antes de estos límites de medición ajustados, los documentos fundamentales en la literatura de recuperación escasa incluyen:

Lazo: reducción y selección de la regresión a través del lazo Tibshirani ( 1996 ) – Esta popularización de la l1 en la comunidad estadística
Persecución de base: descomposición atómica por Persecución de base Chen, Donoho, Saunders ( Originalmente 1994 en Asilomar ). Esto introdujo la regularización l1 en la comunidad de procesamiento de señales.
Principios de incertidumbre discreta: Principios de incertidumbre y descomposición atómica ideal Donoho, Huo (junio de 1999) – Excelente trabajo que define principios de incertidumbre discreta. Una vez más, después de la revolución de detección comprimida de 2004, Candes y Romberg mejoraron sustancialmente
Representaciones de Fourier dispersas casi óptimas a través del muestreo Gilbert, Guha, Indyk, Muthukrishnan, Strauss (2002)
Aproximación escasa mejorada sobre diccionarios cuasi-incoherentes Tropp, Gilbert, Muthukrishnan, Strauss ( 2003 )
La codicia es buena: resultados algorítmicos para Tropp de aproximación dispersa ( febrero de 2003 )
Just Relax: métodos de programación convexos para la selección de subconjuntos y Tropp de aproximación dispersa ( 2003 )

Los documentos 4-7 en realidad toman una ruta diferente y usan métodos algorítmicos codiciosos para una recuperación dispersa. Finalmente, ha habido una serie de extensiones interesantes en la última década después de que estos documentos lo iniciaran. Pero supongo que esa revisión merece un tratamiento separado 🙂