Korean
English
지난 글에서는 내적과 거리를 Hilbert 공간으로 확장해보았습니다. 이번 글에서는 bases, subspace, projection에 대해 다루고 Parseval's identity나 Bessel's inequality와 같이 orthonormal bases들이 갖는 유용한 특성을 살펴볼 것입니다. 한가지 재미있는 점은 이 두 특성이 이름은 다 다르지만 사실은 우리가 잘 알고 있는 유클리드 공간에서의 피타고라스 정리가 일반화 된 형태일 따름이라는 것이죠.
Subspaces and Bases
어떤 공간에 대한 구조를 엿보려면 그 뼈대를 알아야합니다. 벡터 공간에서 이런 뼈대에 해당하는 것이 바로 basis인데요. 우리가 흔히 생각하는 뼈대와는 다르게 이런 수학적 공간에서의 뼈대는 상당히 유연해서, 공간을 망가뜨리지 않고 늘리거나 휘거나 돌리는 등의 변형이 가능합니다. 이를 선형 변환(linear transformation)이라고도 하죠.
이렇게 유연한 성질을 바탕으로, 기존 공간의 성질들을 망가뜨리지 않는 선에서 뼈대를 맘대로 바꾸는 것을 "change of basis"라고 합니다. 이렇게 뼈대를 바꾸는 까닭은 보통 현재의 구조로는 살펴보기가 힘든 정보가 있어서, 이를 좀 더 쉽게 살펴볼 수 있도록 시점을 바꾸기 위해서 입니다. 예를 들면 앞선 글에서 말했었듯 차후 배울 Fourier transform 역시도 대표적인 change of basis 중 하나입니다.
그리고 간혹 벡터 공간 전체가 아닌 좀 더 한정된 공간을 깊게 분석하기 위해 공간의 일부분만을 떼어서 살펴볼 때가 있습니다. 이를 subspace라고 부르는데요. Subspace는 벡터 공간 안에서 허용되는 operation들에 대해 닫혀있는 공간이기 때문에, 마치 샌드박스처럼 해당 공간을 벗어나지 않으면서도 하고 싶은 분석을 할 수 있게 됩니다. 당연하지만 subspace도 공간이기 때문에 자기 자신만의 뼈대를 가지고 있습니다.
그럼 Projection으로 넘어가기 전에 각각의 개념에 대해 좀 더 엄밀히 정의하고 넘어가겠습니다. 먼저 $H(V,S)$는 Hilbert 공간으로 여기서 $V$와 $S$는 각각 벡터 공간과 스칼라 집합입니다.
Subspace.
$V$에 대한 subspace는 다음과 같은 성질을 만족하는 부분 집합 $P\subseteq V$를 말합니다:
$$\mathbf{x} \in P \text{ and } \mathbf{y}\in P \Rightarrow \mathbf{x}+\mathbf{y}\in P$$ $$\mathbf{x} \in P \text{ and } a\in S \Rightarrow a\mathbf{x}\in P$$ 당연하지만 $V$ 역시도 자기 자신의 subspace입니다.
Span.
임의의 $M$개 벡터 집합 $W=\{\mathbf{x}^{(m)}\}_{m = 0,1,\cdots,M-1}$에 대해
$$\text{span}(W)=\left\{\sum_{m=0}^{M-1}a_m\mathbf{x^{(m)}}\right\}\quad a_m\in S$$ 즉, $W$의 span이라는 것은 $W$에 속하는 벡터들의 모든 가능한 선형 조합을 원소로 갖는 집합입니다. 그리고 $W$의 벡터들이 다음과 같은 성질을 만족하면 서로 "선형 독립"이라 합니다: $$\sum_{m=0}^{M-1}a_m\mathbf{x^{(m)}}=0 \Longleftrightarrow a_m=0\quad \text{for } m=0,1,\cdots,M-1$$
Basis.
이제 앞서 정의한 두 개념을 바탕으로 basis를 정의하면, $P$ subspace에서 뽑은 $K$개 벡터들의 집합 $W=\{\mathbf{x}^{(k)}\}_{k = 0,1,\cdots,K-1}$는 다음과 같은 성질들을 만족할 때 $P$의 basis라고 불립니다:
- $W$의 원소들이 서로 선형 독립이다.
- $\text{span}(W)=P.$
두번째 조건은 $W$가 $P$에서 complete하다고 표현하기도 합니다.
Orthogonal/Orthonormal Basis.
Subspace $P$의 orthonormal basis는 다음과 같은 $K$개의 벡터 집합을 말합니다:
$$\langle \mathbf{x^{(i)}},\mathbf{x^{(j)}}\rangle = \delta[i-j] \quad 0\leq i,j<K$$ 벡터가 서로 orthogonal하지만 normal하지는 않을 수도 있는데 사실 서로 선형 독립이기만 하면 Gramm-Schmitt로 언제나 orthonormal하게 만들 수 있기 때문에 별 문제 될 것은 없습니다.
Orthonormal 벡터가 특별한 이유는 $N$-차원 subspace 안에서 얻은 $N$개의 벡터가 서로 orthonormal하면 곧 그 벡터들의 집합이 subspace의 basis라는 특징이 있기 때문입니다. 즉, 유한 차원에서는 모든 orthonormal 벡터들을 찾는 순간, 언제나 그 집합이 해당 공간을 span한다고 얘기할 수 있다는 뜻이죠.
Properties of Orthonormal Bases
이제 Projection에 대해 설명하기 위한 재료들이 모두 소개가 끝났습니다. $P$ subspace의 orthonormal basis 집합 $W=\{\mathbf{x}^{(k)}\}_{k = 0,1,\cdots,K-1}$는 다음과 같은 성질들을 만족하는데요. 이들을 소개하면서 projection도 간단히 살펴보도록 하겠습니다.
Synthesis and Analysis Formula.
$\mathbf{y}\in P$는 아래와 같이 basis $W$의 선형 조합으로 표현할 수 있고 $$y=\sum_{k=0}^{K-1}a_k\mathbf{x}^{(k)}$$ 여기서 $a_k$는 각 basis 벡터에 대응하는 coefficient입니다. 이 때, 위 식을 일반적으로 synthesis formula라 하며 $a_k$ coefficient들은 *Fourier coefficient라 불립니다.
* Fourier coefficients라 하면 Fourier series에 대한 coefficients를 말하는 경우가 많지만, 사실 일반적으로 임의의 orthonormal basis에 대한 coefficients을 칭하는 말이기도 합니다.
여기서 synthesis formula라고 부르는 까닭은 basis 집합과 각 basis에 대응하는 coefficent들이 있을 때 원래 신호 혹은 vector를 "만들어내는" 식이라고 생각할 수 있기 때문이죠. 한편, 해당 Fourier coefficients를 찾는 방법은 아래와 같으며: $$a_k = \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle$$ 이를 synthesis formula에 대응하여 analysis formula라고 부릅니다. Fourier basis로 expansion 했을 때를 생각해보시면 신호의 주파수 성분들을 "찾거나 분석"한다고 생각할 수 있으므로 이렇게 이름을 붙이는게 자연스럽습니다.
Parseval's Identity.
Orthonormal basis들은 다음과 같은 norm conservation 성질을 만족하는데요:
$$||\mathbf{y}||^2=\sum_{k=0}^{K-1}\left| \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle \right|^2.$$ 이를 물리적인 값으로 표현하자면 에너지를 뜻한다고도 생각할 수 있고, 따라서 Parseval's Identity는 에너지 보존 법칙이라고도 알려져 있습니다.
혹은! 피타고라스 정리이기도 하죠. 위 식이 2차원일 때를 생각해보시면 됩니다. 좌표평면에 두 좌표축(basis)의 coefficient 값들은 내적으로 계산되고 이렇게 직교하는 좌표축에 대해 각 좌표값의 제곱의 합은 빗변의 길이인 벡터 $y$의 길이의 제곱과 같다고 말하고 있습니다.
피타고라스 정리이지요!
Bessel's Inequality.
Parseval's equality를 한 번 더 일반화한 형태가 바로 Bessel's Inequality입니다. subspace $P$에서 $L$ 개의 orthonormal 벡터 집합 $G\subset P$, $G=\{\mathbf{g}^{(l)}\}_{l=0,1,\cdots,L-1}$에 대해 언제나 다음이 성립합니다:
$$||\mathbf{y}||^2 \geq \sum_{l=0}^{L-1}\left| \langle\mathbf{g}^{(l)}, \mathbf{y}\rangle \right|^2.$$ 여기서 lower bound는 $G$가 $P$에서 complete할 때 입니다 ($\text{span}(G)=P$).
Best Approximations (Projections).
Hilbert 공간에서 orthogonal basis가 중요한 이유 중 하나는, Hilbert projection theorem에 의해 가장 optimal한 approximation이 orthogonal projected vector로 유일하기 때문입니다. 즉, $P$가 $V$의 subspace이고 $\mathbf{y}\in V$에 대해 $P$에서 이에 가장 가까운 벡터를 찾기 위해서는 least squares appoximation과 orthogonal projections에 대한 개념이 필요합니다. 먼저 "가장 좋은" approximation을 $||\mathbf{y}-\mathbf{\hat{y}}||$가 최소가 되는 $\mathbf{\hat{y}}$라고 정의할 때, 아래 그림과 같이 간단히 $\mathbf{y}$를 $P$의 orthonormal basis에 project하는 것으로 얻을 수 있습니다.
여기서 projection은 아래와 같이 정의됩니다: $$||\mathbf{y}||^2 =\sum_{k=0}^{K-1} \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle \mathbf{x}^{(k)}$$ 근사에 대한 error를 벡터 $\mathbf{d}=\mathbf{y}-\hat{\mathbf{y}}$라고 정의하면, $\mathbf{d}\perp\hat{\mathbf{y}}$이며, 위와 같은 방식이 error square norm을 최소화한다는 것을 알 수 있습니다. $$\arg\min_{\hat{\mathbf{y}}\in P}||\mathbf{y}-\hat{\mathbf{y}}||_2 = \sum_{k=0}^{K-1} \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle \mathbf{x}^{(k)}.$$
Examples of Bases
Finite Euclidean Spaces
먼저 orthononal 벡터 $N$개 $\{\mathbf{x}^{(k)}\}$의 *conjugate 벡터를 행으로 쌓아 $N\times N$ 행렬 $M$을 만듭니다. 이 때, $m$번째 basis에 대한 $n$번째 원소는 다음과 같이 표현될 수 있는데요: $$M_{mn}=\left(\mathbf{x}_n^{(m)}\right)^*$$ 이런 행렬 $M$을 change of basis 행렬이라고 부르고, 이제 이를 이용하여 syntheis formula와 analysis formula를 표현할 수 있습니다. 즉, $\mathbf{y}$가 주어졌을 때, $\{\mathbf{a_k}\}_{k=0,\cdots,N-1}$은 coefficient 벡터 $\mathbf{a}\in \mathbb{C}^N$로 표현할 수 있으므로, synthesis formula와 analysis formula는 각각 다음과 같습니다: $$\mathbf{y} = M^H\mathbf{a}$$$$\mathbf{a} = M\mathbf{y}.$$ * 사실 conjugate가 아니라도 전혀 상관없고 똑같은 결과를 만들 수 있지만 굳이 이렇게 한 이유는 다음 챕터에서 다룰 Discrete Fourier Transform가 같은 형태를 만들어 연관성을 보여주기 위함입니다.
Haar basis
좀 더 재미있는 예시가 무엇이 있을까 생각해보다가 Haar basis를 가져와 봤습니다. 매우 간단하게 생겼지만 Haar basis는 Wavelet analysis의 시금석이라고도 할 수 있는 중요한 신호처리 도구 중 하나입니다. $\mathbb{C}^8$ 공간에서의 예시를 보자면 다음과 같이 Haar basis에 대한 change of basis 행렬을 만들 수 있습니다.
$$ H = \begin{bmatrix}
1&-1&0&0&0&0&0&0 \\
0&0&1&-1&0&0&0&0 \\
0&0&0&0&1&-1&0&0 \\
0&0&0&0&0&0&1&-1 \\
1&1&-1&-1&0&0&0&0 \\
0&0&0&0&1&1&-1&-1\\
1&1&1&1&-1&-1&-1&-1\\
1&1&1&1&1&1&1&1
\end{bmatrix}
$$
$H$의 각 행이 모두 선형 독립이라는 것은 쉽게 알 수 있죠. 따라서 각 행이 basis를 이룬다는 것은 간단히 증명되었습니다. 그리고 $HH^H$이 diagonal 행렬이란 것도 계산해보면 쉽게 알 수 있습니다. 즉, 각 행들이 서로 orthogonal하다는 것도 알 수 있습니다.
이제 이 녀석이 갖는 재미있는 성질을 약간 엿보고 싶다면 다음과 같이 간단한 예시들을 확인해보면 됩니다. 먼저 $\mathbf{y}=[1, 1, \cdots, 1]^H$이라는 상수 신호를 Haar basis로 분해해보겠습니다: $$H\mathbf{y} = [0, 0, 0, 0, 0, 0, 0, 8] ^H$$이라는 것을 매우 간단히 알 수 있습니다. 그럼 $\mathbf{y}=[1, -1, \cdots, 1,-1]^H$과 같이 부호가 교차되는 신호는 어떻게 될까요? 손으로도 쉽게 계산해볼 수 있지만 답을 알려드리자면, $$H\mathbf{y} = [2, 2, 2, 2, 0, 0, 0, 0]^H$$으로 표현이 가능합니다. 즉, 상수 신호의 경우는 마지막 basis만으로도 표현이 가능하고 부호가 교차하는 경우도 4개의 basis들만으로 표현이 가능합니다. 즉, Haar basis를 사용하면 매우 적은 수의 coefficient 조합으로 신호를 표현하는 것이 가능하다는 뜻입니다. 이런 성질을 바탕으로 다양한 이미지 분석 방법들이 개발되어 왔습니다.
마치며...
이제 드디어 도구들이 모두 준비가 끝났습니다. 지금까지 이런 도구들을 배우는 이유를 한 번 짧게 정리해보자면 다음과 같습니다.
먼저 Hilbert 공간에 대해 살펴봤었는데요. 지금까지 살펴본 유한 차원 신호들이나 periodic 신호들은 모두 $\mathbb{C}^N$에 포함되고 우리가 관심이 있을만한 무한 차원 신호들은 모두 $L_2$ 혹은 $\ell_2$에 포함됩니다. 이들은 모두 Hilbert 공간이기에 이를 알면 신호처리 전반을 하나의 통일된 관점에서 이해할 수 있게 되고, 따라서 매우 강력한 도구라 할 수 있습니다.
둘째로 orthogonal basis에 대해 다뤘는데요. 이들이 여러 종류가 있을 수 있음을 알 수 있고 basis 각각이 갖는 특성에 따라 같은 신호를 서로 다른 관점들로 분석하는 것이 가능하다는 것을 알 수 있었습니다. 이런 이해는 뒤에 있을 Fourier transform을 이해하는데 도움이 될 것입니다.
마지막으로 subspace projection과 approximation을 보았는데, 이는 신호를 filtering하거나 이미지를 압축하는 것을 이해할 때 사용할 도구입니다.
다음 글부터는 본격적으로 신호처리에 관련된 얘기들을 다루게 될 것입니다. 푸리에 해석(Fourier Anaylsis)이라고 불리는 다음 쳅터는 신호처리에서 매우 중요한 내용을 담고 있으니 꼭 이해하고 넘어가는 것이 좋습니다. 이름이 매우 무서워 보이지만 지금까지 다룬 기초 개념들을 잘 숙지하셨다면 매우 쉽게 이해하실 수 있을것이라 장담합니다. 제가 그렇게 되도록 도와드리겠습니다.
그럼 다음 글에서 뵙겠습니다.
To be continued ... (planned)
- Preface
- What is Digital Signal Processing? (1)
- Discrete-Time Signals (2)
- Signals and Hilbert Spaces
- Euclidean Spaces and Hilbert Spaces (3-1)
- Subspaces, Bases, Projections, Haar basis ($\leftarrow$)
- Fourier Analysis (4 $\leftarrow$ next to read)
- Interpolation and Sampling (9-1)
- Interpolation
- Sampling theorem
- Aliasing
- Multirate Signal Processing
- Downsampling
- Upsampling
- Oversampling
