필립 클라인의 저서 코딩 더 매트릭스 11장 특수 기저

다항식의 평가와 인터폴레이션을 알아봅니다.
내적이 복소수 필드에 대해 적용될 때 정의를 알아봅니다.
이산 푸리에 변환과 고속 푸리에 변환 (FFT)를 알아봅니다.
순환행렬의 특징을 알아봅니다.

다항식 평가와 인터폴레이션 (interpolation)

차수가 $d$ 인 다항식(polynomial)은 다음 형태를 가지는 단일 변수의 함수입니다.

f(x) = a_0 1 + a_1 x^1 + a_2 x^2 + ... + a_d x^d

함수 $f(x)$ 의 $x$ 값을 대입해 값을 얻는 것을 다항식을 평가한다고 합니다. 예를 들어 다항식 $2 + 3x + x^2$ 을 7에 대해 평가하면 72를 얻습니다.

다항식의 차수가 2이상일 때 함수 자체는 선형함수가 아니지만 각 변수 $x$ 의 값을 달리하고 행렬-벡터 곱셈으로 표현하면 선형함수입니다. 예를 들어 $r_i^d$ 를 $f(x)$ 에 대입하는 행렬-벡터 곱셈은 다음과 같이 표현할 수 있습니다.

\begin{bmatrix} r_0^0 & r_0^1 & r_0^2 & r_0^3 \\ r_1^0 & r_1^1 & r_1^2 & r_1^3 \\ & ... & & \\ r_{k-1}^0 & r_{k-1}^1 & r_{k-1}^2 & r_{k-1}^3 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix}

왼쪽의 행렬은 $x^d$ 에 대입한 값에 대응합니다. 오른쪽 벡터는 다항식의 계수입니다. 다항식의 평가가 위 행렬-벡터 곱셈 연산을 수행하는 것이라면 반대로 결과값을 알고 계수를 구하는 것을 인터폴레이션(interpolation)이라 합니다. 다항식 평가와 인터폴레이션은 역함수 관계입니다.

복소수 필드에 대한 내적

복소수 필드상의 벡터들에 대한 내적은 다음과 같이 정의됩니다.

\langle u, v \rangle = \bar{u} \cdot v

여기서 $\bar{u}$ 는 $u$ 의 켤레 복소수 벡터입니다. 이러한 정의는 복소수 벡터 $v$ 의 norm이 음수가 아님을 보장합니다.

\begin{aligned} \langle v, v \rangle & = [\bar{z_1}, ..., \bar{z_n}] \cdot [z_1, ..., z_n] \\ & = \bar{z_1} z_1 + ... + \bar{z_n} z_n \\ & = |z_1|^2 + ... + |z_n|^2 \end{aligned}

이것은 음수가 아닌 실수입니다.

예를 들어 $w = e^{\theta i}$ 라고 할 때 $v = [w^0, w^1, ..., w^n]$ 이면 $\langle v, v \rangle$ 는 다음과 같습니다.

\begin{aligned} \langle v, v \rangle & = \bar{v} \cdot v \\ & = e^{\theta i \cdot 0 - \theta i \cdot 0} + e^{\theta i \cdot 1 - \theta i \cdot 1} + ... + e^{\theta i \cdot n - \theta i \cdot n} \\ & = 1 + 1 + ... + 1 = n \end{aligned}

한편 복소수 필드상의 벡터 내적은 실수상의 벡터 내적과 다르게 대칭성이 성립하지 않습니다. 즉, 복소수 벡터 $u$ , $v$ 에 대해 $\langle u, v \rangle = \langle v, u \rangle$ 가 항상 성립하는 것은 아닙니다. 예를 들어 $u = [1 + 2i, 1]$ , $v = [2,1]$ 라고 할 때,

\begin{aligned} \langle u, v \rangle & = \begin{bmatrix} 1 - 2i & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 1 \end{bmatrix} \\ & = \begin{bmatrix} 2 - 4i + 1 \end{bmatrix} \\ \langle v, u \rangle & = \begin{bmatrix} 2 & 1 \end{bmatrix} \begin{bmatrix} 1 + 2i \\ 1 \end{bmatrix} \\ & = \begin{bmatrix} 2 + 4i + 1 \end{bmatrix} \end{aligned}

