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.
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".
FUENTE :http://www.laflecha.net/canales/ciencia/noticias/nuevo-algoritmo-que-mejora-la-ftt-transformada-rapida-de-fourier
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".
FUENTE :http://www.laflecha.net/canales/ciencia/noticias/nuevo-algoritmo-que-mejora-la-ftt-transformada-rapida-de-fourier
