Python SciPy convolve vs fftconvolve

convolution

Question

Sé que, en términos generales, la FFT and multiplication suelen ser más rápidas que la operación de convolve directa, cuando la matriz es relativamente grande. Sin embargo, estoy convolviendo una señal muy larga (digamos 10 millones de puntos) con una respuesta muy corta (digamos 1 mil puntos). En este caso, el fftconvolve no parece tener mucho sentido, ya que obliga a una FFT de la segunda matriz al mismo tamaño que la primera matriz. ¿Es más rápido hacer convolución directa en este caso?

Answer 1

La convolución rápida de FFT mediante los algoritmos de superposición-adición o superposición guardada se puede realizar en una memoria limitada mediante el uso de una FFT que es solo un pequeño múltiplo (como 2X) mayor que la respuesta de impulso. Se rompe la FFT larga en FFT superpuestas, más cortas pero sin relleno.

Incluso con la sobrecarga de solapamiento, O (NlogN) vencerá M * N en eficiencia para N y M lo suficientemente grandes.

Answer 2

Gracias por tu ayuda. Ahora mismo hice la prueba, hice la convolución con 2 matrices, tamaño de 2 ^ 20 y 2 ^ 4, y este es el resultado:

numpy.convolve: 110 ms
scipy.signal.convolve: 1.0 s
scipy.signal.fftconvolve: 2.5 s

Entonces, tenemos un ganador, la convolvente numpy es mucho más rápida que las demás. Todavía no sé por qué.

Ahora probé 2 matrices más largas, tamaño de 2 ^ 22 y 2 ^ 10. El resultado es:

numpy.convolve: 6.7 s
scipy.signal.convolve: 221 s
scipy.signal.fftconvolve: MemoryError

La diferencia simplemente se hace más grande.

Answer 3

Echa un vistazo a la comparación que hice aquí:

http://scipy-cookbook.readthedocs.io/items/ApplyFIRFilter.html

Su caso podría estar cerca de la transición entre el uso de una convolución simple y el uso de la convolución basada en FFT, por lo que su mejor opción (como lo sugiere @Dougal en un comentario) es cronometrarlo usted mismo.

(Tenga en cuenta que no superpuse-agregue o superponga-guarde en esa comparación).