위와 같이 $\langle u, v \rangle$ 와 $\langle v, u \rangle$ 의 값은 다를 수 있습니다.

복소수 필드에서 직교하는 두 벡터의 내적은 실수에서와 같이 0입니다. 예를 들어 $u = [e^{\frac{0 \cdot \pi i}{2}}, e^{\frac{1 \cdot \pi i}{2}}, e^{\frac{2 \cdot \pi i}{2}}, e^{\frac{3 \cdot \pi i}{2}}]$ 이고 $v = [e^{0 \cdot \pi i}, e^{1 \cdot \pi i}, e^{2 \cdot \pi i}, e^{3 \cdot \pi i}]$ 의 내적은 다음과 같습니다.

\begin{aligned} e^{-\frac{0 \cdot \pi i}{2}} e^{0 \cdot \pi i} + e^{-\frac{1 \cdot \pi i}{2}} e^{1 \cdot \pi i} + e^{-\frac{2 \cdot \pi i}{2}} e^{2 \cdot \pi i} + e^{-\frac{3 \cdot \pi i}{2}} e^{3 \cdot \pi i} \\ = e^{\frac{0 \cdot \pi i}{2}} + e^{\frac{1 \cdot \pi i}{2}} + e^{\frac{2 \cdot \pi i}{2}} + e^{\frac{3 \cdot \pi i}{2}} \end{aligned}

위의 마지막 식은 등비수열의 합이므로 $\frac{exp(\frac{0 \cdot \pi i}{2}) (exp(\frac{4 \cdot \pi i}{2}) - 1)}{exp(\frac{1 \cdot \pi i}{2}) - 1}$ 와 같이 쓸 수 있고 $exp(\frac{4 \cdot \pi i}{2})$ 는 오일러의 공식에 의해 $cos 2\pi + (sin 2\pi)i = 1$ 이므로 내적값은 0입니다. 따라서 $u$ 와 $v$ 는 직교합니다.

복소수 필드 상의 행렬 $A$ 의 에르미트 수반행렬은 $A^H$ 로 나타내고 이것은 $A$ 의 전치행렬에서 각 원소의 켤레복소수를 취함으로써 얻어지는 행렬입니다. 복소 필드상의 행렬 $A$ 는 만약 $A$ 가 정방행렬이고 $A^H A$ 가 단위행렬이면 유니터리(unitary)라고 말합니다. 직교행렬에 의한 곱이 norm을 보존하는 것처럼 유니터리 행렬에 의한 곱셈은 norm을 보존합니다.

이산 푸리에 변환

$w = exp(\frac{2\pi}{n}i)$ 라 하고 $F(t) = w^t$ 로 정의되는 함수 $F: \Bbb{R} \to \Bbb{C}$ 를 고려해 보겠습니다. $t = 0$ 에서 오일러의 공식에 의해 $w^0 = exp(\frac{2 \pi}{n} i \cdot 0) = cos (\frac{2 \pi}{n}\cdot 0) + (sin (\frac{2 \pi}{n} \cdot 0))i = 1 + 0i$ 라 쓸 수 있습니다. $t = n, 2n, 3n, ...$ 인 경우 $1 + 0i$ 로 돌아옵니다. 따라서 이 함수의 주기는 $n$ , 주파수는 $\frac{1}{n}$ 이라 할 수 있습니다.

이번에는 함수 $k = 0, 1, 2, 3, ..., n-1$ 에 대해 $F_0$ , $F_1$ , $F_2$ , $F_3$ , ..., $F_k$ 를 정의해 보겠습니다.

\begin{aligned} F_0(x) &= \frac{1}{\sqrt{n}}w^{0 \cdot t} \\ F_1(x) &= \frac{1}{\sqrt{n}}w^{1 \cdot t} \\ F_2(x) &= \frac{1}{\sqrt{n}}w^{2 \cdot t} \\ F_3(x) &= \frac{1}{\sqrt{n}}w^{3 \cdot t} \\ & ... \\ F_k(x) &= w^{k \cdot t} \end{aligned}

