연결 강의: MIT 18.06 Linear Algebra - Lecture 26: Complex Matrices; Fast Fourier Transform

1. 이번 강의의 위치

이번 강의는 positive definite matrix로 들어가기 직전에 복소수 행렬을 정리하는 연결 강의이다.

실수 행렬만 다룰 때는 전치, 내적, 직교, 대칭행렬을 비교적 단순하게 다룰 수 있었다. 그런데 실수 행렬이라도 고유값이 복소수로 나올 수 있다. 대표적으로 회전행렬은 실수 행렬이지만 복소수 고유값을 가진다.

그래서 복소수 벡터와 복소수 행렬에서는 다음 질문을 다시 정리해야 한다.

1. 복소수 벡터의 길이는 어떻게 정의하는가?
2. 복소수 벡터의 내적은 어떻게 계산하는가?
3. 대칭행렬에 해당하는 복소수 행렬은 무엇인가?
4. orthogonal matrix에 해당하는 복소수 행렬은 무엇인가?
5. Fourier matrix와 FFT는 왜 중요한가?

이 강의의 핵심은 “복소수에서는 전치할 때 켤레도 함께 취해야 한다”는 점이다.

---

2. 복소수 벡터의 길이

복소수 벡터를 다음처럼 두자.

$$z= \begin{bmatrix} z_1 \\ z_2 \\ \vdots \\ z_n \end{bmatrix} \in \mathbb{C}^n$$

실수 벡터에서는 길이의 제곱을 다음처럼 계산했다.

$$x^T x$$

하지만 복소수 벡터에서는 $z^Tz$가 길이의 제곱으로 적절하지 않다.

예를 들어,

$$z= \begin{bmatrix} 1 \\ i \end{bmatrix}$$

라고 하자.

그냥 전치만 사용하면,

$$z^Tz = \begin{bmatrix} 1 & i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 1+i^2 = 0$$

이 되어 버린다.

하지만 $[1 \ i]^T$는 0벡터가 아니다. 길이가 0이 되면 안 된다.

복소수에서는 각 성분을 자기 자신의 켤레와 곱해야 양수인 크기가 나온다.

$$\bar{z}_j z_j=|z_j|^2$$

따라서 복소수 벡터의 길이 제곱은 다음처럼 정의한다.

$$\bar{z}^T z = \bar{z}_1z_1+\bar{z}_2z_2+\cdots+\bar{z}_nz_n$$

이를 더 자주 쓰는 표기로는 다음처럼 쓴다.

$$z^H z$$

여기서 $H$는 Hermitian transpose를 뜻한다.

즉,

$$z^H=\bar{z}^T$$

이다.

복소수에서는 transpose와 conjugate를 함께 적용한 것이 기본이다.

---

3. 예시: $z=[1 \ i]^T$의 길이

다시 다음 벡터를 보자.

$$z= \begin{bmatrix} 1 \\ i \end{bmatrix}$$

Hermitian transpose는 다음이다.

$$z^H= \begin{bmatrix} 1 & -i \end{bmatrix}$$

따라서,

$$z^Hz = \begin{bmatrix} 1 & -i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 1+(-i)i = 1+1 = 2$$

이다.

그러므로 길이는 다음이다.

$$\|z\|=\sqrt{2}$$

이제 0이 아닌 벡터가 양의 길이를 갖게 된다.

---

4. 복소수 벡터의 Inner Product

실수 벡터에서 내적은 다음이었다.

$$y^T x$$

복소수 벡터에서는 첫 번째 벡터에 켤레전치를 취한다.

$$y^H x$$

즉,

$$y^H x = \bar{y}_1x_1+\bar{y}_2x_2+\cdots+\bar{y}_nx_n$$

이다.

이 값은 일반적으로 복소수일 수 있다.

하지만 같은 벡터끼리 내적하면 항상 실수이면서 0 이상이다.

$$z^Hz = |z_1|^2+|z_2|^2+\cdots+|z_n|^2 \geq 0$$

그리고 $z=0$일 때만 $z^Hz=0$이다.

따라서 복소수 벡터 공간에서 길이와 내적을 제대로 정의하려면 반드시 conjugate transpose를 사용해야 한다.

---

5. Hermitian Matrix

실수 행렬에서 대칭행렬은 다음 조건을 만족한다.

$$A^T=A$$

하지만 복소수 행렬에서는 단순 전치만으로는 부족하다.

복소수 행렬에서는 전치와 켤레를 함께 적용해야 한다.

$$A^H=\bar{A}^T$$

복소수 행렬에서 대칭행렬에 해당하는 개념은 Hermitian matrix이다.

Hermitian matrix는 다음 조건을 만족한다.

$$A^H=A$$

즉 전치하고 모든 성분에 complex conjugate를 취해도 자기 자신으로 돌아오는 행렬이다.

예를 들어 다음 행렬을 보자.

$$A= \begin{bmatrix} 2 & 3+i \\ 3-i & 5 \end{bmatrix}$$

이 행렬은 Hermitian matrix이다.

대각성분 $2$, $5$는 실수이다. 대각선 밖의 성분은 서로 켤레 관계이다.

$$3+i \quad \leftrightarrow \quad 3-i$$

Hermitian matrix는 실수 대칭행렬의 복소수 버전이다.

실수 대칭행렬처럼 Hermitian matrix도 다음 성질을 가진다.

1. 고유값이 모두 실수이다.
2. 고유벡터를 orthonormal하게 선택할 수 있다.

---

6. 복소수 공간에서의 직교성과 Unitary Matrix

복소수 벡터 $q_i$, $q_j$가 직교한다는 것은 다음을 의미한다.

$$q_i^H q_j=0 \qquad (i\neq j)$$

또 단위벡터라는 것은 다음을 의미한다.

$$q_i^H q_i=1$$

따라서 복소수 공간에서 orthonormal basis는 다음 조건을 만족한다.

$$q_i^H q_j= \begin{cases} 1, & i=j \\ 0, & i\neq j \end{cases}$$

이 벡터들을 열로 모은 행렬을 $Q$라고 하자.

$$Q= \begin{bmatrix} | & | & & | \\ q_1 & q_2 & \cdots & q_n \\ | & | & & | \end{bmatrix}$$

실수 공간에서는 orthogonal matrix가 다음을 만족했다.

$$Q^TQ=I$$

복소수 공간에서는 transpose 대신 Hermitian transpose를 사용한다.

$$Q^HQ=I$$

이런 행렬을 unitary matrix라고 한다.

unitary matrix는 복소수 버전의 orthogonal matrix이다.

unitary matrix에서는 역행렬이 아주 간단하다.

$$Q^{-1}=Q^H$$

즉 복소수에서는 $Q^T$가 아니라 $Q^H$가 역행렬 역할을 한다.

---

7. Fourier Matrix

복소수 행렬에서 가장 중요한 예시 중 하나가 Fourier matrix이다.

Fourier matrix는 Fourier transform을 행렬 형태로 표현한 것이다. 이 행렬은 full matrix이지만 매우 특별한 구조를 가지고 있다.

$n\times n$ Fourier matrix를 만들기 위해 다음 복소수를 사용한다.

$$\omega_n=e^{2\pi i/n}$$

이 값은 $n$제곱하면 1이 되는 복소수이다.

$$\omega_n^n=1$$

이를 $n$-th root of unity라고 한다.

복소평면에서 $\omega_n$은 단위원 위에서 전체 원을 $n$등분했을 때 한 칸만큼 회전한 위치에 있다.

예를 들어 $n=6$이면,

$$\omega_6=e^{2\pi i/6}$$

이고, 이는 단위원에서 60도 회전한 점이다.

그 거듭제곱들은 다음처럼 단위원 위를 한 바퀴 돈다.

$$1,\omega_6,\omega_6^2,\omega_6^3,\omega_6^4,\omega_6^5$$

그리고,

$$\omega_6^6=1$$

이다.

---

8. 일반적인 Fourier Matrix의 형태

Fourier matrix $F_n$의 $(i,j)$번째 성분은 다음처럼 쓸 수 있다.

$$(F_n)_{ij}=\omega_n^{ij}$$

여기서 $i,j$는 $0$부터 $n-1$까지의 값을 가진다고 본다.

즉,

$$i,j=0,1,2,\dots,n-1$$

이다.

그러면 Fourier matrix는 다음 형태가 된다.

$$F_n= \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)^2} \end{bmatrix}$$

여기서 $\omega=\omega_n$이다.

이 행렬은 성분이 하나도 0이 아닌 full matrix이다. 일반적으로 full $n\times n$ matrix를 벡터에 곱하려면 $n^2$번 정도의 곱셈이 필요하다.

하지만 Fourier matrix는 특별한 구조 덕분에 훨씬 빠르게 곱할 수 있다. 이것이 FFT의 핵심이다.

---

9. $4\times 4$ Fourier Matrix

$n=4$일 때를 보자.

$$\omega_4=e^{2\pi i/4}=e^{i\pi/2}=i$$

따라서,

$$\omega_4=i, \qquad \omega_4^2=-1, \qquad \omega_4^3=-i, \qquad \omega_4^4=1$$

이다.

이를 이용하면 $4\times 4$ Fourier matrix는 다음과 같다.

$$F_4= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix}$$

각 성분은 $\omega_4^{ij}$의 형태로 만들어진다.

예를 들어 마지막 성분은 $i^9$이다.

$$i^9=i$$

이 행렬은 Fourier transform의 4-point 버전이다.

---

10. Fourier Matrix의 열들은 직교한다

Fourier matrix의 중요한 성질은 열들이 서로 직교한다는 것이다.

다만 복소수 행렬이므로 내적을 계산할 때 반드시 conjugate를 취해야 한다.

예를 들어 $F_4$의 두 열을 비교해 보자.

두 번째 열과 네 번째 열은 다음이다.

$$c_2= \begin{bmatrix} 1 \\ i \\ -1 \\ -i \end{bmatrix}, \qquad c_4= \begin{bmatrix} 1 \\ -i \\ -1 \\ i \end{bmatrix}$$

단순히 $c_2^Tc_4$를 계산하면 원하는 직교성이 보이지 않는다.

복소수 내적은 다음처럼 계산해야 한다.

$$c_2^H c_4$$

즉 $c_2$를 켤레전치한 뒤 곱한다.

$$c_2^H= \begin{bmatrix} 1 & -i & -1 & i \end{bmatrix}$$

따라서,

$$c_2^Hc_4 = 1+(-i)(-i)+(-1)(-1)+i(i)$$

정리하면,

$$1+(-1)+1+(-1)=0$$

이다.

따라서 두 열은 직교한다.

이처럼 Fourier matrix의 열들은 Hermitian inner product 기준으로 서로 직교한다.

---

11. Fourier Matrix의 정규화

$F_4$의 각 열의 길이 제곱은 4이다.

예를 들어 첫 번째 열은 다음이다.

$$\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}$$

길이 제곱은 다음이다.

$$1^2+1^2+1^2+1^2=4$$

따라서 길이는 2이다.

열들을 단위벡터로 만들려면 $F_4$ 전체에 $\frac{1}{2}$를 곱하면 된다.

$$\frac{1}{2}F_4$$

이 정규화된 Fourier matrix는 unitary matrix가 된다.

$$\left(\frac{1}{2}F_4\right)^H \left(\frac{1}{2}F_4\right) =I$$

일반적인 $F_n$에서는 열의 길이가 $\sqrt{n}$이므로, $\frac{1}{\sqrt{n}}F_n$이 unitary matrix가 된다.

$$\left(\frac{1}{\sqrt{n}}F_n\right)^H \left(\frac{1}{\sqrt{n}}F_n\right) =I$$

따라서 정규화된 Fourier matrix의 역행렬은 Hermitian transpose이다.

$$F^{-1}=F^H$$

정확히는 $F$를 unitary하게 정규화했을 때 위 식이 그대로 성립한다. 정규화하지 않은 $F_n$에 대해서는 상수배가 추가된다.

---

12. FFT가 필요한 이유

Fourier matrix는 full matrix이다.

따라서 아무 구조를 이용하지 않고 $F_nx$를 계산하면 대략 $n^2$번의 곱셈이 필요하다.

$$\text{naive cost} \approx n^2$$

하지만 Fourier transform은 과학 계산, 신호처리, 이미지 처리, 음성 처리 등에서 반복적으로 등장한다.

$n^2$ 계산은 $n$이 커지면 너무 느리다.

Fast Fourier Transform, 즉 FFT는 Fourier matrix의 특수한 구조를 이용해 계산량을 크게 줄이는 알고리즘이다.

핵심은 다음이다.

$$n^2 \quad \longrightarrow \quad n\log_2 n$$

강의에서는 더 구체적으로 곱셈 수가 대략 다음 수준까지 줄어든다고 설명한다.

$$\frac{1}{2}n\log_2 n$$

즉 FFT는 단순한 공식 하나가 아니라, Fourier matrix를 잘 factorization해서 곱셈을 빠르게 만드는 아이디어이다.

---

13. FFT의 핵심 아이디어: 큰 Fourier Matrix를 작은 Fourier Matrix로 나누기

FFT의 핵심은 $F_{64}$ 같은 큰 Fourier matrix를 $F_{32}$ 두 개로 나누는 것이다.

이때 중요한 관계는 다음이다.

$$\omega_{64}^2=\omega_{32}$$

$\omega_{64}$는 단위원을 64등분한 한 칸 회전이고, 이를 제곱하면 각도가 두 배가 되어 단위원을 32등분한 한 칸 회전이 된다.

이 성질 때문에 $64$-point Fourier transform은 $32$-point Fourier transform 두 개로 쪼갤 수 있다.

구조적으로는 다음과 같은 형태를 가진다.

$$F_{64} = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{32} & 0 \\ 0 & F_{32} \end{bmatrix} P$$

여기서 $P$는 permutation matrix이다.

$P$는 입력 벡터의 성분을 짝수 인덱스와 홀수 인덱스로 나누어 재배열한다.

$$x_0,x_1,x_2,x_3,\dots \quad \longrightarrow \quad x_0,x_2,x_4,\dots,x_1,x_3,x_5,\dots$$

$D$는 diagonal matrix이다.

$$D= \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & \omega & \cdots & 0 \\ 0 & 0 & \omega^2 & 0 \\ \vdots & \vdots & \vdots & \ddots \\ 0 & 0 & 0 & \omega^{31} \end{bmatrix}$$

여기서 $\omega=\omega_{64}$이다.

이 분해의 의미는 다음이다.

1. 입력을 짝수 성분과 홀수 성분으로 나눈다.
2. 각각에 대해 $F_{32}$를 적용한다.
3. 대각행렬 $D$와 간단한 덧셈/뺄셈으로 결과를 합친다.

---

14. Recursion으로 더 작게 쪼개기

한 번 쪼개면 $F_{64}$가 $F_{32}$ 두 개로 바뀐다.

하지만 여기서 멈추지 않는다.

각 $F_{32}$도 다시 $F_{16}$ 두 개로 쪼갤 수 있다.

$$F_{32} \quad \longrightarrow \quad F_{16},F_{16}$$

그리고 다시,

$$F_{16} \quad \longrightarrow \quad F_8,F_8$$

이 과정을 계속하면 다음처럼 내려간다.

$$64 \rightarrow 32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

이런 재귀적 분해가 FFT의 핵심이다.

큰 Fourier transform을 한 번에 계산하지 않고, 작은 Fourier transform 여러 개로 나누어 계산한다.

각 단계에서 필요한 추가 작업은 permutation과 diagonal matrix 곱 정도이다.

permutation은 성분을 재배열하는 것이고, diagonal matrix 곱은 성분별 곱셈이므로 계산 비용이 작다.

---

15. 계산량 비교

단순 계산에서는 $F_nx$를 구할 때 약 $n^2$번의 곱셈이 필요하다.

하지만 FFT를 사용하면 계산량은 대략 다음이 된다.

$$\frac{1}{2}n\log_2 n$$

예를 들어 $n=1024$라고 하자.

단순 계산에서는 다음 정도의 곱셈이 필요하다.

$$1024^2$$

이는 약 백만 번 수준이다.

반면 FFT에서는 다음 정도가 된다.

$$\frac{1}{2}\cdot 1024\cdot \log_2 1024$$

$1024=2^{10}$이므로,

$$\log_2 1024=10$$

따라서,

$$\frac{1}{2}\cdot 1024\cdot 10 = 5120$$

이다.

단순 계산과 비교하면 약 200배 정도 차이가 난다.

즉 같은 시간에 Fourier transform을 1번 하던 일을 FFT를 사용하면 약 200번 할 수 있게 된다.

이 차이 때문에 FFT는 현대 과학계산과 신호처리에서 결정적인 알고리즘이 되었다.

---

16. 이번 강의의 핵심 정리

복소수 벡터와 행렬에서는 전치만으로는 부족하다.

전치할 때 complex conjugate도 함께 취해야 한다.

복소수 벡터의 길이 제곱은 다음이다.

$$z^Hz = |z_1|^2+|z_2|^2+\cdots+|z_n|^2$$

복소수 벡터의 inner product는 다음이다.

$$y^Hx$$

실수 대칭행렬의 복소수 버전은 Hermitian matrix이다.

$$A^H=A$$

실수 orthogonal matrix의 복소수 버전은 unitary matrix이다.

$$Q^HQ=I$$

Fourier matrix는 복소수 행렬의 가장 중요한 예시 중 하나이다.

$$(F_n)_{ij}=\omega_n^{ij}, \qquad \omega_n=e^{2\pi i/n}$$

Fourier matrix의 열들은 Hermitian inner product 기준으로 직교한다.

정규화하면 unitary matrix가 된다.

$$\frac{1}{\sqrt{n}}F_n$$

FFT는 Fourier matrix의 구조를 이용해 큰 Fourier transform을 작은 Fourier transform들로 쪼개는 알고리즘이다.

계산량은 단순 계산의 $n^2$에서 대략 $n\log_2 n$ 수준으로 줄어든다.

이번 강의는 positive definite matrix 자체보다는, 그 이후에도 계속 등장하는 복소수 내적과 unitary/Hermitian 구조를 정리하는 연결 지점이다.