Fast Fourier Transformation

나는 야호다.

오늘은 FFT에 대해 알아보겠다. 이의 이론적 배경을 위해서는 선형대수학에 대한 지식이 다소 필요할수 있으므로 알아서 잘 알아듣길 바란다. (설명은 할것이니 걱정안해도된다.)

선형대수학 기본

본인이 선형대수학에 자신이 있다면 이 부분은 과감히 넘겨도 좋다.

벡터에 대해서 들어본 적이 있는가? 보통 벡터라고 하면 떠올리는 게 고등학교 기하와 벡터에서 배우는 그 벡터일것이다. $$\overrightarrow{v} = (x,y)$$라고 쓰는 바로 그 벡터이다.

이를 일반화한 개념이 벡터공간이고, https://ko.m.wikipedia.org/wiki/벡터_공간

에 잘 나와있으니 저만큼은 읽길 바란다.

우리가 기존에 알던 이차원 평면, 삼차원 공간들도 모두 벡터공간이다. 하지만 우리가 본 내용에서 다뤄야하는 것은 주기를 $$n$$으로 가지는 무한복소수열이다. 이 수열로 이루어진 벡터공간을 편의상 $$V_n$$이라고 하겠다.

일반적으로 복소벡터공간에서 다뤄지는 내적은 에르미트 내적이라고 해서 다음과 같이 정의된다.

$$<\cdot ,\cdot >: V_n \times V_n\rightarrow K$$

$$x=(x_j), y=(y_j)$$ 일때, $$<x, y> = \sum {x_j \bar{y_j}}$$

내적이 어떻게 정의되는지, 왜 이런식으로 정의 되어야 하는지에 대해서도 장황하게 설명할수 있으나 넘어가겠다.

복소벡터공간의 기저

이 복소벡터공간은 당연히 $$n$$차원이고, 푸리에라는 작자가 이 공간의 유용한 직교기저를 하나 찾았다. 다음과 같은 $$\phi_k$$가 기저가 된다.

$$\phi_k=(a_j), a_j=e^{\frac{2 \pi i}{n}jk}$$

단순계산으로 서로 다른 $$\phi_k$$가 직교함을 쉽게 보일수 있고 $$\phi_0, ... \phi_{n-1}$$이 $$V_n$$의 직교기저가 된다.

이산 푸리에 변환

우리가 왜 저런 이상한 직교기저가 필요한것일까?

임의의 벡터공간의 원소 $$(a_i)\in V_n$$에 대해서 다음과 같은 변환을 정의해보겠다.

$$F : V_n \rightarrow V_n$$, $$ F((a_j)) = (\sum a_k \phi_{k,j})$$

이 변환 $$F$$를 이산 푸리에 변환이라고 한다. 그러면 이 변환은 어떤 의미를 가지는가?

$$w=e^{\frac{2 \pi i}{n}}$$라고 한다면

우리는 $$F( (a_j)) = (\sum a_k w^{kj})$$로 변할 수 있다.

이는 다항식 $$a_0+a_1x+...+a_{n-1}x^{n-1}$$에서 $$w^j$$를 대입한 값이 된다.

$$j$$는 0부터 $$n-1$$까지 이므로 $$F((a_j))$$는 $$a$$를 계수로 가지는 $$n-1$$ 차 다항식에 $$w^j$$을 대입한 값을 $$j$$번째 수로 가지는 수열이 된다.

이산 푸리에 역변환

기저의 정의에 의해 이산 푸리에 변환은 역변환도 존재하고, 이 역변환을 이산 푸리에 역변환이라고 한다. 역변환은 다음과 같은 과정으로 구할 수 있다.

$$
\begin{aligned}
(A_k) &= \sum_{\substack{j}} a_j \phi_j\\
A_k\bar{\phi_{l,k}} &=\sum_{\substack{j}}  a_j \phi_{j,k} \bar{\phi_{l,k}} \\
\sum_{\substack{k}} A_k\bar{\phi_{l,k}} &=\sum_{\substack{k}}  \sum_{\substack{j}}  a_j \phi_{j,k} \bar{\phi_{l,k}} \\
&= na_l\\
a_l &= \frac{1}{n}\sum_{\substack{k}} A_k\bar{\phi_{l,k}}\\
&=\frac{1}{n}\sum_{\substack{k}} A_k\bar{\phi_{k,l}}\\
(a_l)&=\frac{1}{n}\sum_{\substack{k}} A_k \bar{\phi_{k}}
\end{aligned}
$$

즉, $$\phi$$대신 $$\bar{\phi}$$를 써서 계산한 후, $$n$$으로 나누어주면 역변환이 된다.

Convolution

컨볼루션은 $$x,y \in V_n$$에 대해서 $$F(x)F(y)=F(z)$$를 만족하는 $$z$$를 $$x,y$$의 컨볼루션이라고 정의하고, $$z=x*y$$로 쓴다. (여기서 F(x)와 F(y)의 곱은 성분별 곱)

$$
\begin{aligned}
F(x * y) &= F(x)F(y)\\
&=(\sum_{\substack{j}} x_j \phi_j) (\sum_{\substack{k}} y_k \phi_k)\\
&=(\sum_{\substack{j,k}}x_j y_k \phi_j \phi_k)\\
&=(\sum_{\substack{j,k}}x_j y_{k-j} \phi_j \phi_{k-j})\\
&=(\sum_{\substack{k}} \sum_{\substack{j}}x_j y_{k-j} \phi_k)\\
c_k &=\sum_{\substack{j}}x_j y_{k-j}
\end{aligned}
$$

여기서 $$c_k$$가 $$a_k$$와 $$b_k$$의 다항식 곱 꼴이라는것을 알 수 있다.

FFT

만약 $$a_k$$와 $$b_k$$가 있을 때 $$c_k$$를 계산하는데 얼마나 시간이 걸릴것같나?

단순히 곱해서 계산하면 $$O(n^2)$$의 시간이 걸린다.

더 빨리 계산하는 방법은 없는가?

만약 이산 푸리에 변환을 빠르게 계산할 수 있으면, $$x*y=F^{-1}(F(x)F(y))$$를 계산해서 컨볼루션을 빠르게 구할수 있다.

킹할갓복을 이용해서 이를 $$O(nlogn)$$만에 구할수 있으며, 이는 수학과 관련없는 글이기 때문에, 나중에 실제 알고리즘의 구현에 대해 다시 글을 올리는 것으로 하겠다.

(누가 올려주겠지 낄낄)

글이 길어져서 이만 줄인다.