$F_0(x)$ 를 제외한 각각의 함수는 주기 $n$ , $\frac{n}{2}$ , $\frac{n}{3}$ , ..., $\frac{n}{k}$ 을 갖습니다. $F_0(x)$ 의 경우 주기 $\frac{n}{0}$ , 즉 무한대를 갖는데 이는 시계가 움직이지 않는 경우를 생각하면 좋을 것 같습니다. 그리고 $t = 0$ 에서 각각의 함수는 $\frac{1}{\sqrt{n}} + 0i$ 을 가집니다.

함수 $F_k(x)$ 와 $x$ 의 대입값을 바탕으로 다음 행렬 방정식을 쓸 수 있습니다.

\begin{bmatrix} F_0(0) & F_1(0) & ... & F_{n-1}(0) \\ F_0(1) & F_1(1) & ... & F_{n-1}(1) \\ ... & ... & ... & ... \\ F_0(n-1) & F_1(n-1) & ... & F_{n-1}(n-1) \end{bmatrix} \begin{bmatrix} \phi_0 \\ \phi_1 \\ ... \\ \phi_{n-1} \\ \end{bmatrix} = \begin{bmatrix} s(0) \\ s(1) \\ ... \\ s(n-1) \end{bmatrix}

위 행렬 방정식을 간단히 $F_k \phi = s$ 라 쓰면 $F_k$ 는 각각의 $F_k(x)$ 함수의 평가이고 $\phi$ 는 선형결합의 계수입니다. $s(t)$ 는 동일한 시간 $t$ 에 대해 각각의 $F_k$ 함수의 선형결합의 결과를 나타내는 샘플링 함수라 할 수 있습니다. (e.g. $s(0) = \phi_0 F_0(0) + \phi_1 F_1(0) + ... + \phi_{n-1} F_{n-1}(0)$ )

행렬 방정식 $F_k \phi = s$ 를 두가지 관점에서 해석할 수 있습니다. 먼저 $F_k \phi$ 를 구함으로서 신호 $s$ 를 찾아낼 수 있습니다. 그리고 $F_k^{-1}$ 을 구함으로서 계수 $\phi$ 를 구할 수 있습니다.

앞으로 다음의 행렬을 $W(w, n)$ 로 표시합니다.

행라벨과 열라벨의 집합이 ${0, 1, ..., n-1}$ 이고
엔트리 $rc$ 는 $w^{r \cdot c}$ 입니다.

W(w, n) = \begin{bmatrix} w^{0 \cdot 0} & w^{0 \cdot 1} & w^{0 \cdot 2} & \text{ } & w^{0 \cdot (n-1)} \\ w^{1 \cdot 0} & w^{1 \cdot 1} & w^{1 \cdot 2} & ... & w^{1 \cdot (n-1)} \\ w^{2 \cdot 0} & w^{2 \cdot 1} & w^{2 \cdot 2} & \text{ } & w^{2 \cdot (n-1)} \\ ... & ... & ... & \text{ } & ... \\ w^{(n-1) \cdot 0} & w^{(n-1) \cdot 1} & w^{(n-1) \cdot 2} & \text{ } & w^{(n-1) \cdot (n-1)} \end{bmatrix}

위의 행렬을 참고하여 $F_n = \frac{1}{\sqrt{n}}W(w, n)$ 이라 쓸 수 있습니다. 이를 푸리에 행렬이라 합니다. 한편 푸리에 행렬의 역행렬은 $F_n^{-1} = \frac{1}{\sqrt{n}}W(w^{-1}, n)$ 입니다. 이는 복소 필드 상의 유니터리 행렬과 연관됩니다. 행렬-벡터 곱셈을 통해 이를 증명할 수 있습니다. 먼저 $F_n F_n^{-1}$ 의 엔트리는 행과 열의 도트곱이고 다음과 같이 표현됩니다.

\begin{aligned} w^{r \cdot 0} w^{-0 \cdot c} + w^{r \cdot 1} w^{-1 \cdot c} + w^{r \cdot 2} w^{-2 \cdot c} + ... + w^{r \cdot (n-1)} w^{-(n-1) \cdot c} \\ = w^{0(r-c)} + w^{1(r-c)} + w^{2(r-c)} + ... + w^{(n-1)(r-c)} \end{aligned}

