La transformada rápida de Fourier, aún más rápida

Artículo publicado por Larry Hardesty el 18 de enero de 2012 en MIT

Para un gran rango de casos de utilidad práctica, los investigadores del MIT encuentran una forma de aumentar la velocidad de uno de los algoritmos más importantes en las ciencias de la información.

La transformada de Fourier es uno de los conceptos más fundamentales en las ciencias de la información. Es un método para representar una señal irregular – como fluctuaciones de voltaje en un cable que conecta un reproductor MP3 con un altavoz – en forma de combinación de frecuencias puras. Es universal en el procesado de señales, pero también puede usarse para comprimir ficheros de imagen y audio, resolver ecuaciones diferenciales y valorar las opciones sobre acciones, entre otras cosas.

La razón de que la transformada de Fourier sea tan predominante es un algoritmo conocido como Transformada Rápida de Fourier (Fast Fourier Transform- FFT), desarrollado a mediados de la década de 1960, que hizo viable calcular las transformadas de Fourier sobre la marcha. Desde que se propuso la FFT, no obstante, la gente se ha preguntado si podría encontrarse un algoritmo aún más rápido.

FFT © by hazure


En el Simposio de Algoritmos Discretos de la Asociación de Maquinaria de Cálculo (SODA) de esta semana, un grupo de investigadores del MIT presentará un nuevo algoritmo que, en un amplio rango de casos de importancia práctica, mejora a la FFT. Bajo ciertas circunstancias, la mejora puede ser drástica – un incremento de hasta 10 veces en la velocidad. El nuevo algoritmo podría ser particularmente útil para la compresión de imágenes, permitiendo, digamos, que los smartphones transmitan a través de wi-fi grandes archivos de video sin agotar sus baterías, o consumir tu cuota mensual de ancho de banda.

Como la FFT, el nuevo algoritmo trabaja con señales digitales. Una señal digital es, simplemente, una serie de números – muestras discretas de una señal analógica, tal como el sonido de un instrumento musical. La FFT toma una señal digital que contiene un cierto número de muestras y las expresa como la suma ponderada de un número equivalente de frecuencias.

“Ponderada” indica que algunas de esas frecuencias cuentan más para el total que otras. Es más, muchas de las frecuencias pueden tener una ponderación tan baja que pueden descartarse sin problema. Por esto es por lo que la FFT es útil para la compresión. Un bloque de 8×8 píxeles puede verse como una señal de muestra 64, y por tanto como la suma de 64 frecuencias distintas. Pero, como señalan los investigadores en su nuevo artículo, los estudios empíricos demuestran que, de media, 57 de esas frecuencias pueden descartarse con una mínima pérdida de calidad en la imagen.

División muy ponderada

Las señales cuyas FFT incluyen un número relativamente bajo de frecuencias muy ponderadas se conocen como “poco densas” (sparse). El nuevo algoritmo determina la ponderación de las frecuencias de mayor peso de una señal; cuanto menos densa sea la señal, mayor será la aceleración que proporciona el algoritmo. Es más, si la señal es lo bastante poco densa, el algoritmo puede simplemente muestrearla aleatoriamente en lugar de leerla por completo.

“En la naturaleza, la mayor parte de las señales son poco densas”, dice Dina Katabi, una de las desarrolladoras del nuevo algoritmo. Ten en cuenta, por ejemplo, la grabación de una pieza de música de cámara: La señal compuesta consta de sólo unos pocos instrumentos, cada uno tocando una única nota en cada instante. Una grabación, por otra parte, de todos los posibles instrumentos tocando cada uno todas las notas posibles a la vez, sería poco densa – pero tampoco sería una señal que interesara a nadie.

El nuevo algoritmo – que la Profesora Asociada Katabi y el profesor Piotr Indyk, ambos del Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT (CSAIL), desarrollaron junto a sus estudiantes Eric Price y Haitham Hassanieh – se basa en dos ideas clave. La primera es dividir una señal en dos anchos de banda más estrechos, de un tamaño que cada porción generalmente contenga sólo una frecuencia de gran peso.

En el procesado de señales, la herramienta básica para aislar frecuencias particulares es el filtro. Pero los filtros tienden a tener límites difusos: un rango de frecuencias pasará a través del filtro más o menos intacto; las frecuencias justo fuera del rango se verán algo atenuadas; las frecuencias más lejos del rango se atenuarán aún más; y así sucesivamente, hasta que alcanzas las frecuencias que se filtran casi perfectamente.

Si sucede que la frecuencia con el peso importante está en el límite del filtro, sin embargo, podría terminar tan atenuada que no pueda identificarse. Por lo que la primera contribución de los investigadores fue encontrar una forma computacionalmente eficiente de combinar filtros de forma que se solaparan, asegurando que ninguna frecuencia dentro del rango deseado se atenuase indebidamente, pero que los límites entre las porciones del espectro quedasen bien definidas.

Apuntando

