벡터의 직교와 사영

두 벡터 $a,\ b$가 피타고라스의 정리 $\| a\|^2+\|b\|^2=\|a-b\|^2$를 만족할 때 orthogonal(직교)이라 하고 $a\perp b$라 쓴다. $\displaystyle \|a\|^2=\sum_i a_i^2=a^Ta$이므로 두 벡터가 직교할 조건은 $\displaystyle 2\sum_i a_ib_i = 0$이다. 여기에서 좌변의 $a^Tb$를 두 벡터의 dot product(점곱) 또는 scalar product라 하며 이는 inner product를 이룬다. 그렇다면 두 벡터 $a,\ b$에 대해서 비율 $a^Tb/(a^Ta)$는 $\displaystyle a^Tb-\frac{a^Tb}{a^Ta}a^Ta=0$이므로 $\displaystyle a \perp \left(b-\frac{a^Tb}{a^Ta}a\right)$를 만족시킨다. 즉 $\displaystyle \frac{a^Tb}{a^Ta}a$는 $ca$들 가운데 $b$에 가장 가까운 벡터이다. 이를 $b$의 $a$로의 projection(사영)이라 하고 $\operatorname{proj}_a b$라 쓴다. $\R^n$의 두 벡터 $a,\ b$의 사잇각 $\theta$는 $\operatorname{proj}_a b=(\|b\|\cos\theta)a$를 만족하므로 $a^Tb=\|a\|\|b\|\cos\theta$이다.

$[(a^Tb)a]_i=a_1b_1a_i+\cdots+a_nb_na_i$와 $[(aa^T)b]_i=\begin{pmatrix}a_ia_1 & a_ia_2 & \cdots & a_ia_n\end{pmatrix}b=a_ia_1b_1+\cdots+a_ia_nb_n$가 같으므로 $a$로의 projection은 outer product를 하여 벡터 $b$에 작용하는 연산자로 볼 수 있다:

$\displaystyle \frac{aa^T}{a^Ta}=\frac{1}{\|a\|^2}\begin{bmatrix} a_1a_1 & a_1a_2 & \cdots & a_1a_n \\ a_2a_1 & a_2a_2 & \cdots & a_2a_n \\ \vdots & \vdots & \ddots & \vdots \\ a_na_1 & a_na_2 & \cdots & a_na_n \end{bmatrix}$

이 행렬은 열 공간이 $ca$들이므로 rank가 $1$이다. 또한 다음이 성립한다.

• $P^T=P$이다. 따라서 행 공간과 열 공간이 같아 null space가 $a$에 직교한다.
• $P^2=P$이다. $P^2_{ij}=a_i(a^Ta)a_j/(a^Ta)=P_{ij}$로 보일 수 있다.

$P^T=P$이고 $P^2=P$인 모든 행렬은 rank가 무엇이든 $(b-Pb)^TPx=b^T(I-P)^TPx=b^T(P-P^2)x=b^TOx=0$이므로 $Pb$는 $b$의 $P$의 column space로의 projection이다. $P$를 orthogonal projection matrix(사영 행렬)라 한다.

Cauchy–Schwarz inequality

부등식 $\|b-\operatorname{proj}_a b\|^2\geq 0$은 다음과 같이 전개할 수 있다:

$\displaystyle \left\|b-\frac{a^Tb}{a^Ta}a\right\|^2=\left(b^T-\frac{a^Tb}{a^Ta}a^T\right)\left(b-\frac{a^Tb}{a^Ta}a\right)=b^Tb-2\left(\frac{a^Tb}{a^Ta}\right)(a^Tb)+\left(\frac{a^Tb}{a^Ta}\right)^2(a^Ta)=\frac{(b^Tb)(a^Ta)-(a^Tb)^2}{a^Ta}\geq 0$

