<jupyter_start><jupyter_text>Lesson 2: Fourier Transform  Notations Let $A\in\mathbb{C}^{M\times N}$, then its **conjugate transpose** is $A^*$ and its **transpose** is $A^T$.<jupyter_code>import numpy as np
A = np.array([[1+1j,1,0]]);print(A.T);print(np.asmatrix(A).H)<jupyter_output>[[1.+1.j]
 [1.+0.j]
 [0.+0.j]]
[[1.-1.j]
 [1.-0.j]
 [0.-0.j]]<jupyter_text>1D Fourier Transform Let $F_n$ be the unitary $n\times n$ Fourier matrix as$$F_n=\frac{1}{\sqrt{n}}\begin{bmatrix}1&1&\cdots&1\\1&\omega&\cdots&\omega^{n-1}\\\cdots&\cdots&&\cdots\\1&\omega^{n-1}&\cdots&\omega^{(n-1)^2}\end{bmatrix},$$where $\omega=e^{-2\pi i/n}$.The discrete Fourier transform of $x\in\mathbb{C}^n$ is $F_nx$. Typically, the flop count of an $n\times n$ matrix multiplied by a vector is $O(n^2)$, but $F_nx$ can be computed in $O(n\log n)$ flops, which has a huge computational advantage. So this is also called the Fast Fourier transform. $F_n$ is unitary as $F_n^*F_n=F_nF_n^*=I_n$ where $I_n$ is the $n\times n$ identity matrix. **In Python, np.fft.fft(x) = $\sqrt{n}F_nx$, and np.fft.fft(x, norm='ortho') = $F_nx$**  2D Fourier Transform The 2D fourier transform on an $M\times N$ matrix is $F_2(X)=F_MXF_N^T$, and the inverse Fourier transform is $F_2^{-1}(u)=F_1^*(u)=F_m^*u(F_n^*)^T$.<jupyter_code>import matplotlib.pyplot as plt
%matplotlib inline
X = plt.imread('pepper.png')
X.shape
FX = np.fft.fft2(X)  # 2D fourier transform
# showing the original and its fourier transform (only magnitude) together
f = plt.figure(figsize = (10,10))
f.add_subplot(1,2,1)
plt.imshow(X, cmap = 'gray')
f.add_subplot(1,2,2)
plt.imshow(np.absolute(np.fft.fftshift(FX)), cmap = 'gray')
plt.show(block = True)<jupyter_output><empty_output><jupyter_text>Now we verify that $F_MXF_N^T$ also gives the 2D Fourier Transform. np.fft.fft(X,axis=0) is to apply 1D FFT to every column of X. This is $F_MX$.np.fft.fft(X) is to apply 1D FFT to every row of X. This is $XF_N^T$.<jupyter_code>FX2 = np.fft.fft(np.fft.fft(X,axis=0))
np.linalg.norm(FX-FX2)<jupyter_output><empty_output><jupyter_text>We can test on simplier matrices:<jupyter_code>np.fft.fft(np.fft.fft([[1,1,1,1],[1,1,1,1]],axis=0))
np.fft.fft2([[1,1,1,1],[1,1,1,1]])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1992786293958521, 'fraction_numerical': 0.032912533814247066, 'mean_word_length': 5.56508875739645, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '501375', 'license': 'MIT', 'n_tokens_mistral': 1005, 'n_tokens_neox': 961, 'n_words': 212, 'path': 'nb/L2Fourier.ipynb', 'repo_name': 'xuemeic/Image-Processing', 'size': '2218'}