Transformada de Fourier para series de tiempo Convolución rápida explicada con numpy

Transformada de Fourier para series de tiempo con Convolución rápida utilizando numpy.

Implementación desde cero vs numpy

El algoritmo de la transformada de Fourier se considera uno de los mayores descubrimientos en toda las matemáticas. El matemático francés Jean-Baptiste Joseph Fourier sentó las bases del análisis armónico en su libro “Théorie analytique de la chaleur” en 1822. Hoy en día, la transformada de Fourier y todas sus variantes forman la base de nuestro mundo moderno, impulsando tecnologías como la compresión, la comunicación, el procesamiento de imágenes.

Este maravilloso marco también proporciona grandes herramientas para analizar series de tiempo… ¡y por eso estamos aquí!

Esta publicación es parte de una serie sobre la transformada de Fourier. Hoy hablaremos sobre la convolución y cómo la transformada de Fourier proporciona la forma más rápida de hacerla.

Todas las figuras y ecuaciones son creadas por el autor.

Definición de la Transformada Discreta de Fourier (DFT)

Comencemos con definiciones básicas. La transformada discreta de Fourier para una secuencia de tiempo discreta x de N elementos es:

• EDA con Polars Guía paso a paso para usuarios de Pandas (Parte 1)
• Desbloqueando el éxito del modelado de datos 3 tablas contextuales ...
• Investigadores de la Universidad de Wisconsin y ByteDance presentan...

donde k representa la k-ésima frecuencia del espectro de x. Nótese que algunos autores añaden un factor de escala de 1/N a esa definición, pero no tiene gran importancia para esta publicación, al fin y al cabo es solo una cuestión de definición y adherirse a ella.

La transformada inversa de Fourier es entonces (dada la definición para la transformada de Fourier directa):

Dicho esto, uno de los teoremas más importantes sobre la transformada de Fourier es que la convolución en un espacio es equivalente a la multiplicación en el otro. En otras palabras, la transformada de Fourier de un producto es la convolución de los respectivos espectros de Fourier, y la transformada de Fourier de una convolución es el producto de los respectivos espectros de Fourier.

y

donde el punto representa el producto estándar (multiplicación) y la estrella en círculo representa la convolución circular.

Two important notes:

• Señal periódica: El marco de análisis de Fourier considera que las señales que manejamos son periódicas. En otras palabras, se repiten desde menos infinito hasta infinito. Sin embargo, no siempre es práctico manejar señales de este tipo con una computadora de memoria finita, por lo que solo “jugamos” con un período, como veremos a continuación.
• Convolución circular: El teorema de la convolución establece que la multiplicación es equivalente a la convolución circular, que es un poco diferente de la convolución lineal a la que estamos más acostumbrados. Como veremos, no es tan diferente y tampoco es tan complicado.

Convolución circular vs convolución lineal

Si estás familiarizado con la convolución lineal, a menudo simplemente referida como ‘convolución’, no te confundirás con la convolución circular. Básicamente, la convolución circular es simplemente la forma de convolver señales periódicas. Como puedes suponer, la convolución lineal solo tiene sentido para señales de longitud finita, que no se extienden desde menos infinito hasta infinito. En nuestro caso, en el contexto del análisis de Fourier, nuestras señales son periódicas y por lo tanto no cumplen con esta condición. No podemos hablar de convolución (lineal).

Sin embargo, aún podemos intuir una operación similar a la convolución lineal en nuestras señales periódicas: simplemente convolvemos la señal periódica en una longitud de un período. Eso es lo que hace la convolución circular: convoluciona 2 señales periódicas de la misma longitud a lo largo de un período.

Para convencerte aún más de la diferencia, compara ambas fórmulas para la convolución lineal discreta y la convolución circular discreta:

Observa las diferencias:

– Límites: la convolución lineal utiliza muestras desde menos infinito hasta más infinito, como se mencionó anteriormente, en este contexto x e y tienen energía finita, la suma tiene sentido. Para la convolución circular, solo necesitamos lo que sucedió en un período, por lo que la suma solo abarca un período.

– Índices circulares: en la convolución circular, “envolvemos” el índice de y utilizando una operación de módulo con una longitud de N. Esto es solo una forma de asegurarnos de que y se considere periódica con un período de N: cuando queremos conocer el valor de y en la posición k, simplemente usamos el valor de y en la posición k%N, dado que y es N periódica, obtenemos el valor correcto. Nuevamente, esta es solo una forma matemática de manejar secuencias de muestras periódicas de longitud infinita.