이 결과 $\|a\|\|b\|\geq |a^Tb|$를 Cauchy–Schwarz inequality(코시-슈바르츠 부등식)라 한다. 확률 변수 $X,\ Y$로 나타낼 때 $\mathsf{Var}(X)\mathsf{Var}(Y)\geq \mathsf{Cov}(X,\ Y)^2$이며 $X,\ Y$의 내적을 $\mathbb{E}[XY]$라 정의할 때 $\mathbb{E}[X^2]\mathbb{E}[Y^2]\geq \mathbb{E}[XY]^2$이다.

• $\R^n$의 두 벡터의 사잇각 $\theta$에 대해서 Cauchy–Schwarz inequality는 $|\cos\theta|\leq 1$이라는 뜻이다. 부등식의 등호는 두 벡터가 평행할 때 성립한다.
• 벡터 $a=(x,\ y),\ b=(y,\ x)$에 대해서 $x^2+y^2\geq |2xy|$이다. forward–backward induction을 쓰면 산술-기하 평균 부등식을 얻는다.
• 실수 $a_1,\ a_2,\ a_3$에 대해서 $(a_1^2+a_2^2+a_3^2)(a_2^2+a_3^2+a_1^2)\geq (a_1a_2+a_2a_3+a_3a_1)^2$이므로 양의 실수 $a_1,\ a_2,\ a_3$에 대해서 $(a_1+a_2+a_3)^2\geq 3(a_1a_2+a_2a_3+a_3a_1)$이다.
• 양의 실수 $a_1,\ \cdots,\ a_n,\ b_1,\ \cdots,\ b_n$에 대해서 $\displaystyle \sum_i \frac{a_i^2}{a_i+b_i}\sum_i(a_i+b_i)\geq \left(\sum_i a_i\right)^2$이므로 $\displaystyle \sum_i a_i=\sum_i b_i$일 때 $\displaystyle \sum_i \frac{a_i^2}{a_i+b_i}\geq \frac{1}{2}\sum_{i} a_i$이다.
• 실수 $a_1,\ \cdots,\ a_n$과 양의 실수 $b_1,\ \cdots,\ b_n$에 대해서 $\displaystyle (b_1+b_2)\left(\frac{a_1^2}{b_1}+\frac{a_2^2}{b_2}\right)\geq(a_1+a_2)^2$이므로 $\displaystyle \sum_i \frac{a_i^2}{b_i}\geq \frac{\left(\sum_i a_i\right)^2}{\sum_i b_i}$이다. 따라서 $\displaystyle \frac{1}{b+c}+\frac{1}{c+a}+\frac{1}{a+b}\geq \frac{9}{2(a+b+c)}$이다.
• $X^T=X$이고 $P^T=-P$이고 양수 $c$에 대해서 $XP-PX=cI$일 때 $\|X\psi\|\|P\psi\|\geq (X\psi)^T(P\psi)=\psi^TXP\psi,\ \|P\psi\|\|X\psi\|\geq (P\psi)^T(X\psi)=-\psi^TPX\psi$이므로 $\displaystyle \|\psi\|^2=\psi^T\frac{1}{c}(XP-PX)\psi=\frac{1}{c}(\psi^TXP\psi-\psi^TPX\psi) \leq \frac{2}{c}\|X\psi\|\|P\psi\|$에서 $\displaystyle \frac{\|X\psi\|}{\|\psi\|}\frac{\|P\psi\|}{\|\psi\|}\geq \frac{c}{2}$이다. 이를 uncertainty principle(불확정성 원리)라고 한다.

전치 행렬

내적을 이용하면 다음을 만족하는 $A^T$를 행렬 $A$의 전치 행렬로 정의할 수 있다:

$\langle Ax,\ y\rangle=\langle x,\ A^Ty\rangle$

다음이 성립한다.