$r = c$ 일 때 즉, $F_n F_n^{-1}$ 의 대각 엔트리는 $1 + 1 + ... 1 = n$ 입니다. $r \neq c$ 일 때 위 식은 등비수열의 합이므로 아래와 같이 표현할 수 있습니다.

\frac{w^{0(r-c)}(w^{(r-c) \cdot n} - 1)}{w^{r-c} - 1}

이 때 $w^{(r-c) \cdot n} = exp(\frac{2 \pi \cdot (r-c)}{n} \cdot n) = cos (2\pi (r-c)) + sin(2\pi (r-c))i = 1$ 이므로 등비수열의 합은 0입니다. (0은 두 벡터가 직교임을 증명합니다.) 따라서 $F_n F_n^{-1}$ 은 대각 엔트리가 $n$ 이고 나머지 엔트리는 모두 0인 행렬과 스칼라 $\frac{1}{n}$ 의 곱, 즉 단위행렬입니다.

고속 푸리에 변환 알고리즘 (FFT)

\begin{bmatrix} w^{0 \cdot 0} & w^{0 \cdot 1} & w^{0 \cdot 2} & \text{ } & w^{0 \cdot (n-1)} \\ w^{1 \cdot 0} & w^{1 \cdot 1} & w^{1 \cdot 2} & ... & w^{1 \cdot (n-1)} \\ w^{2 \cdot 0} & w^{2 \cdot 1} & w^{2 \cdot 2} & \text{ } & w^{2 \cdot (n-1)} \\ ... & ... & ... & \text{ } & ... \\ w^{(n-1) \cdot 0} & w^{(n-1) \cdot 1} & w^{(n-1) \cdot 2} & \text{ } & w^{(n-1) \cdot (n-1)} \end{bmatrix} \begin{bmatrix} \phi_0 \\ \phi_1 \\ \phi_2 \\ ... \\ \phi_{n-1} \end{bmatrix} = \begin{bmatrix} s(0) \\ s(1) \\ s(2) \\ ... \\ s(n-1) \end{bmatrix}

푸리에 행렬 $W(w, n)$ 과 계수 벡터의 행렬-벡터 곱셈은 $n^2$ 의 연산이 필요합니다. 연산을 크게 줄이는 알고리즘으로 고속 푸리에 변환 알고리즘 (FFT)이 있습니다. FFT에는 다음 두 가지 전제 조건이 있습니다.

$n$ 은 2의 거듭제곱입니다.
$w^n = 1$

FFT의 핵심은 아래와 같이 짝수번째와 홀수번째로 분할 정복하는 것입니다.

\begin{aligned} s(k) & = \phi_0 w^{k \cdot 0} + \phi_1 w^{k \cdot 1} + \phi_2 w^{k \cdot 2} + ... + \phi_{n-1} w^{k \cdot (n-1)} \\ & = \phi_0 w^{k \cdot 0} + \phi_2 w^{k \cdot 2} + ... + \phi_{n-2} w^{k \cdot (n-2)} + w^k(\phi_1 w^{k \cdot 1} + \phi_3 w^{k \cdot 3} + ... + \phi_{n-1} w^{k \cdot (n-1)}) \end{aligned}

다음과 같이 $s_{even}$ 과 $s_{odd}$ 를 정의하고 $k$ 값에 따른 식을 정리해 보겠습니다.

\begin{aligned} s_{even}(x) = s_0 + s_2 x + s_4 x^2 + ... + s_{n-2} x^{\frac{n-2}{2}} \\ s_{odd}(x) = s_1 + s_3 x + s_5 x^2 + ... + s_{n-1} x^{\frac{n-2}{2}} \end{aligned}

\begin{aligned} s(w^0) &= s_{even}(w^{0 \cdot 2}) + w^0(s_{odd}(w^{0 \cdot 2})) \\ s(w^1) &= s_{even}(w^{1 \cdot 2}) + w^1(s_{odd}(w^{1 \cdot 2})) \\ s(w^2) &= s_{even}(w^{2 \cdot 2}) + w^2(s_{odd}(w^{2 \cdot 2})) \\ & ... \\ s(w^{n-1}) &= s_{even}(w^{(n-1) \cdot 2}) + w^{n-1}(s_{odd}(w^{(n-1) \cdot 2})) \end{aligned}

FFT를 Python 코드로 옮겨 보겠습니다.

