Matriz DFT

En matemáticas aplicadas, una matriz DFT es una matriz cuadrada como expresión de una transformada discreta de Fourier (DFT) como una matriz de transformación , que se puede aplicar a una señal a través de la multiplicación de matrices .

Definición

Una DFT de N puntos se expresa como la multiplicación $X=Wx$ , dónde $x$ es la señal de entrada original, $W$ es la matriz DFT cuadrada de N por N , y $X$ es la DFT de la señal. La matriz cuadrada garantiza que la transformación sea invertible.

La matriz de transformación $W$ puede definirse como $W=\left({\frac {\omega ^{jk}}{\sqrt {N}}}\right)_{j,k=0,\ldots ,N-1}$ , o equivalentemente:

W={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}

,

dónde $\omega =e^{-2\pi i/N}$ es una raíz N primitiva de la unidad en la que $i^{2}=-1$ Podemos evitar escribir exponentes grandes para $\omega$ utilizando el hecho de que para cualquier exponente $x$ tenemos la identidad $\omega ^{x}=\omega ^{x{\bmod {N}}}.$ Esta es la matriz de Vandermonde para las raíces de la unidad, hasta el factor de normalización. Nótese que el factor de normalización delante de la suma ( $1/{\sqrt {N}}$ ) y el signo del exponente en ω son meras convenciones y difieren en algunos tratamientos. Toda la discusión siguiente se aplica independientemente de la convención, con ajustes mínimos como máximo. Lo único importante es que las transformadas directa e inversa tengan exponentes de signo opuesto y que el producto de sus factores de normalización sea 1/ N . Sin embargo, la $1/{\sqrt {N}}$ La elección en este caso hace que la matriz DFT resultante sea unitaria , lo cual resulta conveniente en muchas circunstancias.

Los algoritmos de transformada rápida de Fourier utilizan las simetrías de la matriz para reducir el tiempo de multiplicación de un vector por esta matriz, en comparación con el tiempo habitual. $O(N^{2})$ Se pueden aplicar técnicas similares para multiplicaciones por matrices como la matriz de Hadamard y la matriz de Walsh .

Ejemplos

Dos puntos

La DFT de dos puntos es un caso sencillo, en el que la primera entrada es la CC (suma) y la segunda entrada es la CA (diferencia).

W={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}

La primera fila realiza la suma y la segunda fila realiza la diferencia.

El factor de $1/{\sqrt {2}}$ es hacer que la transformación sea unitaria (ver más abajo).

Cuatro puntos

La matriz DFT de cuatro puntos en sentido horario es la siguiente:

W={\frac {1}{\sqrt {4}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}\\\end{bmatrix}}={\frac {1}{\sqrt {4}}}{\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\end{bmatrix}}

dónde $\omega =e^{-{\frac {2\pi i}{4}}}=-i$ .

Ocho puntos

El primer caso no trivial de potencia entera de dos es para ocho puntos:

W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\\omega ^{0}&\omega ^{4}&\omega ^{8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\\omega ^{0}&\omega ^{5}&\omega ^{10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\\omega ^{0}&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\\omega ^{0}&\omega ^{7}&\omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\\\end{bmatrix}}={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &-i&-i\omega &-1&-\omega &i&i\omega \\1&-i&-1&i&1&-i&-1&i\\1&-i\omega &i&\omega &-1&i\omega &-i&-\omega \\1&-1&1&-1&1&-1&1&-1\\1&-\omega &-i&i\omega &-1&\omega &i&-i\omega \\1&i&-1&-i&1&i&-1&-i\\1&i\omega &i&-\omega &-1&-i\omega &-i&\omega \\\end{bmatrix}}

dónde

\omega =e^{-{\frac {2\pi i}{8}}}={\frac {1}{\sqrt {2}}}-{\frac {i}{\sqrt {2}}}

(Tenga en cuenta que $\omega ^{8+n}=\omega ^{n}$ .)

Evaluar el valor de $\omega$ , da:

$W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&{\frac {1-i}{\sqrt {2}}}&-i&{\frac {-1-i}{\sqrt {2}}}&-1&{\frac {-1+i}{\sqrt {2}}}&i&{\frac {1+i}{\sqrt {2}}}\\1&-i&-1&i&1&-i&-1&i\\1&{\frac {-1-i}{\sqrt {2}}}&i&{\frac {1-i}{\sqrt {2}}}&-1&{\frac {1+i}{\sqrt {2}}}&-i&{\frac {-1+i}{\sqrt {2}}}\\1&-1&1&-1&1&-1&1&-1\\1&{\frac {-1+i}{\sqrt {2}}}&-i&{\frac {1+i}{\sqrt {2}}}&-1&{\frac {1-i}{\sqrt {2}}}&i&{\frac {-1-i}{\sqrt {2}}}\\1&i&-1&-i&1&i&-1&-i\\1&{\frac {1+i}{\sqrt {2}}}&i&{\frac {-1+i}{\sqrt {2}}}&-1&{\frac {-1-i}{\sqrt {2}}}&-i&{\frac {1-i}{\sqrt {2}}}\\\end{bmatrix}}$