• $(AB)^T=B^TA^T$이다. $\langle A(Bx),\ y\rangle=\langle Bx,\ A^Ty\rangle=\langle x,\ B^T(A^Ty)\rangle$로 보일 수 있다.
• $A^T=A,\ B^T=B$이면 $(AB)^T=AB$일 때 $AB=(AB)^T=B^TA^T=BA$이고 $AB=BA$일 때 $(AB)^T=B^TA^T=BA=AB$이다.
• $(A^T)^{-1}=(A^{-1})^T$이다. $A^T(A^{-1})^T=(A^{-1}A)^T=I=(AA^{-1})^T=(A^{-1})^TA^T$로 보일 수 있다.
• $A^TAx=0$이면 $Ax=0$이다. $A^TAx=0$이면 $x^TA^TAx=0$에서 $(Ax)^TAx=\|Ax\|^2=0$으로 보일 수 있다. 이는 $A^T$의 null space와 $A$의 column space가 직교 여공간이기 때문이다. 따라서 $A$의 각 열이 독립이면 $Ax=0$일 때 $x=0$이므로 $(A^TA)^{-1}$이 존재한다. 마찬가지로 $AA^Tx=0$이면 $A^Tx=0$이고, $A$의 각 행이 독립이면 $A^Tx=0$일 때 $x=0$이므로 $(AA^T)^{-1}$이 존재한다. 이는 $Ax=b$의 해 $x$가 row space의 원소일 때 $x$를 $A$의 row들의 linear combination으로 나타내어 $AA^Tx'=b$를 만족시키는 $A^Tx'=x$로 쓰면 해 $x'$가 존재하는데, 그러한 $x'$가 유일하다는 뜻이다.
• $(A^TA)^T=A^TA$이다. $AA^T=A^TA$이면 모든 $x$에 대해서 $\|Ax\|=\|A^Tx\|$이다. $\|Ax\|^2=(Ax)^T(Ax)=x^TA^TAx,\ \|A^Tx\|^2=(A^Tx)^T(A^Tx)=x^TAA^Tx$로 보일 수 있다.

직교 행렬

$0$이 아닌 $n$개의 벡터 $v_i$가 각각 나머지 $n-1$개의 벡터와 모두 직교할 때, 벡터들의 일차 결합과 $v_i$를 내적하면 $v_i^Tv_i$ 항만 남으므로 일차 결합이 $0$인 경우는 $v_i=0$인 경우밖에 없다. 따라서 $n$개의 벡터가 서로 직교하면 linear independent이다. 직교하는 $n$개의 벡터들이 일차 결합하여 공간의 모든 벡터를 유도할 수 있을 때 orthogonal basis(직교 기저)라 하고, 각 $\|v_i\|=1$이면 orthonormal basis(정규 직교 기저)라 한다. $v_1, \cdots,\ v_n$이 정규 직교 기저이면 모든 벡터 $x$를 다음과 같이 나타낼 수 있다:

$x=v_1^Txv_1+v_2^Txv_2+\cdots+v_n^Txv_n$

정규 직교 기저의 각 벡터가 각 열을 이루는 정사각 행렬을 orthogonal matrix(직교 행렬) 또는 orthonormal matrix라 한다. 어떤 벡터들이 정규 직교라는 것은 각 원소 $v_i$가

$v_i^Tv_j=\begin{cases} 0 \quad (i\neq j)\\ 1 \quad (i=j)\end{cases}$

를 만족한다는 뜻이므로 orthogonal matrix $Q$에 대해서 $Q^TQ=I$이다. 따라서 정사각 행렬 $Q$의 각 열이 정규 직교이면 $Q^{-1}=Q^T$이므로 각 행도 정규 직교이다. $Q_1,\ Q_2$가 직교 행렬이면 $(Q_1Q_2)^{-1}=(Q_1Q_2)^T$이므로 $Q_1Q_2$도 직교 행렬이다. 또한 $|\det Q|=1$이고 $(Qa)^T(Qb)=a^Tb$이므로 함수 $Q$는 벡터의 길이, 내적, 각도를 보존시킨다. $n\times n$ 직교 행렬들은 orthogonal group(직교군) $\mathsf{O}(n)$을 이룬다. $\R^2$에서 회전 행렬들

