Discrete Fourier Transform

DFT
Author

SEOYEON CHOI

Published

December 27, 2022

DFT

https://miruetoto.quarto.pub/yechan/posts/CGSP/2022-12-24-CGSP-Chap-8-3-DFT.html#fnref1

https://miruetoto.github.io/yechan/%EB%B2%A0%EC%9D%B4%EC%A7%80%EC%95%88/2019/11/24/(%EB%85%B8%ED%8A%B8)-%EB%B2%A0%EC%9D%B4%EC%A7%80%EC%95%88-%EC%B6%94%EB%A1%A0-%EB%B2%A0%EC%9D%B4%EC%A7%80%EC%95%88.html

import

import numpy as np

Forward operator A

A = np.array([[0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0]])
A
array([[0, 0, 0, 0, 1],
       [1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0]])
np.transpose(A)@A
array([[1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1]])

note: A is orthogonal matrix

s = np.array([[1],[22],[333],[4444],[55555]])
s
array([[    1],
       [   22],
       [  333],
       [ 4444],
       [55555]])
A@s
array([[55555],
       [    1],
       [   22],
       [  333],
       [ 4444]])
A@A@s
array([[ 4444],
       [55555],
       [    1],
       [   22],
       [  333]])
A@A@A@s
array([[  333],
       [ 4444],
       [55555],
       [    1],
       [   22]])

note : thus A is a forward operator,A* is a backward operator.

DFT

\(A = DFT^* \Lambda DFT\)

λ, ψ = np.linalg.eig(A)
λ, ψ
(array([-0.80901699+0.58778525j, -0.80901699-0.58778525j,
         0.30901699+0.95105652j,  0.30901699-0.95105652j,
         1.        +0.j        ]),
 array([[-0.3618034+0.26286556j, -0.3618034-0.26286556j,
         -0.3618034-0.26286556j, -0.3618034+0.26286556j,
          0.4472136+0.j        ],
        [ 0.4472136+0.j        ,  0.4472136-0.j        ,
         -0.3618034+0.26286556j, -0.3618034-0.26286556j,
          0.4472136+0.j        ],
        [-0.3618034-0.26286556j, -0.3618034+0.26286556j,
          0.1381966+0.4253254j ,  0.1381966-0.4253254j ,
          0.4472136+0.j        ],
        [ 0.1381966+0.4253254j ,  0.1381966-0.4253254j ,
          0.4472136+0.j        ,  0.4472136-0.j        ,
          0.4472136+0.j        ],
        [ 0.1381966-0.4253254j ,  0.1381966+0.4253254j ,
          0.1381966-0.4253254j ,  0.1381966+0.4253254j ,
          0.4472136+0.j        ]]))
λ.shape, ψ.shape
((5,), (5, 5))
A 
array([[0, 0, 0, 0, 1],
       [1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 1, 0]])
(ψ @ np.diag(λ) @ ψ.transpose()).round(2)
array([[-0.  +0.j,  0.45+0.j,  0.28+0.j,  0.72+0.j, -0.45+0.j],
       [ 0.45+0.j,  0.28+0.j,  0.72+0.j, -0.45+0.j, -0.  +0.j],
       [ 0.28+0.j,  0.72+0.j, -0.45+0.j,  0.  +0.j,  0.45+0.j],
       [ 0.72+0.j, -0.45+0.j,  0.  +0.j,  0.45+0.j,  0.28+0.j],
       [-0.45+0.j, -0.  +0.j,  0.45+0.j,  0.28+0.j,  0.72+0.j]])

?

define \(\psi^* = DFT\)

DFT = np.transpose(ψ)
DFT
array([[-0.3618034+0.26286556j,  0.4472136+0.j        ,
        -0.3618034-0.26286556j,  0.1381966+0.4253254j ,
         0.1381966-0.4253254j ],
       [-0.3618034-0.26286556j,  0.4472136-0.j        ,
        -0.3618034+0.26286556j,  0.1381966-0.4253254j ,
         0.1381966+0.4253254j ],
       [-0.3618034-0.26286556j, -0.3618034+0.26286556j,
         0.1381966+0.4253254j ,  0.4472136+0.j        ,
         0.1381966-0.4253254j ],
       [-0.3618034+0.26286556j, -0.3618034-0.26286556j,
         0.1381966-0.4253254j ,  0.4472136-0.j        ,
         0.1381966+0.4253254j ],
       [ 0.4472136+0.j        ,  0.4472136+0.j        ,
         0.4472136+0.j        ,  0.4472136+0.j        ,
         0.4472136+0.j        ]])
λ[3,]
(0.30901699437494734-0.9510565162951535j)
a=np.array([1,2,3,4])
np.diag(np.diag(a))
array([1, 2, 3, 4])
λ
array([-0.80901699+0.58778525j, -0.80901699-0.58778525j,
        0.30901699+0.95105652j,  0.30901699-0.95105652j,
        1.        +0.j        ])
(np.matrix(ψ)@np.matrix(np.diag(λ))@np.matrix(ψ).H).round(3)
matrix([[-0.+0.j,  0.+0.j, -0.+0.j,  0.+0.j,  1.+0.j],
        [ 1.+0.j, -0.+0.j,  0.+0.j, -0.+0.j, -0.+0.j],
        [-0.+0.j,  1.+0.j, -0.+0.j,  0.+0.j,  0.+0.j],
        [ 0.+0.j, -0.+0.j,  1.+0.j,  0.+0.j, -0.+0.j],
        [-0.+0.j, -0.+0.j,  0.+0.j,  1.+0.j, -0.+0.j]])
np.matrix(ψ).H
matrix([[-0.3618034-0.26286556j,  0.4472136-0.j        ,
         -0.3618034+0.26286556j,  0.1381966-0.4253254j ,
          0.1381966+0.4253254j ],
        [-0.3618034+0.26286556j,  0.4472136+0.j        ,
         -0.3618034-0.26286556j,  0.1381966+0.4253254j ,
          0.1381966-0.4253254j ],
        [-0.3618034+0.26286556j, -0.3618034-0.26286556j,
          0.1381966-0.4253254j ,  0.4472136-0.j        ,
          0.1381966+0.4253254j ],
        [-0.3618034-0.26286556j, -0.3618034+0.26286556j,
          0.1381966+0.4253254j ,  0.4472136+0.j        ,
          0.1381966-0.4253254j ],
        [ 0.4472136-0.j        ,  0.4472136-0.j        ,
          0.4472136-0.j        ,  0.4472136-0.j        ,
          0.4472136-0.j        ]])

Spectral components and Frequencies

\[\{ 1,\psi_1, \psi_2, \psi_3,\dots, \psi_{N-1} \}\]

These vectors are called spectral components.

In Physics and in operator theory, these eigenvalues are the frequencies of the signal.

Eigenvalues of \(A\)