DFT und Multiplikations- / Faltungsäquivalenz

7

Gibt es eine einfache oder möglicherweise intuitive Erklärung dafür, dass mit der DFT die Vektormultiplikation in einer Domäne der zirkulären Faltung der Transformationen der Vektoren in der anderen Domäne entspricht?

Da eine DFT nur eine Multiplikation mit einer (speziellen) quadratischen Matrix ist, was ist mit dieser Matrix und der Matrixmultiplikation, die die obige Dualität ermöglicht?

fft fourier-transform dft hotpaw2
quelle

5

Wie Sie richtig sagen, kann die DFT durch eine Matrixmultiplikation dargestellt werden, nämlich die Fourier-Matrix . Andererseits "transformiert" die DFT eine zyklische Faltung in einer Multiplikation (da alle Fourier-Transformationsvarianten wie DFT, DTFT, FT eine ähnliche Eigenschaft haben, Faltung in Multiplikation umzuwandeln) und umgekehrt. $\mathbf{F}$

Um dies im Matrixbild zu verstehen, ist zu beachten, dass auch eine (kreisförmige) Faltung mit einer bestimmten Sequenz durch eine Matrixmultiplikation dargestellt werden kann. Insbesondere ist dies eine zirkulierende Matrix, eine spezielle Art einer Toeplitz-Matrix.

Also kann mit der zyklischen Faltung geschrieben werden als wobei die aus Einträgen des Vektors gebildete zirkulierende Matrix bezeichnet . $\mathbf{y} = \mathbf{c} * \mathbf{x}$ $*$ $\mathbf{y} = \mathbf{C}(\mathbf{c}) \mathbf{x}$ $\mathbf{C}$ $\mathbf{c}$

Wenn wir diese Gleichung mit der DFT "transformieren" (dh Multiplikation mit ), erhalten wir $\mathbf{F}$

$\widehat{\mathbf{y}} = \mathbf{F} \, \mathbf{C}(\mathbf{c}) \,\mathbf{F}^H\, \widehat{\mathbf{x}}$

mit und die jeweiligen DFTs (note für die IDFT). $\widehat{\mathbf{y}} =\mathbf{F}\mathbf{y}$ $\widehat{\mathbf{x}} =\mathbf{F}\mathbf{x}$ $\mathbf{F}^H$

Der Punkt ist nun, dass immer eine diagonale Matrix ist, da alle zirkulierenden Matrizen durch die Fourier-Matrix diagonalisiert werden. Dies bedeutet, dass die Eigenvektoren von zirkulierenden Matrizen nur durch die Zeilen der Fourier-Matrix gegeben sind. $\mathbf{F} \mathbf{C}(\mathbf{c}) \,\mathbf{F}^H$

Dies stimmt natürlich mit dem Faltungsbild überein, da die DFT die Faltung in eine elementweite Multiplikation umwandelt. Darüber hinaus sind die diagonalen Elemente dieser Matrix nur die DFT von oder gleich die Eigenwerte der aus gebildeten zirkulierenden Matrix . $\mathbf{c}$ $\mathbf{c}$

Andreas H.
quelle

Klar, ich habe gerade die Identitätsmatrix zwischen eingefügt

C (c)

$C(c)$ und

x

$x$ . Beachten Sie, dass

F^{H} F = I

$F^H F = I$ . Dies ist so, dass in der Gleichung auch die Fourier-Transformation von

x

$x$ erscheint.

F^{H} F = I

$F^H F = I$ liegt daran, dass die Fourier-Matrix eine einheitliche Matrix ist, genau wie die DFT eine einheitliche Transformation ist.

Andreas H.

Linke Seite von x. Beginnen mit

y = C (c) x

$y = C(c)x$ , mal

F

$F$ von links:

\hat{y} = F C (c) x

$\widehat{y} = F C(c) x$ dann einfügen

I = F^{H} F

$I = F^H F$ und bekomme

\hat{y} = F C (c) F^{H} F x

$\widehat{y} = F C(c) F^H F x$ welches ist

\hat{y} = F C (c) F^{H} \hat{x}

$\widehat{y} = F C(c) F^H \widehat{x}$

Andreas H.

Nein,

F C F^{H}

$FCF^H$ ist das, was sich aus der Ableitung ergibt, wäre falsch.

F^{H} C F

$F^H C F$

Andreas H.

2

Im Übrigen ist DFT die einzige bijektive lineare Transformation, die Faltung und termweise Multiplikation austauscht (natürlich bis zur Permutation der Koeffizienten). Dies ist nicht schwer zu beweisen, aber ich habe keinen Hinweis auf dieses Ergebnis gefunden, bevor ich es in Music Through Fourier Space , Thm. 1,11 (Springer 2016). Im kontinuierlichen Fall ist es chaotischer, weil man die beteiligten Funktionsräume gut auswählen muss.

Vielleicht könnte dieser Kehrwert auch mit zirkulierenden Matrizen und gleichzeitiger Diagonalisierung nachgewiesen werden.

E. Amiot
quelle

DFT und Multiplikations- / Faltungsäquivalenz

Antworten: