Lecture 26. 복소 행렬과 푸리에 변환

지난 강의에서 대칭행렬이 자기 자신의 직교기저를 들고 태어난다는 것을 보았다. 직교기저의 위력은 L17에서 이미 배웠다. 계수를 구하는 데 연립방정식을 풀 필요가 없고 내적 한 번이면 끝난다.

이번 강의에서는 가장 유명한 직교기저를 만난다. 신호를 주파수로 갈라 놓는 기저이고, 음악 파일과 영상 통화와 의료 영상이 전부 그 위에 서 있다. 그런데 그 기저는 실수 세계에 살지 않는다. 복소수 위에 산다.

그래서 준비가 필요한데, 시작하자마자 문제가 하나 생긴다. 복소 벡터 $\vv{x} = \begin{bmatrix} 1 \\ i \end{bmatrix}$ 의 길이를 지금까지 배운 대로 $\vv{x}^{\mathsf T}\vv{x}$ 로 계산해 보자.

영벡터가 아닌데 길이가 0이다. 계산 착오가 아니라 지금까지의 정의가 복소수 위에서 무너진다는 신호이다. 이것부터 고치지 않으면 한 발짝도 나갈 수 없다.

1. 길이를 되찾는다¶

실수에서 $\vv{x}^{\mathsf T}\vv{x} = \sum x_j^2$ 가 길이의 제곱 노릇을 할 수 있었던 이유가 무엇인가. 제곱이 늘 음이 아니기 때문이다. 그래서 더한 것도 음이 아니고, 0이 되려면 모든 항이 0이어야 했다.

복소수에서는 그 성질이 깨진다. $i^2 = -1$ 이다. 그러면 복소수에서 늘 음이 아닌 것은 무엇인가. 절댓값의 제곱이다. $z = a + bi$ 에 대해

이다. 자기 켤레와 곱하면 늘 음이 아닌 실수가 나온다. 이것이 우리가 찾던 성질이다.

그러므로 길이의 제곱을 이렇게 고쳐 쓰면 된다.

앞의 예로 확인하자. $\vv{x} = (1, i)$ 이면 $\bar{\vv{x}} = (1, -i)$ 이므로

이다. 길이가 $\sqrt2$ 이다. 성분이 각각 크기 1이니 당연한 답이다.

켤레전치¶

"켤레를 취하고 전치한다"는 일이 앞으로 계속 나오므로 기호를 하나 만든다.

내적이 더 이상 대칭이 아니다¶

실수에서는 $\vv{x}^{\mathsf T}\vv{y} = \vv{y}^{\mathsf T}\vv{x}$ 였다. 복소수에서는 순서를 바꾸면 켤레가 된다.

각 항이 $\bar{y}_jx_j$ 와 $\bar{x}_jy_j$ 로 서로 켤레이기 때문이다. 다만 $\vv{x}^{\mathsf H}\vv{y} = 0$ 이면 그 켤레도 0이므로, 직교는 어느 쪽으로 재도 직교이다.

2. 에르미트 행렬과 유니타리 행렬¶

전치가 켤레전치로 바뀌었으니, 전치로 정의했던 두 종류의 행렬도 따라서 바뀐다.

에르미트 행렬 — 대칭행렬의 복소판¶

를 만족하는 행렬을 에르미트 행렬이라 한다. 성분으로 쓰면 $a_{jk} = \overline{a_{kj}}$ 이다.

대각 성분에 이 조건을 넣어 보자. $j = k$ 로 두면

이다. 에르미트 행렬의 대각 성분은 반드시 실수이다. 자기 켤레와 같은 수는 실수뿐이기 때문이다.

예를 들어 다음은 에르미트 행렬이다.

대각이 $2, 3$ 으로 실수이고, 대각 밖의 두 성분이 서로 켤레이다.

$H$ 의 고윳값을 실제로 구해 보면 1 과 4 로 실수이다. $\operatorname{tr}(H) = 5 = 1 + 4$ 이고 $\det H = 6 - (1-i)(1+i) = 6 - 2 = 4 = 1 \times 4$ 이니 L21의 검산 도구도 그대로 통한다.

유니타리 행렬 — 직교행렬의 복소판¶

를 만족하는 행렬을 유니타리 행렬이라 한다. 열들이 서로 직교하고 길이가 1이라는 뜻이다. L17의 직교행렬이 하던 일을 그대로 한다.

길이를 보존한다. 확인은 한 줄이다.

고윳값의 절댓값이 1이다. $U\vv{x} = \lambda\vv{x}$ 이고 $\vv{x} \neq \vv{0}$ 이면 (11)의 등식에 의해 양변의 길이가 같아야 한다.

고윳값이 전부 단위원 위에 있다. L21에서 회전행렬의 고윳값 $\pm i$ 를 단위원에 찍었던 그림이 여기서 회수된다. 회전행렬은 유니타리 행렬의 가장 단순한 예였던 것이다.

대응표¶

준비가 끝났다. 이제 유니타리 행렬 중 가장 유명한 하나를 만나러 가자.

3. 단위원 위의 $N$ 개 점¶

$N$ 개의 수를 다루려 한다. 소리를 $N$ 번 재서 얻은 표본이라고 생각해도 좋고 그냥 벡터라고 생각해도 좋다. 이 벡터를 담을 좋은 기저를 만들 것인데, 그 재료가 하나 필요하다.

오일러 공식으로 풀어 쓰면 $w = \cos\frac{2\pi}{N} - i\sin\frac{2\pi}{N}$ 이고, 절댓값이 1이다. $w$ 를 곱하는 것은 단위원 위에서 시곗바늘을 한 칸 돌리는 일이다. $N$ 등분한 눈금 하나만큼 돈다.

여기서 두 가지 성질이 나온다. 둘 다 지수법칙 한 줄이면 된다.

말로 옮기면 이렇다. $N$ 칸 돌면 제자리로 오고, 절반인 $N/2$ 칸 돌면 정반대편에 선다.

한 가지 더. $0 < s < N$ 이면 $w^s \neq 1$ 이다. 각도가 $-2\pi s/N$ 인데 $0 < s/N < 1$ 이라 한 바퀴를 채우지 못하기 때문이다. 이 사실도 곧 쓴다.

4. 푸리에 행렬¶

이제 행렬을 만든다.

성분이 첨자의 곱이라는 점이 특이하다. $j$ 와 $k$ 를 곱해서 그만큼 시곗바늘을 돌린 자리의 값을 적는 것이다.

$F_4$ 를 손으로 써 보자¶

$N = 4$ 이면 $w = e^{-2\pi i/4} = e^{-\pi i/2} = -i$ 이다. 거듭제곱을 먼저 정리하자.

$w^4 = 1$ 이므로 지수가 4를 넘으면 4로 나눈 나머지만 보면 된다. 예를 들어 $w^6 = w^{4+2} = w^2 = -1$ 이고 $w^9 = w^{8+1} = w = -i$ 이다.

이제 $(j,k)$ 자리에 $w^{jk}$ 를 적는다.

0행과 0열이 전부 1이다. $j = 0$ 이거나 $k = 0$ 이면 $jk = 0$ 이라 $w^0 = 1$ 이기 때문이다.

열은 주파수이고 행은 시각이다¶

$k$ 열을 위에서 아래로 읽어 보자. $w^{0 \cdot k}, w^{1 \cdot k}, w^{2 \cdot k}, \dots$ 이다. 시곗바늘이 한 걸음에 $k$ 칸씩 도는 수열이다. $k$ 가 클수록 빨리 도는 진동이다. $k = 0$ 열은 아예 돌지 않는 상수 신호이고, $k = 1$ 열은 $N$ 걸음에 한 바퀴 도는 가장 느린 진동이다.