Una vez que aislaron una porción del espectro, sin embargo, los investigadores aún tenían que identificar la frecuencia de mayor peso en esa porción. En el artículo de SODA, hacen esto cortando repetidamente la porción del espectro en trozos menores y guardando sólo aquellos en los que se concentra la mayor parte de la potencia de la señal. Pero, en un artículo aún por publicar, describen una técnica mucho más eficiente, la cual toma prestada una estrategia de procesado de señales de las redes móviles 4G. Las frecuencias normalmente se representan como garabatos arriba y abajo, pero también pueden verse como oscilaciones; muestreando la misma porción de ancho de banda en distintas escalas temporales, los investigadores pueden determinar dónde está la frecuencia dominante dentro de su ciclo oscilatorio.

Dos investigadores de la Universidad de Michigan – Anna Gilbert, Profesora de Matemáticas, y Martin Strauss, Profesor Asociado de Matemáticas, Ingeniería Eléctrica y Ciencias de la Computación – habían propuestos anteriormente un algoritmo que mejoraba la FFT para señales muy poco densas. “Parte del trabajo previo, incluyendo el mío con Anna Gilbert y otros, mejorarían el algoritmo de la FFT, pero sólo si la densidad k” – el número de frecuencias de gran peso – “era considerablemente menor que el tamaño de entrada n”, comenta Strauss. Sin embargo, el algoritmo de los investigadores del MIT, “expande mucho el número de circunstancias bajo las que se puede superar a la FFT tradicional”, señala Strauss. Incluso si el número k empieza a acercarse a n – siendo todos significativos – este algoritmo proporciona algo de mejora sobre la FFT”.


Autor: Larry Hardesty
Fecha Original: 18 de enero de 2012
Enlace Original

Comparte:
  • Print
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Twitter
  • Google Bookmarks
  • Bitacoras.com
  • Identi.ca
  • LinkedIn
  • Meneame
  • Netvibes
  • Orkut
  • PDF
  • Reddit
  • Tumblr
  • Wikio
This page is wiki editable click here to edit this page.

Like This Post? Share It

Comments (8)

  1. Una de las grandes sorpresas de la asignatura de óptica de 4º fue saber que en el foco de una lente no hay un punto… está la transformada de Fourier del plano objeto (salvo factor de fase, para los puristas)… acojonante. Eso permite hacer filtrado óptico de señales, la pera. Saludos

  2. Información Bitacoras.com…

    Valora en Bitacoras.com: Artículo publicado por Larry Hardesty el 18 de enero de 2012 en MIT Para un gran rango de casos de utilidad práctica, los investigadores del MIT encuentran una forma de aumentar la velocidad de uno de los algoritmos más im……

  3. [...] velocidad de uno de los algoritmos más importantes en las ciencias de la información. En español http://www.cienciakanija.com/2012/01/18/la-transformada-rapida-de-fourier-aun etiquetas: transformada de fourier, algoritmo, ciencias de la información negativos: [...]

  4. Tom Wood

    Al margen de que hay personas que tienen siempre explicaciones para todo,… Nunca he podido imaginar que cosa es lo que nos quieren decir las transformadas de Fourier, que es la naturaleza. Las transformadas de Fourier, son como un “acido intelectual” que coge las cosas (ondas, partículas, lo que sea,… no imagino hasta donde podrán llegar) y las vuelve un plástico, una plastilina, que podemos picar, deshilachar, endurecer las partes que queramos, desechar los retazos, en fin moldear en las esencias que queramos; para después, juntar las que necesitamos (transformarlas) en su esencia o en una esencia amigablemente útil. Siempre nos tienen asustados, pensando en que lo que desechamos, en algún momento va a salir, que era importante; que nos va a decir, la suma de las partes es el todo. Es como modelar un auto a partir de otro que ya existe, con las piezas de otro, y que el resultado final se ajuste a nuestros gustos y caprichos, aun así, aunque te sobren piezas del motor; lo que por lógica no daría un buen auto, pero increíblemente, aunque sabes que esta incompleto, no logras encontrar, o ver las diferencias con el anterior. Sigue siendo un buen auto. Parece como si para ella todo fuera maleable, voluble, inconsistente; nada es nada, ni todo es todo. En esencia nada es completamente sólido, ni nada, definitivamente pertenece a nada o a nadie. Son tan plásticas que nunca dejan de sorprendernos. Todo un misterio, una confusión para el intelecto, para nuestros limitados sentidos, para nuestra percepción; que la física-matemática, no le aclaran a su filosofía general. No es una definición muy rigurosa, pero si muy humana. ¡Me gustan, me encantan las transformadas!
    http://www.youtube.com/watch?v=CkGtzoVgDgc
    http://www.youtube.com/watch?v=KlsgDuzdqac&feature=related
    http://www.youtube.com/watch?v=wmqPnnJaaiA

  5. David

    Excelente noticia! Esto significa que las espectofotometrías con detectores fotoeléctricos tipo CCD serán más veloces en el procesamiento de datos, lo que significa más resolución con un flujo de datos mayor y en el mismo tiempo que ahora, esto es bueno para la química y la astronomía en especial.

  6. angel

    ups y para la música no te digo nada!, el espectro de frecuencias a mi alcance ajaja!.

  7. Estimados amigos:

    quiero compartiros una auténtica novedad en los terrenos literario y matemático, la publicación de “Πoetas primera antología de poesía con matemáticas”. Os remito aquí (http://www.edicionesamargord.com/Poetas-primera-antologia-de-poesia-con-matematicas) a la web de la editorial.

    Un saludo.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *