선형대수 note 26: Complex matrices; fast fourier transform

복소벡터 (Complex Vector)

실 (Real) 벡터의 길이는 \mathbf{v}^T \mathbf{v} 로 구할 수 있다.

    \[\begin{aligned} \mathbf{v}^T \mathbf{v} &= v_1 v_1 + v_2 v_2 + \dots + v_n v_n \\ &= ||v_1||^2 + ||v_2||^2 + \dots + ||v_n||^2 \end{aligned}\]

실수끼리의 곱의 합이므로 dot product 이라고도 부른다. 하지만 복소수로 이루어진 벡터의 길이는 transpose 해서 곱하는 것 만으로 충분하지 않다. 예를 들어 다음과 같은 복소벡터가 있다고 하자.

    \[\mathbf{z} =  \begin{bmatrix} 1 \\ i \end{bmatrix}\]

transpose 해서 자기 자신을 곱하면,

    \[\mathbf{z}^T\mathbf{z} = \begin{bmatrix} 1 & i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 0\]

\begin{bmatrix} 1 \\ i \end{bmatrix} 길이가 0 은 아닐 것이다. 복소벡터 자기 자신의 올바른 내적 (inner product) 은 다음과 같다.

    \[\begin{aligned} \overbar{\mathbf{z}}^T \mathbf{z} &= \overbar{z_1}z_1 + \overbar{z_2}z_2 + \dots + \overbar{z_n}z_n \\ &= ||z_1||^2 + ||z_2||^2 + \dots + ||z_n||^2 \end{aligned}\]

여기서 \overbar{\mathbf{z}}^T \mathbf{z} 를 간단히 \mathbf{z}^H \mathbf{z} 라고 쓰고 H 는 Hermit 의 이름을 따서 Hermitian 이라고 부른다. 즉 Hermitian 은 행렬이나 벡터에 complex conjugate 와 transpose 를 적용한 것을 말한다. \mathbf{z} 의 길이의 제곱을 제대로 구하면,

    \[\mathbf{z}^H\mathbf{z} = \begin{bmatrix} 1 & -i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 2\]

실벡터의 내적은 교환법칙이 성립하지만 복소벡터의 내적은 곱하는 방향에 따라 conjugate 관계에 있다.

    \[\mathbf{v}^H \mathbf{w} = \overbar{\mathbf{w}^H \mathbf{v}}\]

복소행렬 (Complex Matrix)

에르미트 행렬 (Hermitian Matrix)

복소벡터 공간에서의 에르미트 (Hermitian) 행렬 ZZ^H = Z 이 성립한다. 정의에 의해 에르미트 행렬의 대각 성분은 실수로 이루어져 있다. 에르미트 행렬의 성분이 모두 실수라면 Z 는 대칭행렬이다. 즉, 에르미트 행렬은 실수 대칭행렬을 포함한다.
실벡터 공간의 대칭행렬과 마찬가지로 에르미트 행렬의 고유값도 실수이고, 고유벡터들도 서로 직교한다.

유니타리 행렬 (Unitary Matrix)

실벡터 공간에서 직교 행렬 (Orthogonal Matrix) QQ^T Q = I 이었다. 복소벡터 공간에서 Q^H Q = I 가 성립하는 행렬을 유니타리 행렬 (Unitary Matrix) 이라고 부른다. 유니타리 행렬은 각 열들이 복소공간에서 서로 직교하고 길이가 1 인 정방행렬을 말한다.

이산 푸리에 변환 (Discrete Fourier Transform)

이산 푸리에 변환 행렬은 복소수로 이루어진 유니타리 행렬이자 대칭행렬이다.

    \[F_n = \frac{1}{\sqrt{n}} \begin{bmatrix} W_n^{0} & W_n^{0} & W_n^{0} & \dots & W_n^{0} \\ W_n^{0} & W_n^{1} & W_n^{2} & \dots & W_n^{1(n-1)} \\ W_n^{0} & W_n^{2} & W_n^{4} & \ddots & W_n^{2(n-1)} \\ \vdots & \vdots & \vdots & & \vdots \\ W_n^{0} & W_n^{(n-1)1} & W_n^{(n-1)2} & \dots & W_n^{(n-1)(n-1)}  \end{bmatrix}\]