$j$ 행은 반대로 시각 $j$ 에서 각 주파수가 어떤 값을 갖는지를 늘어놓은 것이다.

5. 직교성 — 이 강의의 결론¶

푸리에 행렬이 좋은 이유는 하나뿐이다. 열들이 서로 직교하기 때문이다.

증명해 보자. 3절에서 준비한 두 사실만 있으면 된다.

$(F^{\mathsf H}F)_{jk}$ 는 $F$ 의 $j$ 열과 $k$ 열의 내적이다. 성분으로 쓰면

이다. $|w| = 1$ 이므로 $\bar{w} = 1/w = w^{-1}$ 이고, 따라서 $\overline{w^{mj}} = w^{-mj}$ 이다. 지수를 합치면

이 되어 등비급수가 되었다. 공비는 $r = w^{k-j}$ 이다. 두 경우로 나눈다.

$j = k$ 일 때. $r = w^0 = 1$ 이므로 1을 $N$ 번 더하는 것이라 합이 $N$ 이다.

$j \neq k$ 일 때. $0 < |k - j| < N$ 이므로 3절 끝의 사실에 의해 $r \neq 1$ 이다. 그러면 등비급수 공식을 쓸 수 있다.

분자를 계산하자. 여기서 (14)의 $w^N = 1$ 이 쓰인다.

분자가 0이고 분모는 0이 아니므로 합이 0이다. 두 경우를 합치면 (19)의 식이다.

그래서 역변환이 공짜이다¶

(19)의 양변을 $N$ 으로 나누면 유니타리 행렬이 나온다.

$\frac{1}{\sqrt N}F$ 는 유니타리 행렬이다. 그리고 (19)의 양변에 $F^{-1}$ 을 곱하면 역행렬이 곧바로 나온다.

계수는 내적 한 번¶

$\vv{c} = F\vv{x}$ 를 성분으로 읽어 보자. $c_k$ 는 $F$ 의 $k$ 행과 $\vv{x}$ 의 곱인데, $F$ 는 $F_{jk} = w^{jk}$ 로 $j$ 와 $k$ 에 대칭이라 $k$ 행과 $k$ 열이 같다. 그러므로

이고, 이것은 $\vv{x}$ 와 $k$ 번째 주파수 기저의 내적이다.

L17에서 배운 그 원리 그대로이다. 직교기저에서는 계수를 구하려고 연립방정식을 풀지 않는다. 내적 한 번이면 된다. 그리고 (25)의 역변환은 그 계수들로 $\vv{x}$ 를 도로 조립하는 일이다.

푸리에 변환과 역변환이 거의 같은 모양인 이유가 이것이다. 유니타리 행렬이기 때문이다.

6. 그런데 $N^2$ 이 문제다¶

이론은 끝났다. 실제로 써 보면 곧 벽에 부딪힌다.

$N \times N$ 행렬을 벡터에 곱하려면 성분마다 곱셈 한 번씩, 모두 $N^2$ 번의 곱셈이 든다. $N$ 이 작을 때는 아무 문제가 없다. 그런데 소리 1초는 보통 44100번 재고, 3분짜리 노래 하나면 표본이 800만 개쯤 된다.

1조 번의 곱셈이다. 게다가 $N \times N$ 행렬을 메모리에 올리는 것부터 불가능하다. $N = 10^6$ 이면 복소수 10¹² 개, 16테라바이트가 넘는다.

행렬을 만들지 않고 곱해야 한다. 그리고 곱셈 횟수도 줄여야 한다. 다행히 두 가지가 한꺼번에 해결된다.

7. 푸리에 행렬을 쪼갠다¶

방법은 새롭지 않다. L4에서 $A = LU$ 를 배웠고 L17에서 $A = QR$ 을 배웠다. 복잡한 행렬을 단순한 행렬들의 곱으로 쪼개는 것. 여기서도 같은 일을 한다. 다만 쪼개진 조각들이 극단적으로 성기어서 곱셈의 대부분이 0과의 곱이 되어 건너뛸 수 있을 뿐이다.

