¿Qué es una explicación intuitiva de la matriz DFT W?

Answer 1

donde [math] \ omega = e ^ {- 2 \ pi i / N} [/ math]. El DFT debería devolver un vector que corresponde a los coeficientes de Fourier de la señal de entrada, que se considera una muestra de un ciclo en una repetición infinitamente larga de ese mismo ciclo. Para una muestra de longitud 8, esto se ve así:

… x5 x6 x7 x8 [x1 x2 x3 x4 x5 x6 x7 x8] x1 x2….

Sabemos que podemos descomponer cualquier señal en sinusoides, pero para una señal periódica como esta solo hay algunas sinusoides que pueden ser parte de esto. En el período de tiempo de [x1 x2 x3… xN-1 xN x1], podemos tener 0 oscilaciones (CC), 1 oscilación completa (frecuencia [matemática] 1 / N \ Delta t [/ matemática]) y así sucesivamente. Esto sube a N-1 oscilaciones completas, porque no se puede distinguir la diferencia entre N oscilaciones y ninguna oscilación debido al muestreo finito (ver Aliasing).

La primera fila de W calcula el componente DC Fourier de manera similar a

[matemáticas] X_ {0} = \ int x (t) e ^ {- 2 \ pi i 0t} \, dt [/ matemáticas]

pero con un resumen en su lugar. La segunda fila calcula el componente de Fourier correspondiente a una oscilación completa, con frecuencia [matemática] 1 / N \ Delta t [/ matemática]:

[matemáticas] X_ {1} = \ int x (t) e ^ {- 2 \ pi it / N \ Delta t} \, dt [/ math]

Si cambia eso a una suma, encontrará que [math] t / \ Delta t [/ math] es solo el índice de su serie de tiempo. Entonces quieres tomar la suma de [math] x_i [/ ​​math] multiplicado por [math] \ omega [/ math] elevado a la potencia del índice.

La tercera fila es para dos oscilaciones completas con el doble de frecuencia, y funciona [math] x_i [/ ​​math] multiplicado por [math] \ omega [/ math] elevado a la potencia del doble del índice y así sucesivamente. De esta manera, el DFT le proporciona los componentes estimados de Fourier hasta un factor de las sinusoides que pueden reproducir la muestra que tiene, si se supone que se repite infinitamente, y limitada por alias.

Answer 2

tldr:

Una matriz DFT es una expresión de una transformada de Fourier discreta (DFT) como una multiplicación de matriz

En otras palabras, la matriz DFT puede (según la versión que use) calcular el valor de los valores del dominio original / temporal de una función sinusoidal o, si usa su inversa, calcular los coeficientes que generan esas muestras.

---

Esta respuesta es más para desarrollar la intuición, que ser súper riguroso. Seré riguroso si conozco los detalles.

Primero recuerde el DFT de Wikipedia:

En matemáticas, la transformada discreta de Fourier ( DFT ) convierte una lista finita de muestras igualmente espaciadas de una función en la lista de coeficientes de una combinación finita de sinusoides complejos, ordenados por sus frecuencias, que tienen esos mismos valores de muestra. Se puede decir que convierte la función muestreada de su dominio original (a menudo tiempo o posición a lo largo de una línea) al dominio de frecuencia.

Entonces la transformada de Fourier y su inversa hacen dos cosas.

1. Obtenga los coeficientes que expresan su función sinusoidal (es decir, obtenga la “función” real)
2. Obtenga muestras de su señal utilizando la sinusoide.

Diferentes autores definen la matriz DFT de manera diferente, ya sea con el conjugado de la raíz de la unidad [matemáticas] \ omega [/ matemáticas] o con la raíz real de la unidad [matemáticas] w = e ^ {\ frac {2 \ pi i} { n}} [/ matemáticas]. Prefiero la raíz real de la unidad porque para mí es más natural pensar en la función real que le da las muestras del dominio del tiempo / original en lugar de los coeficientes en el dominio de la frecuencia. Además, Gilbert Strang usa eso y me gusta su libro de álgebra lineal y la explicación que proporcionaré fue una inspiración de su capítulo sobre FFT.

De todos modos, esta es mi interpretación. Del artículo de wikipedia, observe que obtenemos una lista de números. Sabemos que proviene de una función / fuente sinusoidal. También sabemos que es discreto. Sin embargo, queremos saber cuál es la función en realidad. Pero sabemos que podemos escribirlo como una serie finita de Fourier. Pero la clave es que obtenemos una lista de números , es decir, un vector [matemática] y = [y_0, …, y_ {n-1}] [/ matemática] que es una muestra de su dominio original. Por lo tanto, utilizaremos todo este conocimiento para construir un sistema lineal de ecuaciones para obtener los coeficientes de la serie de Fourier y obtener la función que queríamos que describe la serie de Fourier.

Entonces continuemos. También sabemos que la función tiene la forma:

[matemáticas] f (x) = \ sum_ {k = 1} ^ n c_k e ^ {ikx} [/ matemáticas]

Para cada muestra [matemática] y_j [/ matemática] que obtenemos, construimos una ecuación que queremos satisfacer (es decir, construimos las filas de nuestro sistema lineal correctamente, se omitirán los detalles de cómo realizar este paso), digamos :

[matemáticas] y_j = \ sum_ {k = 1} ^ n c_k e ^ {ik x_j} [/ matemáticas]

De esta forma construimos el sistema de ecuaciones:

[matemáticas] y = F_n c [/ matemáticas]

donde c son los coeficientes en cuestión y, por lo tanto, usamos la matriz DFT para encontrar la función sinusoidal que genera las muestras.

Entonces la idea principal es:

1. Obtiene muestras de una función sinusoidal y (observe que necesita saber que es una función sinusoidal. Explotamos esta propiedad de manera crucial para obtener los coeficientes que la describen).
2. Luego construyes la matriz DFT [matemáticas] F_n [/ matemáticas] (como lo describe Hongwan, pero con la raíz de la unidad en lugar del conjugado. Su diferencia es muy pequeña, la que tiene las raíces de la unidad en realidad genera el tiempo original muestras de dominio, y el inverso (con conjugados), el que Hongwan tiene en su respuesta, te da los coeficientes).
3. Luego usa la matriz DFT para obtener los coeficientes de las series finitas de Fourier y, por lo tanto, f (x).

NOTA: ¿Cómo sabemos qué muestra [math] y_j [/ math] debe coincidir con cada fila del sistema de ecuaciones? Si recuerdo correctamente, si sabe a qué hora obtuvo la muestra, sabe qué ángulo x = x (t) en radianes usar para llenar su sistema de ecuaciones lineales. Por lo tanto, obtienes el sistema de ecuaciones que deseas y ahora puedes obtener los coeficientes. 🙂

---

Continuará, ejemplo explícito:

[matemáticas] V =
\ begin {bmatrix}
1 y 1 y 1 y 1 \\
1 & w & w ^ 2 & w ^ 3 \\
1 & w ^ 2 & w ^ 4 & w ^ 6 \\
1 & w ^ 3 & w ^ 6 & w ^ 9 \\
[/matemáticas]