Una transformada rápida de Fourier

Una transformada rápida de Fourier

Nuevos algoritmo para procesar datos

Tomado de https://spectrum.ieee.org, David Schneider

Gilbert Strang , autor del clásico libro de texto de álgebra lineal y sus aplicaciones, una vez se refirió a la transformada rápida de Fourier o FFT , como "el algoritmo numérico más importante en nuestra vida." No es de extrañar. La FFT se utiliza para procesar los datos de todo altamente interconectado en el mundo digital de hoy. 

 No se podría iniciar sesión en una red Wi-Fi o hacer una llamada en su teléfono celular sin ellas. Así que cuando algunos de sus colegas del MIT de Strang anunció en enero en el Simposio ACM-SIAM de algoritmos discretos que habían desarrollado formas de acelerar sustancialmente el cálculo de la FFT, mucha gente tomó nota de esta afirmación.

"Las FFT, se ejecutan miles de millones de veces al día," dice Richard Baraniuk , profesor de ingeniería eléctrica e informática en la Universidad de Rice, en Houston y un experto en el campo emergente de la detección de compresión, que tiene mucho en común con los enfoques que ahora se aplican para acelerar el cálculo de FFT.

Los esfuerzos para mejorar el cálculo de las transformadas de Fourier tienen una historia larga y generalmente pasada por alto. Aunque la mayoría de los ingenieros asocian la FFT con el procedimiento James Cooley de IBM y John Tukey de Princeton descritos en 1965, los especialistas reconocen que tiene muchas raíces más profundas.  Dado que las grandes mentes matemáticas han estado pensando en la manera de acelerar este cálculo particular, durante más de dos siglos, ¿cómo es que todavía se está avanzando? La razón fundamental es que los nuevos métodos están diseñados para correr rápido sólo para algunas señales que se denominan "escasas", ya que contienen un número relativamente pequeño de componentes de frecuencia de tamaño significativo. La FFT tradicional toma la misma cantidad de tiempo de cálculo para cualquier señal.

Imágenes y análisis: Steve Haroz

Escasez cotidiana: las señales naturales [top] son a menudo "escasas", lo que significa que tienen relativamente pocos componentes de frecuencia de importancia. Una imagen aleatoria [abajo], sin embargo, contiene elementos importantes en todas las frecuencias. El nuevo algoritmo de la transformada rápida de Fourier acelera cálculos en sólo señales dispersas.

"La mayoría de las señales son escasas", dice Katabi, quien señala que cuando se envía, por ejemplo, un archivo de vídeo a través de canales inalámbricos, transmitiendo solamente un pequeño porcentaje del contenido de frecuencia suele ser suficiente y en línea con los niveles de escases que de su grupo manejan bien nuevos algoritmos. 

Speedy: Un nuevo algoritmo de MIT, que se describe como  mejor que la tradicional FFT siempre y cuando el número de componentes de frecuencia presenta un porcentaje de un dígito del número de muestras que toma de la señal. Funciona para cualquier señal, pero funciona más rápido que el FFT solamente bajo esas condiciones, dice Indyk.

Los expertos dicen que los nuevos algoritmos procedentes de MIT representan un progreso considerable. "Se han añadido algunas ideas muy inteligentes a la receta", dice Marcos Iwen de la Universidad de Duke, en Durham, Carolina del Norte, que antes había trabajado en el mismo problema con Anna Gilbert y Martin Strauss de la Universidad de Michigan

ID