def FFT(w, s): 
    n = len(s)
    if n == 1: return s
    f0 = FFT(w*w, s[0::2])
    f1 = FFT(w*w, s[1::2])
    return [f0[j] + w**j*f1[j] for j in range(n // 2)] + \
		[f0[j] - w**j*f1[j] for j in range(n // 2)]

재귀호출을 차근차근 따라가면서 직접 도트곱의 값과 비교해 보는 것이 좋습니다. 이 때 $w^n = 1$ , $w^{\frac{n}{2}} = -1$ 인 점을 알면 계산이 쉬워집니다.

\begin{aligned} w^{\frac{n}{2}} &= -1 \\ \because exp(\frac{2\pi i}{n} \cdot \frac{n}{2}) &= exp(\pi i) = cos \pi + (sin \pi)i = -1 \end{aligned}

순환행렬

다음과 같이 다음 행이 이전 행의 오른쪽 시프트인 행렬을 순환행렬이라 합니다.

\begin{bmatrix} a_0 & a_1 & a_2 & ... & a_{n-3} & a_{n-2} & a_{n-1} \\ a_{n-1} & a_0 & a_1 & ... & a_{n-4} & a_{n-3} & a_{n-2} \\ a_{n-2} & a_{n-1} & a_0 & ... & a_{n-5} & a_{n-4} & a_{n-3} \\ \text{ } & \text{ } & \text{ } & ... & \text{ } & \text{ } & \text{ }\\ a_2 & a_3 & a_4 & ... & a_{n-1} & a_0 & a_1 \\ a_1 & a_2 & a_3 & ... & a_{n-2} & a_{n-1} & a_0 \end{bmatrix}

순환행렬을 어디에 응용할지 감 잡기가 쉽지 않습니다. 아래의 순환행렬과 푸리에 행렬 $W(w, 4)$ 의 곱을 통해 순환행렬의 흥미로운 현상을 알아보겠습니다.

\begin{bmatrix} a_0 & a_1 & a_2 & a_3 \\ a_3 & a_0 & a_1 & a_2 \\ a_2 & a_3 & a_0 & a_1 \\ a_1 & a_2 & a_3 & a_0 \end{bmatrix} \begin{bmatrix} w^{0 \cdot 0} & w^{0 \cdot 1} & w^{0 \cdot 2} & w^{0 \cdot 3} \\ w^{1 \cdot 0} & w^{1 \cdot 1} & w^{1 \cdot 2} & w^{1 \cdot 3} \\ w^{2 \cdot 0} & w^{2 \cdot 1} & w^{2 \cdot 2} & w^{2 \cdot 3} \\ w^{3 \cdot 0} & w^{3 \cdot 1} & w^{3 \cdot 2} & w^{3 \cdot 3} \end{bmatrix}

위 행렬 곱셈 중 푸리에 행렬의 첫번째 열만으로 행렬-벡터 곱셈을 살펴보겠습니다.

\begin{bmatrix} a_0 & a_1 & a_2 & a_3 \\ a_3 & a_0 & a_1 & a_2 \\ a_2 & a_3 & a_0 & a_1 \\ a_1 & a_2 & a_3 & a_0 \end{bmatrix} \begin{bmatrix} w^{0 \cdot 0} \\ w^{1 \cdot 0} \\ w^{2 \cdot 0} \\ w^{3 \cdot 0} \end{bmatrix}

순환행렬의 첫번째 행과 벡터의 곱셈은 다음과 같습니다.

a_0 w^{0 \cdot 0} + a_1 w^{1 \cdot 0} + a_2 w^{2 \cdot 0} + a_3 w^{3 \cdot 0}

순환행렬의 두번째 행과 벡터의 곱셈은 다음과 같습니다.

a_3 w^{0 \cdot 0} + a_0 w^{1 \cdot 0} + a_1 w^{2 \cdot 0} + a_2 w^{3 \cdot 0}

위 식은 첫번째식에 $w^{1 \cdot 0}$ 을 곱한것과 같습니다. ( $\because w^4 = 1$ )

마찬가지로 순환행렬의 세번째 행과 벡터의 곱셈은 첫번째 식에 $w^{2 \cdot 0}$ 을, 네번째 행과 벡터의 곱셈은 $w^{3 \cdot 0}$ 을 곱한 것과 같습니다. 따라서 $a_0 w^{0 \cdot j} + a_1 w^{1 \cdot j} + a_2 w^{2 \cdot j} + a_3 w^{3 \cdot j} = \lambda_j$ 라 할 때 다음이 성립합니다.

\lambda_j \begin{bmatrix} w^{0 \cdot j} \\ w^{1 \cdot j} \\ w^{2 \cdot j} \\ w^{3 \cdot j} \end{bmatrix} = \begin{bmatrix} a_0 & a_1 & a_2 & a_3 \\ a_3 & a_0 & a_1 & a_2 \\ a_2 & a_3 & a_0 & a_1 \\ a_1 & a_2 & a_3 & a_0 \end{bmatrix} \begin{bmatrix} w^{0 \cdot j} \\ w^{1 \cdot j} \\ w^{2 \cdot j} \\ w^{3 \cdot j} \end{bmatrix}

푸리에 행렬의 모든 열에 대해 적용하면 다음과 같습니다.

\begin{bmatrix} w^{0 \cdot 0} & w^{0 \cdot 1} & w^{0 \cdot 2} & w^{0 \cdot 3} \\ w^{1 \cdot 0} & w^{1 \cdot 1} & w^{1 \cdot 2} & w^{1 \cdot 3} \\ w^{2 \cdot 0} & w^{2 \cdot 1} & w^{2 \cdot 2} & w^{2 \cdot 3} \\ w^{3 \cdot 0} & w^{3 \cdot 1} & w^{3 \cdot 2} & w^{3 \cdot 3} \end{bmatrix} \begin{bmatrix} \lambda_0 & 0 & 0 & 0 \\ 0 & \lambda_1 & 0 & 0 \\ 0 & 0 & \lambda_2 & 0 \\ 0 & 0 & 0 & \lambda_3 \end{bmatrix} = \begin{bmatrix} a_0 & a_1 & a_2 & a_3 \\ a_3 & a_0 & a_1 & a_2 \\ a_2 & a_3 & a_0 & a_1 \\ a_1 & a_2 & a_3 & a_0 \end{bmatrix} \begin{bmatrix} w^{0 \cdot 0} & w^{0 \cdot 1} & w^{0 \cdot 2} & w^{0 \cdot 3} \\ w^{1 \cdot 0} & w^{1 \cdot 1} & w^{1 \cdot 2} & w^{1 \cdot 3} \\ w^{2 \cdot 0} & w^{2 \cdot 1} & w^{2 \cdot 2} & w^{2 \cdot 3} \\ w^{3 \cdot 0} & w^{3 \cdot 1} & w^{3 \cdot 2} & w^{3 \cdot 3} \end{bmatrix}

위 식을 간단하게 $F_4 \Lambda = A F_4$ 로 쓸 수 있고 양변에 $F_4^{-1}$ 을 곱하면 다음 두 식을 얻을 수 있습니다.

\begin{aligned} F_4 \Lambda F_4^{-1} = A \\ \Lambda = F_4^{-1} A F_4 \end{aligned}

이 방정식은 나중에 대각화에서 다루게 됩니다.

직교 행렬과 관련된 프로시저

직교행렬의 행공간에 대한 좌표 표현을 구하는 프로시저 orthogonal_vec2rep

def orthogonal_vec2rep(Q, b):
    return b * Q.transpose()

프로시저 orthogonal_vec2rep는 직교행렬 $Q$ 에 대해 $Q^TQ = I$ 라는 성질을 이용합니다.

직교행렬에 대해 기저 변경 후 좌표 표현을 구하는 프로시저 orthogonal_change_of_basis

def orthogonal_change_of_basis(A, B, a):
    v = a * A
    return B.transpose() * v

직교행렬에 대한 직교 정사영을 구하는 프로시저 orthonormal_projection_orthogonal

def orthonormal_projection_orthogonal(W, b):
    return b - W.transpose() * W * b

위 프로시저는 직교행렬의 각각의 벡터의 norm은 1임을 이용합니다.

코딩 더 매트릭스 - 11장 특수 기저 (2)

복소수 필드에 대한 내적, 푸리에 변환

2019년 02월 09일