DFT y equivalencia de multiplicación / convolución

7

¿Existe una explicación simple o potencialmente intuitiva para que, con el DFT, la multiplicación de vectores en un dominio sea equivalente a la convolución circular de las transformaciones de los vectores en el otro dominio?

Dado que un DFT es solo la multiplicación por una matriz cuadrada (especial), ¿qué pasa con esta matriz y la multiplicación de la matriz permite la dualidad anterior?

hotpaw2
fuente

Respuestas:

5

Como usted dice correctamente, el DFT puede representarse mediante una multiplicación matricial, es decir, la matriz de Fourier . Por otro lado, el DFT "transforma" una convolución cíclica en una multiplicación (ya que todas las variantes de transformada de Fourier como DFT, DTFT, FT tienen una propiedad similar de transformar la convolución en multiplicación) y viceversa.F

Para comprender esto en la imagen de la matriz, tenga en cuenta que también la convolución (circular) con una secuencia determinada puede representarse mediante una multiplicación de la matriz. Más específicamente, esta es una matriz circulante, un tipo especial de matriz de Toeplitz.

entonces con la convolución cíclica se puede escribir como con denota la matriz circulante formada a partir de las entradas del vector .y=CXy=C(C)XCC

Si "transformamos" esta ecuación con el DFT (es decir, la multiplicación por ) obtenemosF

y^=FC(C)FHX^

con yy^=FyX^=FX los DFT respectivos (nota FH representa el IDFT).

El punto es ahora que FC(C)FHsiempre es una matriz diagonal, porque todas las matrices circulantes están diagonalizadas por la matriz de Fourier. Esto significa que los vectores propios de las matrices circulantes solo están dados por las filas de la matriz de Fourier.

Por supuesto, esto es consistente con la imagen de convolución, porque el DFT transforma la convolución en una multiplicación de todo el elemento. Además, los elementos diagonales de esta matriz son solo el DFT deCo, de manera equivalente, los valores propios de la matriz circulante formada a partir de C.

Andreas H.
fuente
Claro, acabo de insertar la matriz de identidad entre C(C) y X. Tenga en cuenta queFHF=yo. Esto es para que en la ecuación también la transformada de Fourier deX aparece. FHF=yoes porque la matriz de Fourier es una matriz unitaria, al igual que la DFT es una transformación unitaria.
Andreas H.
Lado izquierdo de x. Empezar cony=C(C)X, multiplicar por F desde la izquierda: y^=FC(C)X luego inserte yo=FHF y obten y^=FC(C)FHFX cual es y^=FC(C)FHX^
Andreas H.
No, FCFH es lo que resulta de la derivación, FHCFSería incorrecto.
Andreas H.
2

Por cierto, DFT es la única transformación lineal biyectiva que intercambia convolución y multiplicación de términos (hasta la permutación de los coeficientes, obviamente). Esto no es difícil de probar, pero no he encontrado ninguna referencia sobre este resultado antes de explicarlo en Music Through Fourier Space , Thm. 1.11 (Springer 2016). Es más desordenado en el caso continuo porque uno tiene que elegir bien los espacios de función involucrados.

Quizás este recíproco también podría probarse utilizando matrices circulantes y diagonalización simultánea.

E. Amiot
fuente