$v_1=(\cos\theta,\ \sin\theta),\ v_2=(-\sin\theta,\ \cos\theta)$

과 permutation matrix들은 orthogonal matrix이다.

QR 분해

일차 독립인 $n$개의 벡터 $v_i$를 정규 직교인 $n$개의 벡터 $q_i$로 만들고자 하면 $q_1=v_1/\|v_1\|$에 대해서 $q_2=(v_2-q_1^Tv_2q_1)/\|v_2-q_1^Tv_2q_1\|$라 하고 또 $q_3=(v_3-q_1^Tv_3q_1-q_2^Tv_3q_2)/\|v_3-q_1^Tv_3q_1-q_2^Tv_3q_2\|,\ \cdots$와 같이 $n$단계를 반복할 수 있다. 여기에서 $q_i^Tvq_i=\|q_i\|\operatorname{proj}_{q_i} v=\operatorname{proj}_{q_i} v$이며 이렇게 각 열이 $q_i$인 행렬 $Q$를 얻는 방법을 Gram–Schmidt process(그람-슈미트 과정)라고 한다. $t_i=v_i-q_1^Tv_iq_1-\cdots-q_{i-1}^Tv_iq_{i-1}$라 할 때 $\|t_i\|q_i=t_i$에서 $\|t_i\|=q_i^Tt_i$이므로 전개하면 $\|t_i\|=q_i^Tv_i$이다. 이제 $n$개의 벡터 $v_i$를 $q_1,\ \cdots,\ q_i$들의 일차 결합으로 쓸 수 있다:

$\displaystyle v_i=q_1^Tv_iq_1+q_2^Tv_iq_2+\cdots+q_i^Tv_iq_i$

따라서 $m$개의 열들 $v_i$가 일차 독립인 $n\times m$ 행렬은 $n\times m$ 행렬과 $m\times m$ 행렬의 곱이다.

$\displaystyle \begin{bmatrix} v_1 & v_2 & \cdots & v_m\end{bmatrix}= \begin{bmatrix} q_1 & q_2 & \cdots & q_m\end{bmatrix}\begin{bmatrix} q_1^Tv_1 & q_1^Tv_2 & \cdots & q_1^Tv_m \\ 0 & q_2^Tv_2 & \cdots & q_2^Tv_m \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & q_m^Tv_m \end{bmatrix}$

이를 $A=QR$처럼 쓰며 QR decomposition(QR 분해)라고 한다. $R$은 upper triangular matrix이고 $n=m$일 때 $Q$는 orthogonal matrix이다. $\mathsf{GF}(2)$에서는 Gram–Schmidt process를 쓸 수 없다.

함수 근사

함수 공간에서 두 벡터의 내적을 두 함수의 적당한 곱의 동일한 구간에서의 적분으로 정의할 수 있다. $e^{nxi}$들은 $L^2([-\pi,\ \pi])$에서 orthonormal basis를 이루므로 Fourier series는 어떤 함수를 각 기저에 사영하여 그 합으로 근사할 수 있다. 그러나 다항식 $x^n,\ x^{n-1},\ \cdots,\ 1$들은 함수 공간에서 서로 직교하지 않으므로 예를 들어 어떤 함수를 $x^2,\ x,\ 1$에 사영하여 그 합으로 다항식 근사할 수 없다. $[0,\ 1]$에서의 적분을 내적으로 정의하여 최소 제곱법을 사용하려면 Hilbert matrix의 역행렬을 곱해야 하지만 효율적이지 못하다. $[-1,\ 1]$에서의 적분을 내적으로 정의할 때 $1$과 $x$는 직교하므로 Gram–Schmidt process를 쓰면 $\displaystyle x^2-\frac{\langle 1,\ x^2\rangle}{\langle 1,\ 1\rangle}1-\frac{\langle x,\ x^2\rangle}{\langle x,\ x\rangle}x=x^2-\frac{1}{3}$을 기저의 세 번째 벡터로 삼을 수 있다. 서로 직교하도록 차수를 따라서 이어지는 이러한 다항식들을 Legendre polynomials(르장드르 다항식)라고 한다.