짝수와 홀수로 나눈다¶

$N = 2n$ 이 짝수라 하자. $\vv{y} = F_{2n}\vv{x}$ 의 $j$ 성분을 쓴다.

합을 $k$ 가 짝수인 것과 홀수인 것으로 가른다. 짝수는 $k = 2m$, 홀수는 $k = 2m+1$ 로 쓰면 각각 $m = 0, \dots, n-1$ 이다.

뒤쪽 합에서 $w^{j(2m+1)} = w^{j}\,w^{2jm}$ 이므로 $w^j$ 를 밖으로 빼낸다.

여기서 절반 크기의 문제가 나타난다¶

$w^2$ 가 무엇인지 보자. 지수를 계산하면 된다.

이것은 크기 $n$ 짜리 문제의 $w$ 이다. 그러니 (31)의 두 합이 각각 $F_n$ 을 곱하는 일이다. 짝수 자리만 모은 벡터를 $\vv{x}_{\text{짝}}$, 홀수 자리만 모은 벡터를 $\vv{x}_{\text{홀}}$ 이라 하고

이라 두면, $j = 0, \dots, n-1$ 에 대해

이다. 크기 $2n$ 문제의 절반이 크기 $n$ 문제 두 개로 풀렸다.

나머지 절반은 부호만 다르다¶

남은 것은 $j = n, \dots, 2n-1$ 이다. $j + n$ 자리를 계산해 보자. 두 조각을 따로 본다.

앞의 합. $\left(w^2\right)^{(j+n)m} = \left(w^2\right)^{jm}\left(w^2\right)^{nm}$ 인데, $w^2$ 는 크기 $n$ 문제의 $w$ 이므로 $\left(w^2\right)^n = 1$ 이다. 뒤 인수가 1이라 사라진다. 곧 앞의 합은 $j$ 일 때와 똑같다.

밖으로 뺀 $w^j$. 여기가 핵심이다.

(15)의 $w^{N/2} = -1$ 이 여기서 쓰였다. 부호만 뒤집힌다.

행렬로 쓰면 인수분해이다¶

(34)의 식과 (36)의 식을 행렬로 묶으면 이렇게 된다.

세 조각의 정체가 각각 분명하다.

• $P$ 는 짝수 자리를 앞으로, 홀수 자리를 뒤로 보내는 순열행렬이다. L5에서 배운 그 순열행렬이다. 곱셈이 한 번도 필요 없고 자리만 옮기면 된다.

• 가운데는 절반 크기 문제 두 개이다. 블록 밖이 전부 0이라 곱셈이 절반으로 준다.

• 앞은 둘을 합치는 조각이다. $D$ 가 대각행렬이라 곱셈이 $n$ 번뿐이고, 아래 블록은 위 블록의 부호만 뒤집은 것이라 계산을 다시 할 필요가 없다.

이것을 고속 푸리에 변환(FFT)이라 한다.

8. 얼마나 빨라지는가¶

$F_n$ 이 다시 절반으로 쪼개지고, 또 쪼개진다. $N$ 이 2의 거듭제곱이면 크기 1이 될 때까지 계속 쪼갤 수 있다.

크기 $N$ 문제를 푸는 데 드는 곱셈 횟수를 $T(N)$ 이라 하자. (37)에서 절반 문제가 둘이고, 합치는 데 $D$ 의 곱셈이 $N/2$ 번 든다.

풀어 보자. 한 단계 내려갈 때마다 문제 크기가 절반이 되므로 $\log_2 N$ 단계만에 크기 1에 닿는다. 그리고 각 단계에서 합치는 비용은, 문제가 두 배로 많아지는 대신 각각이 절반 크기라 총합이 늘 $N/2$ 로 같다.

$N^2$ 이 $\frac{N}{2}\log_2 N$ 으로 줄었다.

