¿Cuál es la mejor manera de comprender intuitivamente la rápida transformación de Fourier de un grupo (simétrico)?

Daré una respuesta parcial a su pregunta.

En primer lugar, comprendamos qué es la transformación de Fourier en grupos. Un buen lugar para comenzar es la transformada discreta de Fourier,
[matemáticas] \ displaystyle {X [k] = \ sum_ {n = 0} ^ {N-1} x_n e ^ {- j2 \ pi nk / N}, k = 0 .. (N-1)} [/ matemáticas]
y transformada discreta inversa de Fourier
[matemáticas] \ displaystyle {x_n = \ frac {1} {N} \ sum_ {k = 0} ^ {N-1} X [k] e ^ {j2 \ pi nk / N}, n = 0 .. ( N-1)} [/ matemáticas]
Podemos representar la transformada discreta de Fourier como matriz [matemática] F_N (k, m) = e ^ {- j2 \ pi km / N} [/ matemática].

El grupo significa índice [matemática] 0 .. (N-1) [/ matemática], que es un grupo cíclico en tal caso. Es decir, estamos trabajando en un grupo cíclico en un ciclo unitario en un plano complejo para una transformada discreta de Fourier. Para algunos [matemática] N [/ matemática] especiales, como [matemática] N = p ^ m [/ matemática] donde [matemática] p [/ matemática] es primo, hay muchos algoritmos rápidos de transformación de Fourier que puede encontrar, que son básicamente explorar la simétrica de dicho grupo cíclico en el ciclo unitario en el plano complejo (o explorar la ley distributiva recursiva).

Si extiende el índice a [matemática] [0, N) [/ matemática], que también es un grupo cíclico, tendrá series de Fourier (inversas).

Para obtener la transformación de Fourier [matemáticas] \ displaystyle {X (w) = \ int _ {- \ infty} ^ {\ infty} x (t) e ^ {- j2 \ pi wt} dt} [/ math], extienda índice en el círculo unitario del plano complejo a la línea real. Todos estos pertenecen a transformaciones de Fourier más clásicas.

Para la transformación general de Fourier en grupos, 1. el grupo no tiene que ser un grupo cíclico simple o real, puede ser un grupo finito abeliano o no abelien. 2. el grupo no tiene que sentarse en un círculo complejo de unidades.

El grupo abeliano finito más simple que no sea la transformada discreta de Fourier es la transformada de Walsh-Hadamard, que se puede entender como la transformada de Fourier en [matemáticas] Z_2 ^ n [/ matemáticas], aquí están [matemáticas] H_2 [/ matemáticas] y [matemáticas] H_4 [/ matemáticas],
[matemáticas]
H_ {2} = F_2 = \ begin {bmatrix}
1 y 1 \\\\
1 y -1 \\\\
\ end {bmatrix}
[/matemáticas]
[matemáticas]
H_ {4} = F_2 \ bigotimes F_2 = \ begin {bmatrix}
H_ {2} y H_ {2} \\\\
H_ {2} y -H_ {2} \\\\
\ end {bmatrix}
= \ begin {bmatrix}
1 y 1 y 1 y 1 \\\\
1 y -1 y 1 y -1 \\\\
1 y 1 y – 1 y -1 \\\\
1 y -1 y -1 y 1 \\\\
\ end {bmatrix}
[/matemáticas].

De manera similar, puede construir la transformada de Fourier en [matemáticas] Z_2 \ bigotimes Z_3 [/ matemáticas] como [matemáticas] F_2 \ bigotimes F_3 [/ matemáticas]

[matemáticas] \ begin {bmatrix}
1 y 1 y 1 y 1 y 1 y 1 \\\\
1 y -1 y 1 y -1 y 1 y -1 \\\\
1 y 1 y e ^ {j2 \ pi / 3} y e ^ {j2 \ pi / 3} y e ^ {j4 \ pi / 3} y e ^ {j4 \ pi / 3} \\\\
1 y -1 y e ^ {j2 \ pi / 3} y -e ^ {j2 \ pi / 3} y e ^ {j4 \ pi / 3} y -e ^ {j4 \ pi / 3} \\\\
1 y 1 y e ^ {j4 \ pi / 3} y e ^ {j4 \ pi / 3} y e ^ {j2 \ pi / 3} y e ^ {j2 \ pi / 3} \\\\
1 y -1 y e ^ {j4 \ pi / 3} y -e ^ {j4 \ pi / 3} y e ^ {j2 \ pi / 3} y -e ^ {j2 \ pi / 3} \\\\
\ end {bmatrix}
[/matemáticas].

Las transformadas de Fourier en un grupo no abeliano no se analizan aquí.

No necesariamente para grupos simétricos, pero esta es una de mis formas interactivas e intuitivas favoritas de entender FFT.

Una guía interactiva de la transformada de Fourier

Visualizando la transformada discreta de Fourier

Fftvisualize2 por urtubia / HasCanvas