직교 여공간

두 공간의 모든 벡터가 서로 직교할 때 두 공간이 직교한다고 하자. 행렬 $A$의 null space의 원소는 $Ax=0$의 모든 행과 직교하므로 $A$의 행 공간과 null space는 직교하는 두 공간이고, 마찬가지로 $A$의 열 공간과 left null space는 직교하는 두 공간이다. 식으로 나타내면 $Ax=b,\ A^Tx'=b'$가

$\displaystyle \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23}\end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3\end{bmatrix}=\begin{bmatrix} b_1 \\ b_2 \end{bmatrix},\ \begin{bmatrix} a_{11} & a_{21} \\ a_{12} & a_{22} \\ a_{13} & a_{23}\end{bmatrix} \begin{bmatrix} x'_1 \\ x'_2 \end{bmatrix}=\begin{bmatrix} b'_1 \\ b'_2 \\ b'_3 \end{bmatrix}$

일 때 $x'_1([A]_1)^T+x'_2([A]_2)^T=A^Tx'=[b']^1$이므로 $A$의 row space에 속하는 모든 열벡터 $A^Tx'$에 대해서 $A$의 null space의 원소 $x$와의 내적 $(A^Tx')^Tx=x'^TAx$는 항상 $0$이다.

$A$의 null space는 $Ax=0$의 해들을 모두 모은 것이므로 $A$의 row space의 각 원소에 직교하는 모든 벡터를 모은 것이기도 하다. 이러한 관계를 orthogonal complement(직교 여공간)라 하고, 내적 공간 $V$의 부분 공간 $W$의 직교 여공간을 $W^{\perp}$와 같이 쓴다. 행렬 $A$가 예를 들어 $A:\R^m\to \R^n$로 주어지면 $\R^m$의 모든 벡터는 $r$차원의 행 공간과 그에 직교하는 $m-r$차원의 null space로 분해할 수 있고, $\R^n$의 모든 벡터는 $r$차원의 열 공간과 그에 직교하는 $n-r$차원의 left null space로 분해할 수 있다. 따라서 $Ax=b$가 해를 가지지 않으면 $b$가 $A$의 column space에 없다는 뜻이므로 $A^Tx'=0$은 $b$와 직교하지 않는 해를 가진다.

최소 제곱법

독립인 식이 미지수보다 더 많아서 해가 없는 경우에는 오차가 가장 적은 해를 구하는 방법을 생각해 볼 수 있다. 독립인 식이 여러 개이고 미지수가 한 개일 때, 해가 존재하려면 $0=b-ax$이어야 하는데 이 조건과의 오차 $\displaystyle \sum_i (b_i-a_ix)^2$를 최소화하는 $x$는 $xa$를 $b$에 가장 가깝게 만들어야 한다. 즉 그러한 해는 $\hat{x}=a^Tb/(a^Ta)$이다. $a$가 영벡터이면 $\hat{x}$를 정할 수 없지만 pseudoinverse는 $0^T=0$이다.

이러한 least squares 방법을 미지수가 여러 개일 때로 일반화하려면 $A$의 열 공간에 속하는 점 $Ax$들 가운데 $b$에 가장 가까운, 즉 오차 $\|b-Ax\|$를 최소화하는 벡터 $\hat{x}$를 찾아야 한다. $n$차원에서의 직교와 사영을 정의했기 때문에 직관을 따라서, 그러한 $\hat{x}$가 $b-A\hat{x}$를 $A$의 열 공간에 수직으로 만든다고 생각할 수 있다. 따라서 $b-A\hat{x}$는 $A$의 left null space에 속하고 $A^T(b-A\hat{x})=0$이다. 이를 normal equations(정규 방정식) 또는 ordinary least squares라고 한다. 여기에서 $\hat{x}=(A^TA)^{-1}A^Tb$을 얻는다. 따라서 $b$의, $A$의 column space $Ax$로의 projection은 $A(A^TA)^{-1}A^Tb$이다.