Implementación en numpy

Numpy proporciona excelentes herramientas para señales de longitud finita: y eso es una buena noticia porque, como acabamos de ver, nuestra señal periódica de longitud infinita se puede representar con solo un período.

Creemos una clase simple para representar tales señales. Agregamos un método para trazar rápidamente el arreglo, así como un período adicional antes y después del arreglo “base”, para tener en cuenta que estamos tratando con una secuencia periódica.

Veamos dos ejemplos: primero con una secuencia sinusoidal muestreada, luego con una secuencia lineal. Ambas se consideran N-periódicas (N = 10 en este caso).

Convolución circular, el método lento

Ahora implementemos la ecuación de convolución circular vista anteriormente. Utilizando indexación y el operador módulo, es bastante sencillo:

Eso es genial, ahora podemos ver cómo se ve la convolución circular entre dos señales. Poniéndolo todo en una sola figura:

Ahora esta solución funciona muy bien, pero tiene una gran falla: es lenta. Como puedes ver, tenemos que recorrer 2 bucles anidados para calcular el resultado: uno para cada posición en el arreglo resultante y otro para calcular el resultado en esa posición: decimos que el algoritmo es O(N²), a medida que N aumenta, el número de operaciones aumentará al cuadrado de N.

Para arreglos pequeños como los del ejemplo, no es un problema, pero a medida que tu arreglo crezca, se convertirá en un problema importante.

Además, los bucles en datos numéricos se consideran la mayoría de las veces una mala práctica en Python. Debe haber una mejor manera…

Convolución circular, el modo Fourier

Y ahí es donde entra en juego la transformada de Fourier y el teorema de la convolución. Debido a la forma en que se implementa la transformada discreta de Fourier, de manera muy rápida y optimizada utilizando la Transformada Rápida de Fourier (FFT), la operación es **muy** rápida (decimos que la FFT es O(N log N), lo cual es mucho mejor que O(N²)).

Usando el teorema de la convolución, podemos usar el hecho de que el producto de la DFT de 2 secuencias, cuando se transforma de nuevo al dominio del tiempo usando la DFT inversa, obtenemos la convolución de las secuencias de tiempo de entrada. En otras palabras, tenemos:

donde DFT representa la transformada discreta de Fourier, e IDFT la operación inversa.

Luego podemos implementar este algoritmo para calcular la convolución de x e y usando numpy muy fácilmente:

Comparación numérica y de tiempo

Para terminar, verifiquemos que ambos enfoques produzcan los mismos resultados y comparemos el tiempo que le lleva a Python calcular la convolución circular utilizando ambas técnicas:

¡Es una coincidencia perfecta! Ambos son rigurosamente equivalentes en términos de valores numéricos.

Ahora, para la comparación de tiempo:

Y los resultados son:

• para N=10 muestras, la DFT es más rápida por un factor de 6
• para N=1000 muestras, la DFT es más rápida por un factor de aproximadamente 10000

¡Eso es enorme! ¡Considera ahora lo que puede ofrecerte cuando analices tus series de tiempo con miles y miles de muestras!

Conclusión

Hemos visto en esta publicación que la transformada de Fourier es una herramienta poderosa, especialmente gracias al teorema de la convolución que nos permite calcular la convolución de manera muy eficiente. Hemos visto que la convolución lineal y la circular no son exactamente la misma operación, pero ambas se basan en una convolución.

¡Suscríbete para recibir futuras publicaciones sobre la transformada de Fourier directamente en tu feed!

También, echa un vistazo a mis otras publicaciones y si te gusta alguna de ellas, por favor suscríbete. ¡Me ayuda mucho a alcanzar mi objetivo de 100 suscriptores!

Resolución 300 veces más rápida del Método de Diferencias Finitas utilizando NumPy | por Yoann Mocquin | Towards Data Science (VoAGI.com)

PCA/LDA/ICA: una comparación de algoritmos de análisis de componentes | por Yoann Mocquin | Towards Data Science (VoAGI.com)

Envolviendo el array de NumPy. El enfoque de contenedor. | por Yoann Mocquin | Towards Data Science (VoAGI.com)

Profundizando en Seaborn: Paletas de colores | por Yoann Mocquin | Analytics Vidhya | VoAGI

• Convolution
• Fourier Transform
• Machine Learning
• Numpy
• Time Series Analysis