La siguiente imagen representa la DFT como una multiplicación de matrices, donde los elementos de la matriz están representados por ejemplos de exponenciales complejas:

La parte real (onda coseno) se representa con una línea continua, y la parte imaginaria (onda sinusoidal) con una línea discontinua.

La fila superior está compuesta enteramente por unos (escalada por $1/{\sqrt {8}}$ para la unitariedad), por lo que "mide" el componente de CC en la señal de entrada. La siguiente fila son ocho muestras de menos un ciclo de una exponencial compleja, es decir, una señal con una frecuencia fraccionaria de −1/8, por lo que "mide" cuánta "intensidad" hay en la frecuencia fraccionaria +1/8 en la señal. Recordemos que un filtro adaptado compara la señal con una versión invertida en el tiempo de lo que estamos buscando, por lo que cuando buscamos la frecuencia fraccionaria 1/8 la comparamos con la frecuencia fraccionaria −1/8, por eso esta fila es una frecuencia negativa . La siguiente fila son menos dos ciclos de una exponencial compleja, muestreados en ocho lugares, por lo que tiene una frecuencia fraccionaria de −1/4, y por lo tanto "mide" el grado en que la señal tiene una frecuencia fraccionaria de +1/4.

A continuación se resume cómo funciona la DFT de 8 puntos, fila por fila, en términos de frecuencia fraccionaria:

0 mide la cantidad de CC presente en la señal.
−1/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +1/8.
−1/4 mide qué parte de la señal tiene una frecuencia fraccionaria de +1/4.
−3/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +3/8.
−1/2 mide qué parte de la señal tiene una frecuencia fraccionaria de +1/2.
−5/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +5/8.
−3/4 mide qué parte de la señal tiene una frecuencia fraccionaria de +3/4.
−7/8 mide qué parte de la señal tiene una frecuencia fraccionaria de +7/8.

De forma equivalente, se puede decir que la última fila tiene una frecuencia fraccionaria de +1/8 y, por lo tanto, mide qué parte de la señal tiene una frecuencia fraccionaria de −1/8. De esta manera, se podría decir que las filas superiores de la matriz "miden" el contenido de frecuencia positiva en la señal y las filas inferiores miden el componente de frecuencia negativa en la señal.

Transformación unitaria

La DFT es (o puede ser, mediante una selección adecuada de escalado) una transformación unitaria, es decir, una que conserva la energía. La elección adecuada de escalado para lograr la unitariedad es $1/{\sqrt {N}}$ De modo que la energía en el dominio físico sea igual a la energía en el dominio de Fourier, es decir, que se cumpla el teorema de Parseval . (También se suelen utilizar otras escalas no unitarias por conveniencia computacional; por ejemplo, el teorema de convolución adquiere una forma ligeramente más simple con la escala mostrada en el artículo sobre la transformada discreta de Fourier ).

Otras propiedades

Para conocer otras propiedades de la matriz DFT, incluidos sus valores propios, su relación con las convoluciones, sus aplicaciones, etc., consulte el artículo sobre la transformada discreta de Fourier .

Un caso límite: El operador de Fourier

Parte real (coseno)

Parte imaginaria (seno)

El operador de Fourier

La noción de transformada de Fourier se generaliza fácilmente . Una generalización formal de la DFT de N puntos se puede imaginar tomando N arbitrariamente grande. En el límite, la maquinaria matemática rigurosa trata a estos operadores lineales como transformadas integrales . En este caso, si creamos una matriz muy grande con exponenciales complejas en las filas (es decir, partes reales de coseno y partes imaginarias de seno) y aumentamos la resolución indefinidamente, nos aproximamos al núcleo de la ecuación integral de Fredholm de segundo tipo, es decir, el operador de Fourier que define la transformada de Fourier continua. Una porción rectangular de este operador de Fourier continuo se puede mostrar como una imagen, análoga a la matriz DFT, como se muestra a la derecha, donde el valor del píxel en escala de grises denota una cantidad numérica.

Véase también

Transformación multidimensional
Matrices de reloj y de desplazamiento
Teorema de Chebotarev sobre las raíces de la unidad

Referencias

Yip, PC; Rao, K. Ramamohan, eds. (2001). "2. La transformada discreta de Fourier" . Manual de transformada y compresión de datos . CRC Press. doi : 10.1201/9781315220529 . ISBN 978-1-315-22052-9.– Un tratamiento de la DFT basado en gran medida en la matriz de la DFT.