• $\|b^T-x^TA^T\|$를 최소화하는 벡터 $x^T$는 $b^T-x^TA^T$가 $(b^T-x^TA^T)A=0$을 만족시킨다. 따라서 $x^T=b^TA(A^TA)^{-1}$이다.
• $\|b-A^Tx\|$를 최소화하는 벡터 $x$는 $b-A^Tx$가 $A(b-A^Tx)=0$을 만족시킨다. 따라서 $x=(AA^T)^{-1}Ab$이다.
• $\|b^T-x^TA\|$를 최소화하는 벡터 $x^T$는 $b^T-x^TA$가 $(b^T-x^TA)A^T=0$을 만족시킨다. 따라서 $x^T=b^TA^T(AA^T)^{-1}$이다.
• $A=QR$로 분해할 수 있으면 $A^TA=R^TR$이므로 $\|b-Ax\|$를 최소화하는 벡터는 $\hat{x}=R^{-1}Q^Tb$이다.

$A(A^TA)^{-1}A^T$는 projection matrix이다. $A$의 열들이 정규 직교이면 이는 $AA^T$이며, $A$가 정사각 행렬이 아닐 때 $I$가 아니다.

overdetermined system

$n$개의 직선 $y=a_ix+b_i$이 만나는 점 $(x,\ y)$를 구하는 연립일차방정식은

$\displaystyle \begin{bmatrix} 1 & -a_1 \\ \vdots & \vdots \\ 1 & -a_n\end{bmatrix} \begin{bmatrix} y \\ x \end{bmatrix}=\begin{bmatrix} b_1 \\ \vdots \\ b_n \end{bmatrix}$

이다. 여기에 least squares를 쓰면 $b_i-(y-a_ix)$의 제곱의 합을 최소화하는 점 $(\hat{x},\ \hat{y})$를 구할 수 있다. $a$축과 $b$축으로 이루어진 좌표 평면을 생각하였을 때 이 해는 $b=\hat{x}a+\hat{y}$ 위의 점 $(a_i,\ \hat{x}a_i+\hat{y})$에서, 점 $(a_i,\ b_i)$까지의 거리들에 대해서 제곱의 합을 최소화한다. 따라서 직선 $y=\hat{x}x+\hat{y}$는 평면 위의 $n$개의 점 $(a_i,\ b_i)$들의 분포를 설명하는 직선으로 쓸 수도 있다.

weighted least squares

더 좋은 데이터를 더 중요하게 다루고 싶을 때에는 각 $b_i$에 가중치 $w_i^2$를 부여하여 오차 $\displaystyle \sum_i w_i^2(b_i-x)^2$를 최소화하는 weighted average를 쓸 수 있다. 가중치를 부여하는 행렬 $W$를 곱하여 $WAx=Wb$에 least squares를 쓰면 $\hat{x}=(A^TW^TWA)^{-1}A^TW^TWb$이다. 여기에서 두 벡터 $x,\ y$의 내적을 $y^TW^TWx$라 정의할 때 $\hat{x}$가 $b-A\hat{x}$를 $A$의 열 공간에 수직으로 만든다. 즉 $W$가 직교 행렬이면 내적은 변하지 않는다. $W^TW$로 적당한 것은 covariance matrix의 역행렬이다.

유사 역행렬