F_n 의 성분은 (F_n)_{ij} = W_n^{ij} 이고1, W_n = e^{-\frac{2\pi i}{n}} 이다.

W_n 는 복소평면의 반지름이 1 인 단위원의 \frac{1}{n} 조각을 말한다. W_n 를 제곱할 수록 복소평면을 회전하게 되어 W_n^0 = W_n^n = 1 이 된다.
W_n^k 의 길이는 1 이다. 그러므로 열벡터들은 길이가 \sqrt{n} 이다. 앞의 상수로 나누어져 열벡터들은 길이가 1 이고, 각각의 열들은 서로 직교하는 기저를 나타내기 때문에 F_n 은 유니타리 행렬이다. 유니타리 행렬이므로 F_n^{-1} = F_n^H 이다. 대칭행렬이므로 F_n^HF_n 에서 각 성분 W_n^kk 의 부호만 바뀐 행렬이 된다.

FFT (Fast Fourier Transform)

이산 푸리에 변환 행렬 F_nn^2 번의 곱셈이 필요하지만 FFT 를 이용해서 \frac{n}{2} \log_2 n 번의 곱셈으로 획기적으로 줄일 수 있다.
F_n 의 성분인 W_n 은 회전 연산자라고도 불리는데 주기성 (Periodicity property) 과 대칭성 (Symmetry property) 이라는 두가지 성질이 있다.

  • 주기성 W_n^k = W_n^{k+n}
  • 대칭성 W_n^k = -W_n^{k+\frac{n}{2}}

즉, 복소평면의 단위원을 한 바퀴를 돌면 값이 변하지 않고 반 바퀴를 돌면 음수가 되는 것이다. 그림을 떠올려 보면 쉽게 이해가 갈 것이다.

푸리에 변환 행렬 F_4 를 써보면

    \[\begin{aligned} F_4 P_4^T &= \begin{bmatrix} W_4^{0} & W_4^{0} & W_4^{0} & W_4^{0} \\ W_4^{0} & W_4^{1} & W_4^{2} & W_4^{3} \\ W_4^{0} & W_4^{2} & W_4^{4} & W_4^{6} \\ W_4^{0} & W_4^{3} & W_4^{6} & W_4^{9} \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} W_4^{0} & W_4^{0} & W_4^{0} & W_4^{0} \\ W_4^{0} & W_4^{2} & W_4^{1} & W_4^{3} \\ W_4^{0} & W_4^{4} & W_4^{2} & W_4^{6} \\ W_4^{0} & W_4^{6} & W_4^{3} & W_4^{9} \\ \end{bmatrix} \\ &= \begin{bmatrix} W_2^{0} & W_2^{0} & W_4^{0}W_2^{0} & W_4^{0}W_2^{0} \\ W_2^{0} & W_2^{1} & W_4^{1}W_2^{0} & W_4^{1}W_2^{1} \\ W_2^{0} & W_2^{2} & W_4^{0}W_2^{1} & W_4^{0}W_2^{3} \\ W_2^{0} & W_2^{3} & W_4^{1}W_2^{1} & W_4^{1}W_2^{4} \\ \end{bmatrix} =  \begin{bmatrix} W_2^{0} & W_2^{0} & W_4^{0}W_2^{0} & W_4^{0}W_2^{0} \\ W_2^{0} & W_2^{1} & W_4^{1}W_2^{0} & W_4^{1}W_2^{1} \\ W_2^{0} & W_2^{0} & -W_4^{0}W_2^{0} & -W_4^{0}W_2^{0} \\ W_2^{0} & W_2^{1} & -W_4^{1}W_2^{0} & -W_4^{1}W_2^{1} \\ \end{bmatrix} \\ &= \begin{bmatrix} F_2 & D_2 F_2 \\ F_2 & -D_2 F_2 \\ \end{bmatrix} =  \begin{bmatrix} I_2 & D_2 \\ I_2 & -D_2 \\ \end{bmatrix} \begin{bmatrix} F_2 & 0 \\ 0 & F_2 \\ \end{bmatrix} \end{aligned}\]

    \[F_4 = \begin{bmatrix} I_2 & D_2 \\ I_2 & -D_2 \\ \end{bmatrix} \begin{bmatrix} F_2 & 0 \\ 0 & F_2 \\ \end{bmatrix} P_4\]

