Introduction
이번에 선형대수를 공부하면서 내용을 정리해보았습니다.
강의 영상 : https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/
Video Lectures | Linear Algebra | Mathematics | MIT OpenCourseWare
This section contains a complete set of video lectures on linear algebra along with transcripts and related resource files.
ocw.mit.edu
스터디 github : https://github.com/jwkweon/study-linear-algebra
GitHub - jwkweon/study-linear-algebra
Contribute to jwkweon/study-linear-algebra development by creating an account on GitHub.
github.com
참고한 블로그 :
Lecture 26: Complex matrices; fast fourier transformation
본 내용은 https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/le...
blog.naver.com
복소 행렬(Complex Matrix)
행렬이 실수 행렬이라도 고유값과 고유벡터가 복소수가 될 수 있다. 또 벡터나 행렬이 복소수일수도 있다.
만약, 2개의 복소수의 내적등이 있을 때 무엇이 발생할까?
복소수 행렬의 가장 중요한 예제는 푸리에 행렬(Fourier matrix)이다.
푸리에 행렬은 복소수 행렬이다. 그리고 푸리에 변환(Fourier transform)에서 필요한 행렬이다.
그리고 이번 강의에서 다루고자 하는 것은 FFT 즉, Fast Fourier Transform인데 말그대로 푸리에 변환을 빠르게 적용할 수 있다.
그러면, nxn의 푸리에 행렬을 어떻게 빠르게 곱할 수 있을까?
일반적인 경우에 nxn의 행렬 곱은 $n^2$의 곱셈이 된다. 이런 경우는 full matrix이면서, orthogonal column을 가진 행렬이다. best matrix일 때를 말한다.
FFT의 아이디어는 $n^2$의 곱셈을 감소시키는 것이다. 즉, 계산량을 $n \log_2 n$으로 줄여준다.
먼저, 복소수 벡터와 행렬에 대해서 다뤄보자.
다음과 같은 복소수 벡터 z가 있다고 해보자. 벡터 z의 성분은 z1, z2, ..., zn은 전부 복소수이다.
$$ z = \begin{bmatrix} z_1 \\ z_2 \\ \vdots \\ z_n \end{bmatrix}$$
복소수 벡터 z는 n차원 실수공간인 $R^n$에 존재하는게 아니라 n차원 복소공간(Complex space)인 $C^n$에 존재한다.
여기서, 요점은 복소벡터의 길이에 대한 포인트 $z^T z$가 좋지 않다는 것이다.
$$ {\rm length} \ \ z^T z \ \ {\rm no \ \ good} $$
$$ z^T z = \begin{bmatrix} z_1 & z_2 & \cdots & z_n \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ \vdots \\ z_n \end{bmatrix} $$
왜냐하면, 길이 제곱은 양수여야하기 때문이다. 아래 예시를 봐보자.
$$ z^T z = \begin{bmatrix} 1 & i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 1^2 + i^2 = 1 - 1 = 0$$
벡터의 길이는 0이면 안된다. 또, i가 2i라면 음수가 된다.
따라서, 우리가 원하는건 켤레복소수와의 곱 $\bar{z}^T z $이 되야한다. 왜냐하면, $\bar{z}_1 z_1 = |z_1|^2 $으로 항상 양수이기 때문이다.
$$ {\rm length} \ \ \bar{z}^T z \ \ {\rm is \ \ good} $$
$$ \bar{z}^T z = \begin{bmatrix} \bar{z}_1 & \bar{z}_2 & \cdots & \bar{z}_n \end{bmatrix} \begin{bmatrix} z_1 \\ z_2 \\ \vdots \\ z_n \end{bmatrix} $$
아래 예시를 봐보자.
$$ \bar{z}^T z = \begin{bmatrix} 1 & -i \end{bmatrix} \begin{bmatrix} 1 \\ i \end{bmatrix} = 1^2 + (-i)*(i) = 1 + 1 = 2$$
요점은 올바른 정의로 가려면 우리가 복소벡터를 전치할때마다 켤레복소수를 사용해야한다는 것이다.
그래서 새로운 기호를 정의한다. 전치와 켤레화를 동시에 하는 기호로 H(Hermitian)(에르미트)라고 부른다.
$$ \bar{z}^T z = z^H z $$
그리고 위와 같은 식은 길이의 제곱이 된다.
그러면 복소벡터의 내적은 무엇이 될까?
더이상 $y^T x $와 같은 내적은 사용할 수 없다. 이것은 실수 벡터에 대한 내적이다.
복소벡터의 내적도 마찬가지로 전치를 하고 켤레화를 해야한다.
$$ \bar{y}^T x = y^H x $$
복소벡터에 대한 내적은 더이상 실수가 되지 않는다.
여기서, y와 x가 동일하다면, $z^H z$가 되고 길이의 제곱을 갖게 된다.
$$ z^H z = |z_1|^2 + |z_2|^2 + \cdots + |z_n|^2 $$
이번에는 대칭행렬(Symmetric matrix)의 아이디어를 변경해야한다.
$$ A^T = A $$
이것은 실수행렬에 적용하는 특성이다. 만일, 행렬 A가 복소수일 경우에는 좋지 않게 된다.
$$ A^T = A \ \ {\rm no \ \ good} $$
행렬이 복소수일 때, 전치를 시키고 싶을거고 켤레화를 이용할 것이다. 전치를 시킨 후에도 원래 행렬과 같기 위해서 이다.
$$ \bar{A}^T = A \ \ {\rm is \ \ good} $$
이것이 대칭행렬에 대한 올바른 복소수 버전이 된다.
복소행렬에서의 대칭성을 확인하기 위해서는 대각선을 기준으로 전치를 시키고 켤레를 취한게 원래 행렬과 같아야 한다.
그리고, 이렇게 복소행렬에서의 대칭성을 만족하는 행렬을 에르미트행렬(Hermitian matrix)라고 부른다.
$$ \bar{A}^T = A \quad \longrightarrow \quad A^H = A $$
다음 에르미트행렬 예시를 봐보자.
$$ A = \begin{bmatrix} 2 & 3+i \\ 3-i & 5 \end{bmatrix} = A^H $$
여기서, 에르미트행렬의 대각성분은 반드시 실수여야한다. 왜냐하면, 대각성분은 전치를 하면 그대로 있기 때문이다.
만일, 대각성분이 복소수라면 전치를 한 후 켤레를 하면 바뀌기 때문이다
에르미트 행렬은 고유값으로 실수를 가지고 있고, 서로 수직인 고유벡터를 가지고 있다.
수직은 무슨 의미일까?
예를들어 다음과 같이 서로 수직인 단위벡터 q1, q2, ..., qn이 있다고해보자. 이것들은 orthonormal basis가 된다.
벡터들이 서로 수직임을 체크하기 위해서는 내적을 해야하고 이제는 내적을 위해 전치를 시킬 때 켤레화도 해야한다.
위 벡터들이 서로 수직이라 서로 다른 벡터를 내적하면 0이 될 것이고 서로 같은 벡터를 내적하면 1이 될 것이다.
$$ \bar{q}_i^T q_j = q_i^H q_j = \begin{cases} 0 & i \ne j \\ 1 & i = j \end{cases}$$
그리고 수직(orthogonal)은 모든 각도가 90도임을 의미하느데, 복소수 n차원 공간내에서의 각도가 된다.
이번에는 위의 벡터들을 서로 내적시키기 위해 column으로 사용하는 행렬 Q를 만들어보자.
$$ Q = \begin{bmatrix} | & | & & | \\ q_1 & q_2 & \cdots & q_n \\ | & | & & | \end{bmatrix} $$
$$ Q^T Q = I $$
행렬 Q는 직교행렬(Orthogonal matix)이다.
우리는 $C^n$이라는 복소벡터 스페이스를 다루고 있다.
따라서, 내적할 때 켤레화를 한다음 내적을 해야한다.
$$ Q^H Q = I$$
그리고 이러한 특성을 만족하는 행렬을 유니터리행렬(Unitary matrix)이라 부른다.
유니터리행렬은 일종의 orthonormal matrix와 같다. 정사각 형태이고, nxn 행렬이고, 각각의 column들은 orthonormal columns이고, 서로 수직인 perpendicular columns이고, 단위벡터가 된다.
그리고 이러한 orthogonal columns을 가지는 유니터리 행렬의 이름에는 Fourier가 붙는다.
푸리에 행렬(Fourier Matrix)
푸리에 행렬은 유니터리 행렬이며, column 벡터들이 정규직교(orthonormal)하다.
다음 행렬은 nxn 푸리에 행렬이다.
$$ F_n = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & W & W^2 & \cdots & W^{n-1} \\ 1 & W^2 & W^4 & \cdots & W^{2(n-1)} \\ \vdots & & & & \\ 1 & W^{n-1} & W^{2(n-1)} & \cdots & W^{(n-1)^2} \end{bmatrix} $$
푸리에 행렬을 보면 대칭행렬처럼 보인다. 하지만 W가 복소수이기 때문에 이전에 알던 그런 대칭행렬은 아니다.
그리고 여기서는 첫번째 column의 index는 0을 사용할 것이다. 따라서, 마지막 column의 index는 n-1이 된다.
index를 살펴보면, i와 j가 0에서 n-1로 가는것을 알 수 있다.
$$ (F_n)_{ij} = W^{ij} $$
$$ i, \ j = 0, \ 1 , \ \cdots , \ n-1 $$
푸리에 행렬은 0이 하나도 없다. 즉, Full matrix이다.
그리고 W는 매우 특별한 숫자인데 이것은 n번째 거듭제곱이 1이 되는 숫자이다.
$$ W^n = 1 $$
여기서, W의 각도는 $ \frac{2 \pi}{n} $이 된다. (왜냐하면, 신호를 n개의 등간격 주파수 성분으로 분해하기 위해서)
따라서, W는 다음과 같이 되야한다.
$$ W = e^{i \frac{2 \pi}{n}} = \cos{\frac{2 \pi}{n}} + i \sin{\frac{2 \pi}{n}}$$
그리고 W는 복소수 평면에서 단위원 위에 있고, n이 커질수록 W는 단위원 위를 돌게 된다.
만약, n이 6이라면 W는 원의 $\frac{1}{6}$의 위치에 있을 것이고 각도로는 360/6=60도가 될 것이다.
$$ W = e^{i \frac{2 \pi}{6}} = e^ { i \frac{\pi}{3}} $$
$W^2$은 어디에 있을까?
$$ W^2 = e^{2 i \frac{2 \pi}{6}} = e^{ i \frac{2 \pi}{3}}$$
따라서, 단위원 상에서 120도에 위치하게 될 것이다.
$W^3$은 당연히 180도, $W^4$은 240도, $W^5$은 300도, $W^6$은 360도에 위치하게 되는데
$W^6$은 실수 성분만있는 1이 된다.
따라서, 거듭제곱할수록 다음과 같은 순서가 계속해서 반복되고, 6개의 점을 찍으면서 원을 계속 돌게 된다.
$$ 1 \rightarrow W \rightarrow W^2 \rightarrow W^3 \rightarrow W^4 \rightarrow W^5 \rightarrow W^6 = 1 \rightarrow W^7 = W \rightarrow W^8 = W^2 \rightarrow \cdots $$
이번에는 n=4로 바꿔보자.
$$ W = e^{i \frac{2 \pi}{4}} = e^ { i \frac{\pi}{2}} $$
W는 단위원의 $\frac{1}{4}$이 된다. 그리고 W는 정확히 i가 된다.
$$ W = e^{i \frac{2 \pi}{4}} = \cos{\frac{2 \pi}{4}} + i \sin{\frac{2 \pi}{4}} = \cos{\frac{\pi}{2}} + i \sin{\frac{\pi}{2}} = 0 + i = i $$
따라서, W의 거듭제곱은 i의 거듭제곱이므로 다음과 같이 된다.
$$ W = i $$
$$ W^2 = i^2 = -1 $$
$$ W^3 = i^3 = -i $$
$$ W^4 = i^4 = 1 $$
이제, 4x4 케이스에 대한 푸레이 행렬을 작성할 준비가 됬다.
$$ F_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & i^2 & i^3 \\ 1 & i^2 & i^4 & i^6 \\ 1 & i^3 & i^6 & i^9 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix}$$
이 행렬은 4x4행렬로 4개의 점을 가진 푸리에 변환(four point Fourier transform)에 나온다.
따라서, 우리가 4개의 성분을 가진 벡터에 대해서 푸리에 변환을 한다면 $F_4$ 푸리에 행렬을 바로 곱하거나 이것의 역행렬을 곱할 수 있다. (나중에 배움)
푸리에 행렬의 역행렬도 굉장히 좋은 행렬이 된다.
푸리에 행렬은 직교행렬이기 때문에 역행렬이 전치행렬과 같아 쉽게 역행렬을 찾을 수 있다.
그러면 column들이 정말 직교하는지 $F_4$행렬의 column 벡터들을 내적을 통해 확인해보자.
이때, 복소수 벡터들의 내적은 전치후 켤레화를 하는 것을 잊지말자.
두번째 column과 네번째 column을 내적해보자.
$$ \begin{bmatrix} 1 & -i & -1 & i \end{bmatrix} \begin{bmatrix} 1 \\ -i \\ -1 \\ i \end{bmatrix} = 1 -1 + 1 - 1 = 0 $$
따라서, column들이 서로 직교함을 알 수 있다.
그러나 완전히 orthogonormal하지는 않다. 왜냐하면, column 벡터 크기가 1이 아니기 때문인데, 쉽게 고칠 수 있다.
첫번째 column의 크기가 2가되므로 행렬을 2로 나눠주면된다.
$$ F_4 = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & i^2 & i^3 \\ 1 & i^2 & i^4 & i^6 \\ 1 & i^3 & i^6 & i^9 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix}$$
$F_4$는 유니터리행렬이 되고 다음 특성을 만족한다.
$$ F_4^H F^4 = I$$
따라서, $F_4$의 역행렬은 전치를 시킨후 켤레화를하면 쉽게 찾을 수 있다.
FFT(Fast Fourier Transform)
먼저 말하면 F6과 F3은 연결되어 있다. F8과 F4도 연결되어 있고, F64와 F32도 연결되어있다.
그렇다면 F64와 F32에는 어떤 연결이 있을까?
F64는 64x64행렬이고 F32는 32x32행렬이다. 두 행렬의 크기는 서로 다르다.
여기서 64x64의 W를 제곱하면 어떻게 될까?
$$ (W_{64})^2 = W_{32} $$
즉, 64x64의 W를 제곱하면 32x32의 W가 된다.
왜냐하면, 64x64의 W는 단위원에서 $\frac{1}{64}$지점에 있고 32x32의 W는 단위원에서 $\frac{1}{32}$지점에 있게 된다.
따라서, 64x64의 W를 제곱하면 각도가 2배가 되고 따라서, 32x32의 W와 같아지게 된다.
그러면, F64와 F32를 어떻게 연결할 수 있을까?
F64는 64x64행렬인데, F32의 2개의 복사본과 연결된다.
$$ \begin{bmatrix} & & \\ & F_{64} & \\ & & \end{bmatrix} \rightarrow \begin{bmatrix} F_{32} & {\rm zero \ \ matrix} \\ {\rm zero \\ matrix} & F_{32} \end{bmatrix} $$
위의 행렬은 둘다 64x64의 행렬이다. 하지만, 완전히 같은 것은 아닌 상태고 약간의 수정을 해야 등호를 쓸 수 있다.
여기서, zero matrix가 핵심인데, 만일, F64로 어떤 벡터와 계산을 하면 $64^2$만큼의 곱셈이 존재한다.
F32 2개를 이용한다면, $ 2 * 32^2$만큼의 곱셈이 존재하게된다.
이제 완전히 두 행렬을 완전히 같게 해보자.
먼저, 치환행렬 P가 오른쪽에 붙게 된다. 매우 단순한 odds and even 치환행렬이 된다.
$$ \begin{bmatrix} & & \\ & F_{64} & \\ & & \end{bmatrix} \rightarrow \begin{bmatrix} F_{32} & {\rm zero \ \ matrix} \\ {\rm zero \ \ matrix} & F_{32} \end{bmatrix} \underset{P}{\begin{bmatrix} 1 & & & & & & & \\ & & 1 & & & & &\\ & & & & 1 & & & \\ & & & & & & 1 & \\ & 1 & & & & & & \\ & & & 1 & & & & \\ & & & & & 1 & & \\ & & & & & & & 1 \end{bmatrix}}$$
치환행렬을 실제로 정확하게 만들면 더 많은 1이 존재할 것이고 일단은 대충 저런 형태가 반복된다.
치환행렬 P의 역할은 어떤 벡터의 짝수 성분을 먼저 앞으로 보내고 그다음은 홀수 성분이 나오게 만드는 역할이다.
아마, 벡터의 $x_0$, $x_2$, $x_4$, $x_6$, ...을 골라내고, 밑으로 $x_1$, $x_3$, $x_5$, $x_7$을 골라낼 것이다.
64x64의 푸리에 행렬이 몇개로 분리가 되는데 벡터를 짝수 성분과 홀수 성분으로 나눈 다음 32 크기의 푸리에 변환을 개별적으로 수행하고, 이것을 다시 모으는 작업을 한다.
이렇게 함께 모은 것들은 단위행렬 I로 판명하고, 그리고 대각행렬 D가 필요하고, 또 I, -대각행렬 D가 필요하다.
$$ \begin{bmatrix} & & \\ & F_{64} & \\ & & \end{bmatrix} = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{32} & {\rm zero \ \ matrix} \\ {\rm zero \ \ matrix} & F_{32} \end{bmatrix} \underset{P}{\begin{bmatrix} 1 & & & & & & & \\ & & 1 & & & & &\\ & & & & 1 & & & \\ & & & & & & 1 & \\ & 1 & & & & & & \\ & & & 1 & & & & \\ & & & & & 1 & & \\ & & & & & & & 1 \end{bmatrix}}$$
이제 등호를 붙일 수 있게되고, F32, I, D, zero matrix는 32x32행렬, P는 64x64행렬이 된다.
근본적으로 단위행렬 I나 치환행렬 P에서 연산하는 비용은 발생하지 않고, D가 대각행렬이기 때문에 fix-up 비용은 근본적으로 32개의 곱셈이 된다.
그리고 대각행렬 D는 W의 지수승으로 구성되는데 $(1, \ W, \ W^2, \ \cdots , \ W^{n-1} )$로 구성된다.
따라서, 32x32의 대각행렬 D는 다음과 같다.
$$ D = \begin{bmatrix} 1 & & & & \\ & W & & & \\ & & W^2 & & \\ & & & \ddots & \\ & & & & W^{31} \end{bmatrix}$$
그러면 실제 계산량을 검토해보자.
이전에 F64는 $64^2$번 계산한다.
F32를 이용하면 먼저, F32를 2번 계산하는데 이때, 짝수 성분과 홀수 성분에 대해서 개별적으로 적용하여 계산한다.
여기까지 총 $2 * (32)^2 $ 계산하고 대각행렬 D에 대해서는 대각성분만 계산하면 되므로 32번만 계산하게 된다.
따라서, 계산비용은 $2 *(32)^2 + 32$로 줄어들게 된다.
여기서 다음 아이디어를 얻을 수 있다. F32를 더 작게 나누는 것이다.
F32를 F16 2개로 나눌 수 있있고 이렇게 되면 치환행렬 P의 크기는 32x32가 된다.
이런식으로 재귀적(recursive)으로 사용할 수 있다.
아마, 치환행렬을 두번쓰게 될텐데 처음 치환행렬에서는 짝수성분끼리 나누고 홀수성분끼리 나눈다.
그다음 쓰는 치환행렬에서는 짝수성분의 짝수성분과 홀수성분을 또 나누고, 또 홀수성분의 짝수성분과 홀수성분으로 나눌 것이다.
짝수성분이 (0, 2, 4, 6, 8, 10, 12, 14)이 있다면 짝수성분의 짝수성분은 (0, 4, 8, 12)이고 짝수성분의 홀수성분은 (2, 6, 10, 14)로 나눈다는뜻이다.
결국, 계산비용은 $ 2 * [ 2(16)^2 + 16] +32 $로 줄어들게 된다.
이런식으로 재귀적으로 계속가다보면 F8, F4, F2, F1까지 내려갈 것이고 전부 6단계가 생긴다.
그리고, 6개의 fix-up factor를 갖는데, 최종적으로 계산비용은 $6*32$가 될 것이다.
결국, 계산비용은 $64^2$에서 $6 *32$로 바뀌고, $\log_2 64 = 6$, $\frac{64}{2} = 32 $가 된다.
따라서, 계산량은 다음과 같이 된다.
$$ \frac{1}{2} n \log_2 n $$
예를들어 $n= 1024 = 2^{10}$ 이라 해보자.
원래라면 $1024^2 = 1024*1024$번의 계산을 해야한다.
그러나 FFT를 사용한다면, $ 1024 * 5 $번의 계산만 하면된다.
약 200배 계산을 절약할 수 있다.