$n\times m$ 행렬과 $m\times r$ 행렬을 곱하면 $n\times r$ 행렬이므로 $A$가 $n\times m$ 행렬일 때 right inverse는 $AA^{-1}=I_{n\times n}$이고 left inverse는 $A^{-1}A=I_{m\times m}$이다. right inverse $A^{-1}$에 대해서 $A^{-1}A$는 $m$차원 벡터를 $A$의 row space로 project하고, left inverse $A^{-1}$에 대해서 $AA^{-1}$는 $n$차원 벡터를 $A$의 column space로 project한다. 최소 제곱법에서 $x$에 $A^{-1}b$를 넣어 계산하면 right inverse $A^T(AA^T)^{-1}$와 left inverse $(A^TA)^{-1}A^T$를 얻을 수 있다. 이는 Frobenius norm에 대해서 $\|I-AX\|$를 최소화한다.

$A^{-1}$이 pseudoinverse이면 $m\times n$ 행렬 $C$에 대해서 $A^{-1}+(I_m-A^{-1}A)C+(I_n-AA^{-1})C$도 pseudoinverse이다. 이들 중에 $AA^{-1}A=A,\ A^{-1}AA^{-1}=A^{-1}$이면서 $AA^{-1},\ A^{-1}A$가 대칭 행렬인 유일한 pseudoinverse를 Moore–Penrose inverse라 한다.

이산 푸리에 변환

주기가 $2\pi$인 함수 $f$의 푸리에 급수 $\displaystyle f(x)=\sum_{n\in\Z} c_ne^{nxi}$는 시간 $x$에 대해서 진폭 $f(x)$를 주파수 $n$에 대응하는 함수 $e^{nxi}$로의 사영들의 합으로 근사한 것이다. 각 사영의 계수는 $\displaystyle c_n=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(x)e^{-nxi} dx$이다. 주기를 없애면 $\displaystyle f(x)=\int_{-\infty}^{\infty} c_{\xi}e^{2\pi\xi xi}d\xi$는 시간 $x$에 대해서 진폭 $f(x)$를 연속적인 주파수 $\xi$에 대응하는 함수 $e^{2\pi\xi xi}$로의 사영들의 적분으로 근사한 것이다. 각 사영의 계수는 $\displaystyle c_{\xi}=\int_{-\infty}^{\infty} f(x)e^{-2\pi\xi xi}dx$이다. time domain을 쓰는 $f(x)$에서 frequency domain을 쓰는 새로운 함수 $\hat{f}(\xi)=c_\xi$를 얻는 변환을 Fourier transform이라고 한다.

유한 개의 $f(0),\ f(1),\ \cdots,\ f(n-1)$로부터 이산적인 해 $\hat{f}(0),\ \hat{f}(1),\ \cdots,\ \hat{f}(n-1)$를 구하기 위해서 discrete Fourier transform과 inverse transform을 $\displaystyle f(a)=\frac{1}{n}\sum_{b} \hat{f}(b)e^{2\pi bai/n}$와 $\displaystyle \hat{f}(b)=\sum_{a} f(a)e^{-2\pi bai/n}$로 정의할 수 있다. 행렬로 쓰면 다음과 같다:

$\displaystyle \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & e^{2\pi i/n} & e^{2\pi 2i/n} & \cdots & e^{2\pi (n-1)i/n} \\ 1 & e^{2\pi 2i/n} & e^{2\pi 4i/n} & \cdots & e^{2\pi (n-1)2i/n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & e^{2\pi (n-1)i/n} & e^{2\pi 2(n-1)i/n} & \cdots & e^{2\pi (n-1)(n-1)i/n} \end{bmatrix} \begin{bmatrix} \hat{f}(0) \\ \hat{f}(1) \\ \hat{f}(2) \\ \vdots \\ \hat{f}(n-1)\end{bmatrix}=\begin{bmatrix} nf(0) \\ nf(1) \\ nf(2) \\ \vdots \\ nf(n-1) \end{bmatrix}$

$x^n=1$의 해는 $\displaystyle e^{2\pi i/n}=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n}$의 거듭제곱들이다. Vieta's formulas에 따라서 이들의 합은 $0$이다. 그러므로 Fourier transform 행렬과 inverse transform 행렬을 곱하면 대각 성분이 아닌 것들은 $1+e^{2\pi ki/n}+e^{2\pi2ki/n}+\cdots+e^{2\pi(n-1)ki/n}=0$이다. 복소 내적에 대해서 Fourier transform 행렬의 column들은 서로 직교한다.