숫자로 보면 차이가 실감난다.

9. 자주 하는 오해¶

복소 벡터에 $\vv{x}^{\mathsf T}\vv{x}$ 를 쓰는 것¶

이 강의가 그 이야기로 시작했다. 실수에서는 맞고 복소수에서는 틀린다. 특히 코드에서 A.T 를 쓰면 오류 없이 조용히 틀린 답이 나오므로 위험하다. 복소수를 다루는 순간부터 A.conj().T 를 반사적으로 써야 한다.

부호 규약과 정규화 상수를 섞는 것¶

4절에서 경고했다. $w$ 의 지수 부호와 $1/N$ 을 어디에 붙이는지가 책마다 다르다. 어느 쪽을 쓰는지 정하고 끝까지 그것만 쓰면 된다. 검산은 간단하다. $F^{-1}F = I$ 가 나오는지 확인하면 된다.

FFT가 DFT의 근사라는 오해¶

결과가 완전히 같다. FFT는 새로운 변환이 아니라 같은 행렬을 곱하는 더 빠른 방법이다. 부동소수점 오차는 오히려 FFT 쪽이 더 작다. 연산 횟수가 적어 오차가 덜 쌓이기 때문이다.

$N$ 이 2의 거듭제곱이어야 한다는 오해¶

7절의 유도는 $N$ 이 짝수라는 것만 썼고, 끝까지 쪼개려면 2의 거듭제곱이 편하다. 그러나 실제 라이브러리는 $N$ 을 소인수분해해서 3이든 5든 같은 방식으로 쪼갠다. 소수인 $N$ 을 위한 방법도 따로 있다. numpy.fft 는 아무 $N$ 이나 받는다.

에르미트 행렬의 대각에 허수를 쓰는 것¶

(8)에서 본 대로 대각은 반드시 실수이다. $\begin{bmatrix} i & 1 \\ 1 & 0\end{bmatrix}$ 은 에르미트가 아니다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

복소수 위에서 길이와 직교를 다시 정의하는 일부터 시작했다. 핵심은 하나, 전치 대신 켤레전치를 쓰는 것이었다. 그 약속 하나로 대칭은 에르미트가 되고 직교는 유니타리가 되며 스펙트럼 정리는 모양을 그대로 유지했다.

그다음 그 유니타리 행렬 중 가장 유명한 것을 만났다. 단위원을 $N$ 등분한 점들로 만든 푸리에 행렬이었고, 그 열들이 서로 직교한다는 사실 하나가 역변환을 공짜로 만들었다. L17에서 배운 "직교기저에서는 계수를 내적 한 번으로 구한다"는 원리가, 신호처리라는 전혀 다른 무대에서 그대로 작동한 것이다.

마지막으로 그 행렬을 쪼갰다. 짝수와 홀수로 나누자 절반 크기의 문제 두 개가 나타났고, $w^{N/2} = -1$ 덕분에 나머지 절반은 부호만 뒤집으면 되었다. $N^2$ 이 $N\log N$ 이 되었다. 새로운 수학이 아니라 행렬 인수분해였다.

다음 강의에서는 다시 실수의 세계로 돌아간다. 그리고 지난 강의에서 남겨 둔 물음에 답한다. 대칭행렬의 고윳값이 실수인 것까지는 알았는데, 그 실수들이 전부 양수라면 무슨 일이 벌어지는가. 별것 아닌 조건 같지만 그 하나에서 최소값과 타원과 안정성이 한꺼번에 따라 나온다.

이번 강의의 내용을 파이썬으로 확인해 보려면 L26 실습 노트북으로 넘어가면 된다. A.T 와 A.conj().T 가 어떻게 다른 답을 내는지 보고, $F^{\mathsf H}F = NI$ 를 직접 확인하며, FFT를 재귀 함수 열 줄로 짜서 numpy.fft 와 대조하고 속도를 재 볼 수 있다.