MIT ha estado haciendo un poco de ruido últimamente sobre un nuevo algoritmo que se promociona como una transformación de Fourier más rápida que funciona en tipos particulares de señales, por ejemplo: "La transformación de Fourier más rápida es una de las tecnologías emergentes más importantes del mundo ". La revista MIT Technology Review dice :
Con el nuevo algoritmo, llamado la transformada escasa de Fourier (SFT), los flujos de datos pueden procesarse de 10 a 100 veces más rápido de lo que era posible con el FFT. La aceleración puede ocurrir porque la información que más nos interesa tiene una gran estructura: la música no es ruido aleatorio. Estas señales significativas generalmente tienen solo una fracción de los valores posibles que una señal podría tomar; El término técnico para esto es que la información es "escasa". Debido a que el algoritmo SFT no está diseñado para funcionar con todos los flujos de datos posibles, puede tomar ciertos atajos que de otro modo no estarían disponibles. En teoría, un algoritmo que puede manejar solo señales dispersas es mucho más limitado que el FFT. Pero "la escasez está en todas partes", señala el coinventor Katabi, profesor de ingeniería eléctrica y ciencias de la computación. "Está en la naturaleza; es ' s en señales de video; está en señales de audio ".
¿Podría alguien aquí proporcionar una explicación más técnica de qué es realmente el algoritmo y dónde podría ser aplicable?
EDITAR: Algunos enlaces:
- El documento: " Transformación de Fourier dispersa casi óptima " (arXiv) por Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price.
- Sitio web del proyecto : incluye implementación de muestra.
fuente
No he leído el documento sobre sFFT, pero tengo la sensación de que la idea de sujetar el FFT detrás está explotando lo anterior de k-sparsity. Por lo tanto, no es necesario calcular todas las entradas de coeficientes FFT, sino calcular k de ellos. Por eso, para la señal k-dispersa, la complejidad es O (klog n) en lugar de O (nlog n) para FFT convencional.
De cualquier manera, con respecto a los comentarios de @rcmpton, al decir "La idea detrás de la detección comprimida es que puede recuperar datos dispersos de muestras aleatorias dispersas extraídas de un dominio diferente (por ejemplo, recuperar imágenes dispersas de datos aleatorios de frecuencia dispersa (es decir, MRI)) ". La pregunta es ¿qué son las "muestras aleatorias dispersas"? Creo que podrían ser muestras recolectadas proyectando aleatoriamente los datos dispersos a un subespacio inferior (medición).
Y como entendí, el marco teórico de la detección de compresión se compone principalmente de 3 problemas, dispersión, medición y recuperación. Por escasez, se trata de buscar representaciones dispersas para cierta clase de señales, que es la tarea del aprendizaje del diccionario. Por medición, se trata de buscar una forma eficiente (eficiencia computacional y recuperable) para medir los datos (o proyectar datos para reducir el espacio de medición), que es la tarea del diseño de la matriz de medición, como la matriz Gaussiana aleatoria, la matriz aleatoria estructurada. ... Y por recuperación, son los escasos problemas de inversión lineal regularizados, l0, l1, l1-l2, lp, l-group, blabla ..., y los algoritmos resultantes son varios, búsqueda coincidente, umbral suave, umbral duro, búsqueda básica, bayesiana, ....
Es cierto que "cs es la minimización de la norma L1", y la norma L1 es un principio básico para cs, pero cs no es solo la minimización de la norma L1. Además de las 3 partes anteriores, también hay algunas extensiones, como la detección de compresión estructurada (grupal o modelo), donde también se explota la escasez estructurada, y se demuestra que mejora en gran medida la capacidad de recuperación.
Como conclusión, cs es un gran paso en la teoría de muestreo, ya que proporciona una forma eficiente de muestrear señales, siempre que estas señales sean lo suficientemente escasas . Entonces, cs es una teoría de muestreo , cualquiera que la vaya a usar como alguna técnica de clasificación o reconocimiento está confundiendo el principio. Y ocasionalmente, encuentro un papel titulado con "detección basada en compresión .....", y creo que el principio de ese papel es explotar la minimización de l1 en lugar de cs y es mejor usar "basado en la minimización de l1 ... ".
Si estoy equivocado, corrígeme por favor.
fuente
He revisado el documento y creo que tengo la idea general del método. El "secreto" del método es cómo obtener una representación escasa de la señal de entrada en el dominio de frecuencia. Los algoritmos anteriores usaban una especie de fuerza bruta para la ubicación del coeficiente disperso dominante. Este método utiliza en su lugar una técnica que se llama artículo de wiki "recuperación espacial" o "detección comprimida" aquí. El método exacto de recuperación dispersa utilizado aquí se parece al 'umbral duro', uno de los métodos dominantes de recuperación dispersa.
La técnica PS de recuperación dispersa / detección comprimida y conectada a la minimización de L1 se usa mucho en el procesamiento moderno de señales y especialmente en relación con la transformada de Fourier. De hecho, es imprescindible saberlo para el procesamiento moderno de señales. Pero antes de la transformación de Fourier se usaba como uno de los métodos para la solución del problema de recuperación dispersa. Aquí vemos lo contrario: escasa recuperación para la transformación de Fourier.
Buen sitio para una visión general de la detección comprimida: nuit-blanche.blogspot.com/
Respuesta de PPS al comentario anterior: si la señal de entrada no es exactamente escasa, es con pérdida.
Siéntete libre de corregirme si tengo un método incorrecto.
fuente