빠른 푸리에 변환

$n\times n$ Fourier transform 행렬 $A$에 대해서 $Ax=b$를 $n/2\times n/2$ Fourier transform 행렬 $A_{n/2}$에 대해서 $A_{n/2}x_{\mathrm{even}}=b_{\mathrm{even}}$와 $A_{n/2}x_{\mathrm{odd}}=b_{\mathrm{odd}}$로부터 계산할 수 있으면 연산 비용을 $n^2$에서 $\displaystyle \frac{n}{2}\log_2 n$으로 줄일 수 있다. 여기에서 $x_{\mathrm{even}}$는 각 성분이 $\hat{f}(0),\ \hat{f}(2),\ \cdots,\ \hat{f}(n-2)$인 벡터이다.

$\displaystyle \begin{split} nf(a)=\sum_{b} \hat{f}(b) e^{2\pi bai/n}&=\sum_{b<n/2} \hat{f}(2b)e^{2\pi 2bai/n}+\sum_{b<n/2} \hat{f}(2b+1)e^{2\pi (2b+1)ai/n} \\ &= \sum_{b<n/2} (x_{\mathrm{even}})_be^{2\pi bai/(n/2)}+e^{2\pi ai/n}\sum_{b<n/2} (x_{\mathrm{odd}})_be^{2\pi bai/(n/2)} \\ &= b_{\mathrm{even}}+e^{2\pi ai/n}b_{\mathrm{odd}}\end{split}$

$nf(a)$는 $b_{\mathrm{even}}+e^{2\pi ai/n}b_{\mathrm{odd}}$이고 $nf(a+n/2)$는 $b_{\mathrm{even}}-e^{2\pi ai/n}b_{\mathrm{odd}}$이다. 이 radix-2 fast Fourier transform, FFT를 이용하여 Cooley–Tukey algorithm을 구현할 수 있다. $n=4$일 때

$\displaystyle \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix}\begin{bmatrix} \hat{f}(0) \\ \hat{f}(1) \\ \hat{f}(2) \\ \hat{f}(3)\end{bmatrix}=\begin{bmatrix} 1 & 1 & 1\times 1 & 1\times 1 \\ 1 & -1 & i\times 1 & i\times -1 \\ 1 & 1 & -1\times 1 & -1\times 1 \\ 1 & -1 & -i\times 1 & -i\times -1 \end{bmatrix}\begin{bmatrix} \hat{f}(0) \\ \hat{f}(2) \\ \hat{f}(1) \\ \hat{f}(3)\end{bmatrix}=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & i \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -i \end{bmatrix}\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 \end{bmatrix}\begin{bmatrix} \hat{f}(0) \\ \hat{f}(2) \\ \hat{f}(1) \\ \hat{f}(3)\end{bmatrix}$

이고 $\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$은 $2\times 2$ Fourier transform 행렬이다. 순서를 바꾼 각 $\hat{f}(b)$에 두 번째 행렬 $A_{n/2}$가 작용하고 첫 번째 행렬이 $b_{\mathrm{even}}+e^{2\pi ai/n}b_{\mathrm{odd}}$를 대응시킨다. $n/2\times n/2$ 행렬로 이어지는 각 단계에서 $e^{2\pi ai/n}b_{\mathrm{odd}}$의 연산 비용은 $n/2$이 된다.

참고 자료

• Gilbert Strang. Linear Algebra and Its Applications.