La transformada de Fourier es fundamental en la ciencia del procesamiento de señales y es muy práctica al procesar imágenes, sonido o compresión de video, así como en técnicas de filtrado y reconstrucción. Por eso simplemente es importante. Sin embargo, por mucho tiempo esta herramienta matemática fue de difícil uso por el tiempo que consumía al usarse. Y era a tal grado el problema que en muchos casos la transformada de Fourier se usaba para demostrar qué se podría hacer, pero era siempre en ejemplos relativamente triviales.
En el dominio digital, una transforma de Fourier es una multiplicación de matrices, una rotación de hecho, que te saca del dominio espacial al dominio de la frecuencia. Esto es, uno da la amplitud en varios puntos del tiempo y la transformada regresa un vector de amplitudes de frecuencia y fase en varios puntos de la frecuencia. Como hablamos de una multiplicación de matrices, el algoritmo toma n^2 operaciones para un vector de tamaño n, lo cual significa que es muy difícil trabajar con conjuntos muy grandes.
La invención de la transformada rápida de Fourier, por J.W. Cooley y John Tukey en 1965, conocida simplemente como el algoritmo Cooley-Turkey en ese momento, tuvo un gran impacto. Lo sorprendente es que ya había sido inventado antes, aparentemente por Gauss, en 1805, pero ¡fue ignorado en su tiempo!. El impacto de la FFT (Fast Fourier Transformation), fue enorme. Abrió todo género de posibilidades en el procesamiento de señales e imágenes y en la inteligencia artificial. Muchos creen que es el algoritmo numérico más importante con el que disponemos y parece ser que no es una exgaeración.
La idea básica de la FFT es simplemente usar la estrategia de dividir y conquistar. Si el tamaño del vector de datos n es factorizable, se puede calcular la transformada de Fourier en partes y unir el resultado para llegar a un resultado completo. La FFT -se puede probar- tarda n log n, lo cual es una mejora sustancial a n^2, para n muy grande.
Hasta hace poco, la FFT era lo mejor que teníamos, pero no se sabía si era el algoritmo óptimo. Con esto en mente, un grupo de investigadores del MIT pudo demostrar un algoritmo que tarda k log n. Este algoritmo toma el vector de datos n y regresa los k componentes más grandes de Fourier, lo cual es la máxima compresión y el algoritmo más aproximado para manipular la señal.
El algoritmo no saca ventaja de la simetría, sino que usan filtros para dividir el ancho de banda. Los filtros, gausianos y Dolph-Chebyshev se construyen de tal manera que se pueden sobreponer de la manera correcta para no perder componentes significativos. Después de esto, una búsqueda divisible es usada para aislar las regiones que contienen coeficientes de Fourier significativos. La transformada resultante es una aproximación de la verdadera transformada, pero su precisión puede cuantificarse.
Todo lo anterior significa que, usando este enfoque, se pueden implementar compresión mp3 y mp4 más rápidamente con un procesador menos poderoso, incluso. Esto es un hito en el terrenos del procesamiento de señales. Como resultado del mismo, el algoritmo puede procesar sonido, imagen o cualquier otra colección de datos más rápido que nunca antes.
Sin embargo, no es tan elegante como el algoritmo tradicional de la FFT, pero hace la tarea ¿o no?
Fuente: i-programmer
Para saber más: Simple and Practical Algorithm for Sparse Fourier Transform; Haitham Hassanieh, Piotr Indyk ,Dina Katabi, and Eric Price.