NeoFronteras

Consiguen mejorar aún más la transformada rápida de Fouier. La nueva versión se mucho más rápida.

No somos conscientes del gran impacto que tiene las Matemáticas en la vida cotidiana. Son odiadas por muchos e ignoradas por otros y, sin embargo, conforman el mundo moderno. Además de ser usadas por las demás ciencias se emplean directamente en muchos casos.
Un resultado de un abogado francés del siglo XVII (el pequeño teorema de Fermat) es el que ahora nos permite conectarnos de manera segura con nuestro banco. Un concepto como el de autovector usando en Álgebra es el que, en el corazón de Google, nos permite encontrar lo que buscamos en Internet. Esto por citar sólo dos ejemplos.
Una rama matemática importante es el Análisis de Fourier, que permite, entre otras cosas, representar una señal irregular como una combinación de sus frecuencias puras, como pueda ser la fluctuación en el voltaje de la corriente que circula por un cable que conecta su reproductor de MP3 si sus auriculares. El análisis de Fourier se utiliza mucho en el procesamiento de señales o para la compresión de ficheros de imagen o sonido.
Permite además transformar problemas diferenciales en problemas algebraicos que se puedan resolver. Un ejemplo típico es la búsqueda de bolsas de petróleo mediante problemas inversos. Se envían ondas sonoras (mediante explosiones) al terreno y se trata de reconstruir la posible bolsa de petróleo que hay ahí a partir de la señal rebotada. Para este tipo de problema inverso hay que ensayar multitud de posibles configuraciones de la bolsa hasta dar con la correcta. Esto exige resolver el mismo tipo de problema muchas veces cambiando los parámetros que lo determinan. Sólo con el uso de la transformada rápida de Fourier se pudo abordar ese problema. Un problema computacional que no es abordable en un momento sólo se puede abordar si se encuentran algoritmos nuevos más rápidos, no con computadoras más rápidos y potentes. Sin la transformada rápida de Fourier muchos problemas computacionales aún no serían abordables.
La transforma de Fourier es una operación matemática que permite descomponer una función en sus frecuencias constituyentes. Se define como una integral definida y no necesariamente se calcula de manera sencilla si se usan métodos analíticos. El adjetivo de “rápida” que se añade se refiere a una clase especial de transformada de Fourier. La definición de transformada de Fourier habitual es muy difícil y costosa de aplicar computacionalmente hablando. La transformada rápida de Fourier o FFT es una versión numérica, una buena aproximación a la original, y que implementada en un programa se calcula bastante rápido.
Desde que se descubrió la transformada rápida de Fourier en los años sesenta los expertos se han preguntado si habría otras versiones aún más rápidas. Ahora un grupo de investigadores del MIT presentan un nuevo algoritmo que permite hacer que la transformada de Fourier sea más rápida. En algunos casos puede llegar a ser 10 veces más rápida que la antigua versión. El nuevo algoritmo ha sido presentado en el Congreso de Algoritmos Discretos en Kioto (Japón) la semana pasada.
El nuevo algoritmo permitiría un tratamiento de imágenes más rápido o enviar un video desde un teléfono celular a otro sin consumir mucho ancho de banda o batería.
Una señal digital es un muestreado discreto de una señal analógica. La FFT toma una señal digital que contiene un determinado número de muestras y las expresa en función del peso ponderado de su equivalente en número de frecuencias. La ponderación tiene en cuenta que algunas frecuencias son más importantes que otras y las que tienen poco peso pueden ser incluso despreciadas. Por esta razón la FFT es importante en la comprensión. Un bloque 8 por 8 píxeles contiene 64 píxeles en total y puede ser determinado directamente por 64 frecuencias distintas (cada píxel de un determinado valor aparece una sola vez). Pero los estudios experimentales muestran que 57 de esas frecuencias pueden ser descartadas con una pérdida mínima de calidad de imagen.
El nuevo algoritmo determina los pesos de las frecuencias más pesadas de la señal. A esto se le puede denominar “dispersar”. Cuando más rápidamente se determinen estas frecuencias, más rápido será el algoritmo y esto dependerá de lo susceptible que sea la señal a ser “dispersada”. Si la señal es lo suficientemente “dispersa” el algoritmo puede muestrearla aleatoriamente en lugar de leerla completamente.
Pero en la Naturaleza la mayoría de las señales son dispersas. Como analogía podemos tomar una pieza musical de cámara realizadas por instrumentos musicales. En ese caso, una señal podría consistir en unos pocos instrumentos musicales de los que sólo uno toca una nota cada vez. Este tipo de señal se podría “dispersar” fácilmente por este método, sería una señal “dispersa”. Pero, por otro lado, una grabación que registrara todos los posibles instrumentos tocando todas las notas a la vez no sería una señal que se pudiera “dispersar”, pero ese tipo de señales no son interesantes.
El nuevo algoritmo descansa sobre dos ideas. La primera es dividir la señal en secciones más delgadas de ancho de banda, justo a un tamaño en el que la sección considerada generalmente contiene sólo una frecuencia con gran peso. Esto permite determinar la importancia de la frecuencia dentro de cada conjunto. Para conseguir identificar la importancia de la frecuencia dentro de cada conjunto usan un filtro que es una combinación de dos ya existentes.
Además, estos investigadores aplican una segunda idea: usar una técnica que normalmente se emplea para mejorar las comunicaciones inalámbricas. La técnica se basa en que las frecuencias más importantes modulan otras señales en el conjunto. Muestreando rápidamente el conjunto a diferentes momentos se revelan qué frecuencias dominan la señal.
En señales dispersas este nuevo algoritmo es mucho más rápido que al anterior. Estos investigadores trabajan ahora en cómo incorporar el nuevo algoritmo a las técnicas de compresión de video y audio usados en la actualidad.
Así que si el smarphone que le hagan comprar en un futuro tiene unas prestaciones mucho mejores que el actual, estas se deberán en gran parte a este nuevo algoritmo.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=3724

Fuentes y referencias:
Nota de prensa.
Ilustración: csee.umbc.edu