https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
이번 강의에서는 다음 내용을 배운다.
Complex vectors, matrices 의 inner product , length
(Fast) Fourier Transform
우선 complex (복소수) vector 를 다뤄보자.
z = [ z 1 z 2 . . . z n ] , ( z i : complex number ) z=\begin{bmatrix} z_1 \\ z_2 \\ ... \\ z_n \end{bmatrix}, \ (\text{$z_i$ : complex number}) z = ⎣ ⎢ ⎢ ⎢ ⎡ z 1 z 2 . . . z n ⎦ ⎥ ⎥ ⎥ ⎤ , ( z i : complex number ) 위 벡터 complex vector z z z z T z z^Tz z T z
z 1 = [ 1 i ] z_1=\begin{bmatrix} 1 \\ i \end{bmatrix} z 1 = [ 1 i ] z 1 T z 1 = [ 1 i ] [ 1 i ] = 1 + i 2 = 0 z_1^Tz_1= \begin{bmatrix} 1 & i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 1 + i^2 =0 z 1 T z 1 = [ 1 i ] [ 1 i ] = 1 + i 2 = 0 길이는 0보다 커야 하는데 위와 같이 z T z z^Tz z T z z ˉ T z \bar z ^T z z ˉ T z
z ˉ 1 T z 1 = [ 1 − i ] [ 1 i ] = 1 − i 2 = 2 \bar z_1^Tz_1= \begin{bmatrix} 1 & -i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 1 - i^2 =2 z ˉ 1 T z 1 = [ 1 − i ] [ 1 i ] = 1 − i 2 = 2 그리고 z ˉ T \bar z^T z ˉ T z H z^H z H
따라서 다음과 같이 정리가 가능하다.
z H z = l e n g t h o f z z^Hz=length \ of \ z z H z = l e n g t h o f z y ˉ T = y H \bar y^T=y^H y ˉ T = y H 그렇다면 이를 Symmetric matrix 와 Perpendicular matrix 에도 적용해보자.
1. Symmetric matrix ( A T = A ) \text{1. Symmetric matrix ($A^T=A$)} 1. Symmetric matrix ( A T = A ) A T = A → A H = A A^T=A \to A^H=A A T = A → A H = A ex. [ 2 3 + i 3 − i 5 ] \text{ex. } \begin{bmatrix} 2 & 3+i \\ 3-i & 5 \\ \end{bmatrix} ex. [ 2 3 − i 3 + i 5 ] 2. Perpendicular matrix ( Q , q 1 , q 2 , . . . , q n ) \text{2. Perpendicular matrix ($Q$, $q_1,q_2,...,q_n$)} 2. Perpendicular matrix ( Q , q 1 , q 2 , ... , q n ) q i H q j = { 0 , if i ≠ j 1 , if i = j q_i^Hq_j = \begin{cases} 0, & \text{if } i \ne j \\ 1, & \text{if } i = j \end{cases} q i H q j = { 0 , 1 , if i = j if i = j Q = [ ∣ . . . ∣ q 1 . . . q n ∣ . . . ∣ ] Q= \begin{bmatrix} | & ... & | \\ q_1 & ... & q_n \\ | & ... & | \\ \end{bmatrix} Q = ⎣ ⎢ ⎡ ∣ q 1 ∣ . . . . . . . . . ∣ q n ∣ ⎦ ⎥ ⎤ 다음으로 Fourier matrix 에 대해서 알아보자.
Fourier matrix F n \text{Fourier matrix $F_n$} Fourier matrix F n F n = [ 1 1 1 . . . 1 1 w w 2 . . . w n − 1 1 w 2 w 4 . . . w 2 ( n − 1 ) . . . . . . . . . . . . . . . 1 w n − 1 w 2 ( n − 1 ) . . . w ( n − 1 ) 2 ] F_n=\begin{bmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & w & w^2 & ... & w^{n-1} \\ 1 & w^2 & w^4 & ... & w^{2(n-1)} \\ ... & ... & ... & ... & ... \\ 1 & w^{n-1} & w^{2(n-1)} & ... & w^{(n-1)^2} \\ \end{bmatrix} F n = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 1 1 . . . 1 1 w w 2 . . . w n − 1 1 w 2 w 4 . . . w 2 ( n − 1 ) . . . . . . . . . . . . . . . 1 w n − 1 w 2 ( n − 1 ) . . . w ( n − 1 ) 2 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ( F n ) i j = w i j ( i , j = 0 , 1 , . . . , n − 1 ) (F_n)_{ij}=w^{ij} \ (i,j=0,1,...,n-1) ( F n ) i j = w i j ( i , j = 0 , 1 , . . . , n − 1 ) w = e 2 π × i n = cos 2 π n + i × sin 2 π n w=e^{\frac{2\pi \times i}{n}} = \cos \frac{2 \pi}{n}+i\times\sin \frac{2\pi}{n} w = e n 2 π × i = cos n 2 π + i × sin n 2 π 그리고 위 w w w
그렇다면 만약 n = 4 n=4 n = 4
F 4 = [ 1 1 1 1 1 i i 2 i 3 1 i 2 i 4 i 6 1 i 3 i 6 i 9 ] = [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] F_4=\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & i^2 & i^3 \\ 1 & i^2 & i^4 & i^6 \\ 1 & i^3 & i^6 & i^9 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{bmatrix} F 4 = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 i i 2 i 3 1 i 2 i 4 i 6 1 i 3 i 6 i 9 ⎦ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ⎦ ⎥ ⎥ ⎥ ⎤ w 4 = 1 , w = e 2 π × i 4 w^4=1, w=e^{\frac{2\pi\times i}{4}} w 4 = 1 , w = e 4 2 π × i
즉, F 4 = [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] F_4=\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{bmatrix} F 4 = ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ⎦ ⎥ ⎥ ⎥ ⎤
ex. c o l 2 H c o l 4 = 1 + i 2 + 1 + i 2 = 0 \text{ex. } col_2^Hcol_4=1+i^2+1+i^2=0 ex. c o l 2 H c o l 4 = 1 + i 2 + 1 + i 2 = 0 그리고 모든 벡터의 길이가 2인 것을 알 수 있으며, 다음과 같이 표기가 가능하다.
F 4 = 1 2 [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] ⏟ orthonomal F_4=\frac{1}{2}\underbrace{\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{bmatrix}}_{\text{orthonomal}} F 4 = 2 1 orthonomal ⎣ ⎢ ⎢ ⎢ ⎡ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ⎦ ⎥ ⎥ ⎥ ⎤ F 4 H F 4 = I F_4^HF_4=I F 4 H F 4 = I 이제 Fast Fourier Transform 에 대해서 알아보자.F n F_n F n n 2 n^2 n 2 n 2 log n \frac{n}{2}\log n 2 n log n
w n = e 2 π × i n w_n=e^{\frac{2\pi \times i}{n}} w n = e n 2 π × i ( w n ) 2 = e 2 π × i × 2 n = e 2 π × i n 2 = w n 2 (w_n)^2=e^{\frac{2\pi \times i\times 2}{n}}=e^{\frac{2\pi \times i}{\frac{n}{2}}} = w_{\frac{n}{2}} ( w n ) 2 = e n 2 π × i × 2 = e 2 n 2 π × i = w 2 n [ F 64 ] = [ I D 32 I − D 32 ] [ F 32 0 0 F 32 ] [ 1 . . . . . . . . . 1 . . . . . . . . . 1 1 . . . . . . . . . 1 . . . . . . . . . 1 ] ⏟ Permutations P \begin{bmatrix} F_{64} \end{bmatrix} = \begin{bmatrix} I & D_{32} \\ I & -D_{32} \\ \end{bmatrix} \begin{bmatrix} F_{32} & 0 \\ 0 & F_{32} \\ \end{bmatrix} \underbrace{ \begin{bmatrix} 1 & ... & ...\\ ... & 1 & ...\\ ... & ... & 1\\ 1 & ... & ...\\ ... & 1 & ...\\ ... & ... & 1 \\ \end{bmatrix}}_{\text{Permutations P}} [ F 6 4 ] = [ I I D 3 2 − D 3 2 ] [ F 3 2 0 0 F 3 2 ] Permutations P ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 . . . . . . 1 . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . . . . . 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ D 32 = [ 1 . . . . . . . . . . . . . . . w 1 . . . . . . . . . . . . . . . w 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . w 31 ] D_{32}=\begin{bmatrix} 1 & ... & ... & ... & ...\\ ... & w^1 & ... & ... & ...\\ ... & ... & w^2 & ... & ...\\ ... & ... & ... & ... & ...\\ ... & ... & ... & ... & w^{31}\\ \end{bmatrix} D 3 2 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 . . . . . . . . . . . . . . . w 1 . . . . . . . . . . . . . . . w 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . w 3 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ 따라서 다음과 같이 해석이 가능하다.
F 64 F_{64} F 6 4 6 4 2 64^2 6 4 2 F 32 F_{32} F 3 2 3 2 2 32^2 3 2 2 D 32 D_{32} D 3 2 32 32 3 2 따라서 6 4 2 → 2 ( 3 2 2 ) + 32 64^2\to 2(32^2)+32 6 4 2 → 2 ( 3 2 2 ) + 3 2
따라서 계속 이어서 연산을 진행하면,
F 64 → F 32 → F 16 → . . . → F 1 F_{64}\to F_{32} \to F_{16} \to ... \to F_1 F 6 4 → F 3 2 → F 1 6 → . . . → F 1 와 같고,
6 4 2 → 2 ( 3 2 2 ) + 32 → 2 [ ( 16 ) 2 + 16 ] + 32 → . . . → 6 × 32 = log 64 × 64 2 64^2\to2(32^2)+32\to2[(16)^2+16]+32\to...\to6\times32=\log 64 \times \frac{64}{2} 6 4 2 → 2 ( 3 2 2 ) + 3 2 → 2 [ ( 1 6 ) 2 + 1 6 ] + 3 2 → . . . → 6 × 3 2 = log 6 4 × 2 6 4 따라서 Fast Fourier Transform 을 통해,F n F_n F n n 2 → log n × n 2 n^2\to \log n \times \frac{n}{2} n 2 → log n × 2 n
