Function dftmatrix

Synopse

Kernel matrix for the 1-D Discrete Fourier Transform DFT.

A = dftmatrix(N)
- A: Output image, square N x N, complex

N: Integer, number of points of the DFT



In [1]:

    
import numpy as np

def dftmatrix(N):
    x = np.arange(N).reshape(N,1)
    u = x
    Wn = np.exp(-1j*2*np.pi/N)
    A = (1./np.sqrt(N)) * (Wn ** u.dot(x.T))
    return A

Examples



In [1]:

    
testing = (__name__ == "__main__")

if testing:
    ! jupyter nbconvert --to python dftmatrix.ipynb
    import numpy as np
    import sys,os
    import matplotlib.image as mpimg
    ia898path = os.path.abspath('../../')
    if ia898path not in sys.path:
        sys.path.append(ia898path)
    import ia898.src as ia









    



[NbConvertApp] Converting notebook dftmatrix.ipynb to python
[NbConvertApp] Writing 2322 bytes to dftmatrix.py

Example 1



In [2]:

    
if testing:
    A = ia.dftmatrix(128)
    ia.adshow(ia.normalize(A.real),'A.real')
    ia.adshow(ia.normalize(A.imag),'A.imag')

Example 2



In [3]:

    
if testing:
    A = ia.dftmatrix(4)
    print('A=\n', A.round(1))
    print('A-A.T=\n', A - A.T)
    print((np.abs(np.linalg.inv(A)-np.conjugate(A))).max() < 10E-15)









    



A=
 [[ 0.5+0.j   0.5+0.j   0.5+0.j   0.5+0.j ]
 [ 0.5+0.j   0.0-0.5j -0.5-0.j  -0.0+0.5j]
 [ 0.5+0.j  -0.5-0.j   0.5+0.j  -0.5-0.j ]
 [ 0.5+0.j  -0.0+0.5j -0.5-0.j   0.0-0.5j]]
A-A.T=
 [[ 0.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j  0.+0.j]]
True

Example 3

Showing the product $\mathbf{x}\mathbf{u}^T$:



In [4]:

    
if testing:
    u = x = np.arange(10).reshape(10,1)
    print('u xT=\n', u.dot(x.T))









    



u xT=
 [[ 0  0  0  0  0  0  0  0  0  0]
 [ 0  1  2  3  4  5  6  7  8  9]
 [ 0  2  4  6  8 10 12 14 16 18]
 [ 0  3  6  9 12 15 18 21 24 27]
 [ 0  4  8 12 16 20 24 28 32 36]
 [ 0  5 10 15 20 25 30 35 40 45]
 [ 0  6 12 18 24 30 36 42 48 54]
 [ 0  7 14 21 28 35 42 49 56 63]
 [ 0  8 16 24 32 40 48 56 64 72]
 [ 0  9 18 27 36 45 54 63 72 81]]

Equation

$$ \begin{matrix} W_N &=& \exp{\frac{-j2\pi}{N}} \\ A_N &=& \frac{1}{\sqrt{N}} (W_N)^{\mathbf{u} \mathbf{x}^T} \\ \mathbf{u} &=& \mathbf{x} = [0, 1, 2, \ldots, N-1]^T \end{matrix} $$

$$ \begin{matrix} A_N &=& A_N^T \ \mbox{symmetric} \\ (A_N)^{-1} &=& (A_N)^*\ \mbox{column orthogonality, unitary matrix} \end{matrix} $$

References

http://en.wikipedia.org/wiki/DFT_matrix



In [6]:

    
if testing:    
    print('testing dftmatrix')
    print(repr(np.floor(0.5 + 10E4*ia.dftmatrix(4).real) / 10E4) == repr(np.array(
          [[ 0.5,  0.5,  0.5,  0.5],
           [ 0.5,  0. , -0.5,  0. ],
           [ 0.5, -0.5,  0.5, -0.5],
           [ 0.5,  0. , -0.5,  0. ]])))
    print(repr(np.floor(0.5 + 10E4*ia.dftmatrix(4).imag) / 10E4) == repr(np.array(
          [[ 0. ,  0. ,  0. ,  0. ],
           [ 0. , -0.5,  0. ,  0.5],
           [ 0. ,  0. ,  0. ,  0. ],
           [ 0. ,  0.5,  0. , -0.5]])))









    



testing dftmatrix
True
True



In [ ]: