Discrete Fourier Transform

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 = D F T^{*} Λ D F T$

λ, ψ = 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))

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 $ψ^{*} = D F T$

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, ψ_{1}, ψ_{2}, ψ_{3}, \dots, ψ_{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$