여기서 D 는 대각행렬이고, P\mathbf{x} 에서 P\mathbf{x} 의 짝수 성분을 먼저 오게하고 홀수 성분을 나중에 오도록 섞어주는 치환행렬 (Permutation Matrix) 이다.

    \[D_{n} =  \begin{bmatrix} W_{2n}^0 & & & & \\ & W_{2n}^1 & & & \\ & & W_{2n}^2 & & \\ & & & \ddots & \\ & & & & W_{2n}^{n-1} \end{bmatrix},\quad P_n = \begin{bmatrix} 1 & 0 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 0 & \dots & 0 & 0 \\ & & & \vdots & \\ 0 & 0 & 0 & 0 & \dots & 1 & 0 \\ 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 & 0 \\ & & & \vdots & \\ 0 & 0 & 0 & 0 & \dots & 0 & 1  \end{bmatrix}\]

같은 방식으로 F_2 를 쪼개면,

    \[\begin{aligned} F_4 &= \begin{bmatrix} I_2 & D_2 \\ I_2 & -D_2 \\ \end{bmatrix} \begin{bmatrix} F_2 & 0 \\ 0 & F_2 \\ \end{bmatrix} P_4 \\ &= \begin{bmatrix} I_2 & D_2 \\ I_2 & -D_2 \\ \end{bmatrix} \begin{bmatrix}  \begin{bmatrix}   I_1 & D_1 \\    I_1 & -D_1   \end{bmatrix}   \begin{bmatrix}   F_1 & 0 \\   0 & F_1   \end{bmatrix} P2 & 0 \\   0 & \begin{bmatrix}   I_1 & D_1 \\   I_1 & -D_1   \end{bmatrix}    \begin{bmatrix}   F_1 & 0 \\   0 & F_1   \end{bmatrix} P2 \end{bmatrix}  P_4 \\ &= \begin{bmatrix} I_2 & D_2 \\ I_2 & -D_2 \\ \end{bmatrix} \begin{bmatrix}    \begin{bmatrix}   I_1 & D_1 \\    I_1 & -D_1   \end{bmatrix} & 0 \\   0 & \begin{bmatrix}   I_1 & D_1 \\   I_1 & -D_1   \end{bmatrix}  \end{bmatrix} \begin{bmatrix}   \begin{bmatrix}   F_1 & 0 \\   0 & F_1   \end{bmatrix} & 0 \\   0 & \begin{bmatrix}   F_1 & 0 \\   0 & F_1   \end{bmatrix}   \end{bmatrix}  \begin{bmatrix} P_2 & 0 \\ 0 & P_2 \end{bmatrix} P_4 \end{aligned}\]

이렇게 재귀적으로 쪼개면 행렬 F_1 = 1 이 되어 F_n 부분은 단위행렬이 되고, 앞부분의 대각행렬과의 곱셈만 남는다. 대각행렬과의 곱셈은 \frac{n}{2} + 2\frac{n}{4} + 4\frac{n}{8} + \dots = \frac{n}{2} \log_2 n 번 필요하게 된다. n = 1024 라면 1024^2 = 1048576 번의 곱셈이 \frac{1024}{2} \log_2 1024 = 5120 번의 곱셈으로 줄어들어 연산량에서 약 200배 차이가 난다.


선형대수 note 목록

  1. i, j0 부터 n-1 까지의 범위이다.

Leave a Reply

Your email address will not be published. Required fields are marked *