¿Cómo realizar convoluciones más rápidas usando Fast Fourier Transform (FFT) en Python?

La convolución es una de las operaciones matemáticas más importantes utilizadas en el procesamiento de señales. Esta simple operación matemática aparece en muchas aplicaciones científicas e industriales, desde su uso en una gran CNN de miles de millones de capas hasta la simple eliminación de ruido de imágenes. La convolución puede ser de naturaleza tanto analógica como discreta, pero debido a la naturaleza digital de las computadoras modernas, ¡la convolución discreta es la que vemos por todas partes!

La convolución discreta de dos vectores unidimensionales  y  ,   se define como

Como requiere la multiplicación de dos vectores, la complejidad temporal de la convolución discreta mediante la multiplicación (suponiendo vectores de longitud  ) es  . Aquí es donde entra en juego la transformada rápida de Fourier (FFT). ¡Usando FFT, podemos reducir esta complejidad de   a  !

La intuición detrás del uso de FFT para convolución

Uno de los resultados más fundamentales del procesamiento de señales establece que la convolución en el dominio del tiempo es equivalente a la multiplicación en el dominio de la frecuencia . Para realizar la convolución, podemos convertir ambas señales a sus representaciones en el dominio de la frecuencia y luego tomar la transformada inversa de Fourier del producto de Hadamard (o producto escalar) para obtener la respuesta complicada. El flujo de trabajo se puede resumir de la siguiente manera

Representación esquemática del flujo de trabajo de FFT

Instalación:

Para los propósitos de este artículo, usaremos algunas funciones integradas de las bibliotecas de Python numpy y scipy. Puede usar el administrador de paquetes pip para instalarlos.

pip install scipy numpy

Convolución FFT en Python

Para calcular la convolución usando FFT, usaremos la función fftconvolve() en la biblioteca scipy.signal en Python.

Sintaxis: scipy.signal.fftconvolve(a, b, mode=’full’)

Parámetros:

• a: primer vector de entrada
• b: segundo vector de entrada
• modo: ayuda a especificar el tamaño y el tipo de salida de convolución
  • ‘full’: la función devolverá la salida de convolución completa
  • ‘igual’: la función devolverá una salida con las mismas dimensiones que el vector ‘a’ pero centrada en el centro de la salida del modo ‘completo’
  • ‘válido’: la función devolverá solo aquellos valores que no se basaron en el relleno cero para ser calculados

A continuación se muestra la implementación:

from scipy import signal
  
a = [1, 2, 3]
b = [4, 5, 6]
  
y = signal.fftconvolve(a, b, mode = 'full')
print('The convoluted sequence is ', y)

Producción

The convoluted sequence is  [ 4. 13. 28. 27. 18.]

Comparación de rendimiento de convolución FFT con convolución discreta normal

• Para calcular la convolución lineal normal de dos vectores, usaremos la función np.convolve .
• La función mágica %timeit de los portátiles Jupyter se usó para calcular el tiempo total requerido por cada una de las 2 funciones para los vectores dados.

A continuación se muestra la implementación:

import numpy as np
from scipy import signal
  
a = np.random.randn(10**5)
b = np.random.randn(10**5)
  
print('Time required for normal discrete convolution:')
%timeit np.convolve(a, b)
  
print('Time required for FFT convolution:')
%timeit signal.fftconvolve(a, b)

Producción:

Time required for normal discrete convolution:
1.1 s ± 245 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Time required for FFT convolution:
17.3 ms ± 8.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

¡Puede ver que la salida generada por la convolución FFT es 1000 veces más rápida que la salida producida por la convolución discreta normal!