해당 글은 빠른 이산 푸리에 변환(FFT)이 가능한 수학적 내용을 위주로 서술합니다. 따라서 푸리에 변환 및 역변환을 빠르게 수행하는 Cooley-Tukey 알고리즘 등에 대해서는 다루지 않습니다.
합성곱(Convolution)연산은 함수를 입력받고 연산된 함수를 반환한다. 이는 입력된 함수의 특징을 추출할 수 있는 함수를 얻기 위해 사용되며, 원하는 특징을 추출할 수 있는 또 다른 함수가 합성곱 연산에 사용된다. 합성곱을 수행하는 방법 중 푸리에 변환은 가장 유명하다.
푸리에 변환은 오일러 공식(Euler’s formula)을 통해 알 수 있는 $\exp{x}$ 함수의 복소평면에서의 특징을 이용한다. 이런 특징이란, $\exp{x}$함수는 복소평면에서 원의 형태를 가진다는 것이다. 즉, $\exp{xi} = \cos{x} + i\sin{x}$라는 형태에서 exp함수를 주기 함수로 이용할 수 있다.
결국 푸리에 변환은 이러한 주기적 특성을 이용하여 주어진 함수의 주파수 성분을 분해한다. 이산 합성곱의 상황에서는 이와 다른 방향으로 주기성을 이용한다. 주의할 점은, 이산 합성곱의 상황에서는 DFT 자체가 원래 목적의 합성곱을 수행하지는 않는다는 것이다. 물론 DFT가 합성곱을 수행하기는 하지만, 원래 목적의 합성곱은 DFT이 이루어지고 나서 이루어진다. 이는 아래 내용을 통해 이해할 수 있을 것이다.
이산 합성곱은 함수가 주어졌을 때, 적분 대신 합을 하는 과정으로 생각할 수 있다. 즉, 다음과 같은 형태이다.
\[c_k=\sum_{i=0}^{k}a_i\cdot b_{k-i}\]$c_0 = c_0 \times b_0$
$c_1 = a_0 \times b_1 + a_1 \times b_0$
$c_2 = a_0 \times b_2 + a_1 \times b_1 + a_2 \times b_0$
$\dots$
이때, $a_i$와 $b_i$는 각 함수의 계수를 나타낸다.
특히, 컴퓨터 과학에서 사용하는 형태는 다항함수에 대한 이산 합성곱이다. 이런 경우, matrix로 생각할 수 있다. 모든 다항함수는 선형 시스템(Linear system)으로 표현할 수 있기 때문이다. 대표적인 예가 이미지를 처리하는 인공신경망인 CNN에서 사용하는 kernel을 이용한 Convolution연산일 것이다. 즉, vector나 matrix와 같은 이산적 데이터가 주어지면 다른 어떤 vector 또는 matrix에 대해 함성곱을 수행한 vector나 matrix를 반환하는 것으로 생각할 수 있다.
일반적인 선형 시스템에서는 다항 함수를 ‘계수 표현’ 을 이용하여 표현한다. 다음과 같은 형태이다.
\[1 + x \Rightarrow (1, 1)\] \[1 + x^2 \Rightarrow (1, 0, 1)\] \[x + 4x^3 \Rightarrow (0, 1, 0, 4)\]하나의 계수 표현은 하나의 다항함수와 대응됨은 자명하다.
계수 표현이 아닌 방법으로 다항함수를 표현할 수 있을까? 다음과 같은 표현을 생각해 보자.
\[\left \{ (x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_n, y_n) \right \}\]이때, $y_i = f(x_i)$이다. $x_i$와 $y_i$를 이용하여 $XA = Y$와 같은 선형식을 만들 수 있는데, $X$는 $x_i$값들로 만들어진 행렬이고 $A$는 다항식의 계수 행렬, $Y$는 $y_i$로 이루어진 행렬이다. $X$는 $x_i$값들로 만들어진 행렬로 $x_i$의 제곱수 형태의 수들을 가지고 있는데, 선형 시스템의 $i$번째 row는 $f(x_i) = y_i$인 다항식을 표현하도록 구성되어 있다고 생각하면 쉽게 알 수 있을 것이다. 이러한 상황에서 $X$의 역행렬이 존재하면 $A$를 유일하게 표현할 수 있고, 이는 위와 같은 표현을 이용하여 다항함수 하나를 표현할 수 있다는 것이다. 이는 반데몬드(Vandermonde)행렬을 이용하여 증명될 수 있다. 단, 모든 $x_i$는 서로 다른 값을 가져야 한다.
반데몬드 행렬을 이용한 증명을 통해 위와 같은 표기법을 통해 다항함수 하나를 표현할 수 있음이 보장됨을 알았다. 이러한 표현을 ‘점값 표현’ 이라 한다. Lagrange형을 이용하여 점값 표현에서 다항함수를 구할 수 있고, 이는 점값 표현을 계수 표현으로 변환할 수 있음을 뜻한다.
이제 본 주제인 합성곱의 상황을 생각해 보자. 두 다항함수 $A$, $B$가 주어졌을 때, $A$와 $B$를 합성곱한 $C$를 구하는 상황은 다음과 같이 계수 표현으로 표현할 수 있다.
$A$의 계수 벡터 $a = (a_1, a_2, a_3, \dots, a_n)$와 $B$의 계수 벡터 $b = (b_1, b_2, b_3, \dots, b_n)$ 합성곱 하여 $C$의 계수 벡터 $c = (c_1, c_2, c_3, \dots, c_n)$을 구하라
계수 표현에서는 $c$를 구하기 위해 $a$와 $b$를 $O(N^2)$으로 구해야 한다. 하지만, 동일한 과정을 점값 표현으로 표현해 보자.
A의 점값 벡터 $a = (y_1, y_2, y_3, \dots, y_n)$와 $B$의 점값 벡터 $b = (y_1’, y_2’, y_3’, \dots, y_n’)$를 합성곱 하여 $c$의 점값 벡터 $c = (y_1y_1’, y_2y_2’, y_3y_3’, …, y_ny_n’)$을 구하라.
$c$의 표현으로 부터 점값 표현의 상태에서는 $c$를 구하기 위해 $O(N)$이면 충분하다는 사실을 발견할 수 있다.
하지만, 여전히 문제는 계수 표현에서 점값 표현으로 변환하는 과정에서 $O(N^2)$이 필요하다는 것이다. 이런 변환을 $O(N^2)$미만으로 줄일 수 있다면 점값 표현을 이용하여 더 빠르게 이산 합성곱을 수행할 수 있을 것이다.
이제 변환 과정을 생각해 보자. 계수 표현에서 점값 표현으로 변환하는 과정 또한 합성곱으로 생각할 수 있다. 합성곱에 사용되는 $x$값은 서로 다르다는 조건만 만족하면 되므로, 푸리에 변환에 사용되는 exp값을 이용할 수 있다. 여기서 이산 푸리에 변환 DFT이 등장한다.
FFT는 exp값이 복소평면에서 주기성을 가진다는 것에 초점을 맞추어, 동일한 주기를 가지는 두 개의 다항 함수로 바꾸는 과정을 반복한다. 주어진 다항함수를 2개로 나누어 각각 연산하고 다시 합치는 과정을 반복하므로써 $O(NlogN)$만에 작업을 완료한다.