[PR12 Video] 374. Fourier Features Let Networks Learn High-Frequency Functions in Low Dimensional Domains (+ NTK, Neural Tangent Kernel)

TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#374. Fourier Features Let Networks Learn High-Frequency Functions in Low Dimensional Domains

PR12 374번째 발표입니다. 오늘도 저번처럼 가면 갈수록 inductive bias를 줄여야한다고 외치고 있는 연구 방향과는 정반대로, 이론에 근간한 간단한 fix를 통해 훨씬 강력한 성능을 달성한 모델을 소개해보겠습니다. 매우 즐겁게? 읽었는데요. 다른 분들도 재미있으셨으면 좋겠습니다. (네...제가 그렇죠 뭐. 오늘도 매우 어려운 논문을 골라놓고 내일이 개강인데....난 왜 이 논문을 골라서 스스로 괴롭게 살까 계속 그 생각만 하면서 준비했습니다. 담부턴 좀 쉬운 논문 해야지 하면서 맨날 스스로도 소화하기 힘든 논문을 고르는건 과학인듯 합니다.) (꼭 고를 때 되면 쉽게 할 수 있어보이더라) (다 하보니 1시간...)

Paper:  https://arxiv.org/abs/2006.10739

다른 분들의 발표도 보고 싶다면 아래 링크에서 확인하시면 되겠습니다 :)

1기 2기 3기 4기

* 현재 4기가 진행 중입니다!

다음 읽을거리

• Backpropagation 설명 예제와 함께 완전히 이해하기
• RNN 설명 예제와 함께 완전히 이해하기
• 초짜 대학원생의 입장에서 이해하는 VAE (1)
• 초짜 대학원생 입장에서 이해하는 GANs (1)
• 초짜 대학원생의 입장에서 이해하는 Domain-Adversarial Training of Neural Networks (DANN) (1)
• 초짜 대학원생의 입장에서 이해하는 DCGAN (1)
• 초짜 대학원생의 입장에서 이해하는 Unrolled GAN (1)
• 초짜 대학원생의 입장에서 이해하는 InfoGAN (1)
• 초짜 대학원생의 입장에서 이해하는 LSGAN (1)
• 초짜 대학원생의 입장에서 이해하는 BEGAN (1)
• 초짜 대학원생의 입장에서 이해하는 f-GAN (1)
• 초짜 대학원생의 입장에서 이해하는 EBGAN (1)
• 초짜 대학원생의 입장에서 이해하는 The Marginal Value of Adaptive Gradient Methods in Machine Learning (1)
• 초짜 대학원생의 입장에서 이해하는 SVM (1)
• Image Restoration (IR): inverse problem point of view (1)
• 디지털 신호 처리가 궁금하다면: Signal Processing For Communications
• 머신러닝에 속하는 전반적인 연구 내용들이 궁금하다면: Machine learning
• 머신러닝에서 잘 사용되는 수학에 관심이 있다면: Mathematics

Signal Processing For Communications (3-2)

지난 글에서는 내적과 거리를 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

$\mathbb{C}^N$과 같은 가장 간단한 Hilbert 공간에서는 orthonormal bases를 찾는 것이 매우 쉽습니다. 가장 클래식한 것이 canonical basis $\{\mathbf{\delta}^{(k)}\}_{k=0,\cdots,N-1}$이죠: $$\mathbf{\delta}_n^{(k)}=\delta[n-k]=\begin{cases}1 \quad\text{if } n=k \\ 0 \quad\text{otherwise}\end{cases}$$ 여기서는 analysis와 synthesis formula도 매우 간단한데요.

먼저 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

Signal Processing For Communications (3-1)

Signals and Hilbert Spaces

17세기 이후, 데카르트가 기하적인 구조를 대수적인 형태로 표현하는 방법을 제안하면서부터 대수 (algebra)와 기하(geometry) 분야가 서로 영향을 주고 받으며 엄청나게 발전했습니다.

대표적인 예로 기원전부터 연구되었지만 풀지 못했던 임의 각의 3등분 문제는 3차 방정식의 유리수 해가 존재하지 않는 것을 보이는 것으로 불가능하다는 것이 쉽게 증명되었습니다. 저도 수능 시험을 볼 때, 도형 문제를 좌표계로 표현해서 쉽게 풀었던 경험이 있습니다.

반대로 대수적인 방법으로는 풀기 어려운 문제를 기하적인 직관을 바탕으로 쉽게 이해하거나 풀 수 있는 경우도 많습니다. 예를 들어 거리라던가 직교라는 개념은 대수적인 해석보다는 기하적으로 이해할 때 좀 더 빠르고 쉽게 받아들일 수 있습니다.

하지만 3차원을 넘어서서 4차원, 더 나아가 무한 차원으로 확장했을 때도 우리가 직관적으로 알고 있는 공간에 대한 개념들을 그대로 적용해도 아무 문제가 없을까요? 과연 무한 차원 공간에서도 거리나 직교라는 기하학적인 개념이 우리가 알고 있는 방식으로 동작할지를 생각해보면, 이 부분이 생각보다 명확하지 않다는 것을 알 수 있습니다.

실제로 공간의 차원이 고차원으로 올라갈수록 우리의 직관이 우리를 배신하는 경우가 많기 때문에 주의해야합니다. 예를 들면, 박스 안에 공을 넣었는데 넣고 보니 박스 안에 들어간 공의 지름이 박스보다 커진다거나 (예시1), 분명 찰흙을 뭉쳐 속이 꽉 찬 공을 만들었는데 만들고 보니 무게가 모두 껍질 쪽에 몰려서 마치 비눗방울처럼 바뀐다거나 (예시2) 하는 황당한 상황들을 흔히 볼 수 있죠.

이와 같이 고차원 공간에서는 인간의 직관이 공간에 대해 제대로 이해하는 것을 오히려 방해하는 경우가 생깁니다. 하지만 그렇다고 우리가 태어나서부터 가지고 있던 편한 도구를 버리기에는 너무 아깝죠. 그렇기에 공간에 대한 우리의 직관적인 이해를 무한 차원에서도 그대로 확장해도 문제가 없기 위해서는 좀 더 엄밀하고 구체적인 제약을 지닌 공간이 필요할텐데요. 그런 공간을 만들기 위해 고안된 것이 바로 Hilbert space입니다.

신호 처리 공부하다가 뜬금없이 웬 해석학이냐고 할 수도 있지만, 이 부분이 신호 처리를 이해하는데 매우 좋은 도구가 된다는 것은 차차 자명해질 것입니다. 잠깐만 부연하자면, 이전 글에서 얘기했던 바와 같이 우리는 discrete-time 신호가 벡터의 형태로 표현이 가능하다는 것을 알고 있습니다. 이렇게 신호가 벡터로 표현되는 순간, 선형대수학이나 미적분학에서 개발된 강력한 도구들을 사용할 수 있게 되는데요. 이에 더해 이 신호가 Hilbert 공간 안에 있다는 것이 보장되면, 길이가 유한한 신호이든 함수와 같은 무한한 신호이든 상관없이 우리가 익숙하고 편하게 알고 있던 기하학적인 도구들을 문제없이 그대로 사용할 수 있게 됩니다.

예를 들어 2차원이나 3차원에서 사용하던 피타고라스 정리나 평행 4변형의 법칙과 같은 개념이 자연스럽게 확장되는 것이죠. 따라서, Hilbert 공간에서는 유한한 길이의 벡터 뿐만 아니라 무한한 길이의 벡터에 대한 추상적인 분석과 finite lenght 신호 대한 분석을 같은 관점에서 매끄럽게 설명할 수가 있게 됩니다.

여기까지 Hilbert 공간이 신호처리에서 중요한 이유를 살짝 소개해드렸는데요. 더 구체적인 내용은 먼저 우리에게 익숙한 유한 차원 유클리드 공간(Euclidean space)를 바탕으로 여러 개념들을 소개하고 이를 무한 차원 Hilbert 공간으로 확장해가면서 살펴보겠습니다.

Euclidean geometry

유클리드 기하는 우리가 태어나서부터 자연스럽게 갖고 있는 공간 감각과 매우 잘 맞아 떨어지는 면이 많습니다. 예를 들어 $\mathbb{R}^2$ 공간은 "평면"에 대한 경험과 대응되고 $\mathbb{R}^3$는 우리가 살고 있는 "공간"에 대한 이해로 자연스럽게 이어집니다. 여기서는 "거리"에 대한 개념도 매우 명백하고 "직교"한다는 것도 어떤 이미지인지 매우 명확하게 그릴 수 있습니다. 심지어 "기저 (basis)"와 같이 매우 추상적인 개념조차도 위도나 경도 높이와 같은 개념으로 치환하여 직관적인 이해하는 것이 가능하죠.

물론 앞서 말했듯이 고차원으로 갈수록 여러 문제가 생길 수 있다지만, 최소한 $N$ 차원으로 유한한 유클리드 공간에서는 여러가지 추상적인 개념을 우리가 익숙한 2차원 혹은 3차원으로 내려서 생각해도 문제가 없기 때문에, 여기서 먼저 복잡한 개념들을 소개하고 충분히 이해하는 것에 의미가 있습니다.

Vectors and Notation.

$\mathbb{R}^N$ 공간의 한 점은 $N$-tuple 좌표 형태로 나타낼 수 있습니다:

$$\mathbf{x} = [x_0, x_1, \cdots, x_{N-1}]^T.$$

우리는 이 것을 벡터라고 부르고 이 좌표는 "standard" 직교 기저들로 표현이 됩니다. 

Inner Product.

두 벡터 $\mathbf{x},\mathbf{y\in \mathbb{R}^N}$ 간의 내적은 다음과 같이 정의 됩니다. 

$$\langle \mathbf{x},\mathbf{y}\rangle=\sum^{N-1}_{n=0}x_n y_n$$

이 때 두 벡터의 내적이 0인 경우 우리는 이 두 벡터가 서로 직교한다고 말합니다.

$$\mathbf{x}\perp \mathbf{y} \Longleftrightarrow \langle \mathbf{x},\mathbf{y}\rangle=0$$

Norm.

벡터의 norm은 그 벡터의 길이를 나타냅니다. 보통 벡터의 norm은 내적으로 정의가 되는데 (induced) 기하적으로 생각하면 이해하기 매우 쉽습니다. (원점에서 벡터를 표현하는 좌표까지의 거리). 

$$||\mathbf{x}||_2=\sqrt{\sum^{N-1}_{n=0}x_n^2}=\langle \mathbf{x},\mathbf{x}\rangle^{1/2}$$

Distance.

위에서 정의한 norm은 자연스럽게 두 벡터 간의 유클리디안 거리를 정의하는데 사용됩니다. 

$$ d(\mathbf{x},\mathbf{y})=||\mathbf{x}-\mathbf{y}||_2=\sqrt{\sum^{N-1}_{n=0}(x_n-y_n)^2}$$

Bases.

$\mathbb{R}^N$에 대해 $N$개의 linear independent 벡터들을 골랐을 때: $\{\mathbf{x^{(k)}}\}_{k=0,\cdots,N-1}$, 이를 bases라고 부릅니다. 즉, 이 벡터들의 선형결합으로 임의의 $\mathbf{z}\in\mathbb{R}^N$와 $a_k\in \mathbb{R}$에 대해 다음과 같이 표현할 수 있다는 뜻입니다: 

$$\mathbf{z}=\sum^{N-1}_{k=0}a_k\mathbf{x}^{(k)}$$

이러한 bases들 중에 서로 직교하고 norm이 1인 녀석들을 orthonormal bases $\{\mathbf{y^{(k)}}\}_{k=0,\cdots,N-1}$라고 부릅니다: 

$$\langle \mathbf{y}^{(k)},\mathbf{y}^{(h)}\rangle=\begin{cases}1 \quad\text{if } k=h \\ 0 \quad\text{otherwise}\end{cases}$$

그리고 이러한 bases 중 가장 "기본적인(standard)" 녀석이라 하여 $\mathbb{R}^N$에 대해 다음과 같은 bases를 canonical bases $\{\mathbf{\delta}^{(k)}\}_{k=0,\cdots,N-1}$라 부릅니다:

$$\mathbf{\delta}_n^{(k)}=\delta[n-k]=\begin{cases}1 \quad\text{if } n=k \\ 0 \quad\text{otherwise}\end{cases}$$
이 bases가 orthonormal하다는 것은 매우 자명하죠. 이런 종류 중 또 다른 중요한 녀석이 있는데요. 바로 Fourier bases $\{\mathbf{w}^{(k)}\}_{k=0,\cdots,N-1}$ 입니다:

$$\mathbf{w}_n^{(k)}=\frac{1}{\sqrt{N}}e^{-j\frac{2\pi}{N}nk}$$
이 녀석에 대한 내용은 orthonormality 증명과 함께 나중 챕터에서 다룰 것입니다. 여기서 가져가실 점은 Fourier bases도 일종의 좌표축들이고 임의의 $\mathbf{x}\in\mathbb{R}^N$에 대해 이를 canonical 좌표계로 표현할 수도 있지만, Fourier 좌표로도 표현할 수도 있다는 점입니다. 다만 좌표축이 변한만큼 좌표값도 바뀌겠죠.

이렇게 하나의 좌표축으로 표현된 어떤 벡터를 다른 좌표축으로 바꿔 표현하는 것을 벡터에 대한 좌표축 "변환 (transform)"을 수행한다고 얘기합니다. 즉, Fourier transform은 별게 아니라 임의의 벡터를 Fourier bases로 좌표축을 바꿔서 표현하는 방법임을 알 수 있습니다.

눈치가 빠르신 분들은 이미 여기서부터 어째서 신호처리 개념들을 기하적으로 생각하는 것이 개념을 이해하는데 도움이 되는지 알 수 있으실거라 생각합니다. 그저 대수적인 표현 방식으로만 Fourier transform을 이해하려고 하면 적분과 복잡한 수식으로 이루어진 형태에 그 뒤에 숨어있는 뜻을 알기가 쉽지 않지만, 위와 같은 관점에서 보면 결국 Fourier transform은 그저 좌표축 치환하는 여러가지 방법 중 하나일 뿐이라는 것을 알 수 있죠. 적분은 차후 보시겠지만 내적의 일반적인 표현일 따름이구요.

From Vector Spaces to Hilbert Spaces

이제 앞서 얻은 유한 차원 유클리드 공간에 대한 이해를 바탕으로 무한 차원 Hilbert 공간으로 개념들을 확장해보겠습니다. 그런데 애초에 우리가 편하게 다룰 수 있는 유한 차원 공간에서 굳이 무한한 차원으로 넘어가야 하는 이유가 뭘까요?

두루뭉술하게 이렇게 일반화를 한 형태가 이론적으로 분석하거나 다루기가 더 쉽기 때문에 이론적인 발전을 위해서는 이런 확장이 필연적이었을 것이라 설명할 수도 있겠습니다만, 좀 더 구체적으로 그렇게 하지 않았을 때 어떤 문제가 생기는지를 보는게 더 이해가 쉽겠습니다.

일단 자연에 존재하는 신호가 굳이 discrete하고 유한한 값만을 가질 이유가 없다는 것은 동의하실겁니다. 곰곰히 생각해보면 임의의 신호가 굳이 유한한 차원 안에서 표현되야 한다는 것이 오히려 더 큰 제약이죠. 예를 들어 임의의 continuous 함수 $f: \mathbb{R}\rightarrow \mathbb{R}$는 모두 무한 차원 벡터로 표현될 수 있습니다. 그럼 이런 신호를 다루기 위해서 우리에게 익숙한 유한 차원 유클리드 공간 $\mathbb{R}^N$이나 $\mathbb{C}^N$을 적용하되 단순하게 $N$을 무한하게 키워서 사용하면 어떻게 될까요?

음... 당장 내적이나 norm부터 문제가 생기는군요. 예를 들어 모든 값이 1로 일정한 무한 수열과 같이 매우 단순한 수열을 생각해보시면 내적이나 norm 값들이 발산한다는 것을 쉽게 알 수 있습니다. 이렇듯 단순하게 공간을 확장해보면 우리가 알던 도구들이 잘 정의되지 않아서 신호를 다루기가 쉽지 않아집니다.

그래서 이런 도구들이 제대로 기능하면서도 위와 같은 문제가 없도록 벡터 공간에 적절한 제약을 걸어 일반화한 공간이 Hilbert space입니다. 이 제약을 신호처리에 가까운 언어로 간단히 표현하면, finite energy를 가지는 벡터들만이 Hilbert space의 원소가 되도록 제약을 걸었다고 생각할 수 있습니다.

이를 조금만 더 엄밀하게 얘기해보면 다음과 같습니다:

벡터 집합 $V$와 스칼라 집합 $S$에 대해, 간단한 사칙연산과 null vector 등이 정의된 벡터 공간 $H(V,S)$에 내적이 추가로 구비된 공간을 Inner Product Space라고 부릅니다. Hilbert 공간은 여기에 더해 "completeness"를 추가로 요구하는데요. (Hilbert 공간 = complete inner product space). 한국어로는 완비성이라고 부르는 이 개념은 $H(V,S)$ 공간의 코시 수열(Cauchy sequence)이 수렴할 때, 그 극한에 해당하는 벡터 역시도 같은 공간 $H(V,S)$ 안에 존재한다는 말입니다.  결국 completeness의 정의를 조금 생각해보면 Hilbert 공간이 구멍이 없이 꽉 차있다는 얘기입니다. (조밀성과는 다릅니다.)

음....사실 저는 처음 이런 추상적인 개념이 도대체 신호를 다룰 때 어째서 중요한지 아무도 알려주는 사람이 없어서 도무지 이해하기 어려웠습니다. 그냥 그런가보다 하고 넘어가기에는 답답해 하다가 찾은 나름의 답은 다음과 같습니다.

다시 무한한 support를 갖는 신호를 다루는 입장에서 생각해보겠습니다. 이 신호를 표현하기 위해 앞서 배웠던 유클리드 공간의 basis에 관한 내용을 확장해보면 다음과 같은데요: $$\mathbf{z}=\sum^{\infty}_{k=0}a_k\mathbf{x}^{(k)},\quad \mathbf{x}^{(k)},\mathbf{z}\in\mathbb{R}^\infty, a_k\in \mathbb{R}.$$ 즉, 임의의 신호에 대해 무한 개의, 무한 차원 basis들의 선형 결합으로 표현할 수 있다는 뜻이 됩니다.

문제는 일단 무한 차원의 벡터들에 대한 무한 합이라는 것부터 잘 정의가 될지부터 잘 감이 오지 않죠. 사실 이것이 가능하다는 것을 보여준 것이 Fourier series입니다. 언젠가 더 자세히 소개할 날이 오겠지만 Fourier의 업적 중 하나인 Fourier series는 임의의 함수를 무한 개의 sinusoidal basis 함수들의 합으로 표현이 가능하다는 것을 보여줍니다. 즉, 수렴합니다.

이 때, "신호"란 실제로 물질적인 세상(공간)에 존재하는 신호들로서 어떤 물리적인 조건(예: finite energy)들을 만족할텐데요. 어떤 신호가 이런 공간 내에 존재하지 않는다는 말은, 해당 신호가 물리적인 조건을 만족하지 않아 제대로 된 신호가 아니라고 이해할 수 있겠습니다.

그런데 만약 이런 basis들의 무한 합으로 신호를 표현하고 보니 그 합이 수렴하는 신호가 물질적인 세상을 벗어나 버린다면, 즉, 그 수렴 결과가 의미가 없는 신호라면 (혹은 또 다른 말로 해당 공간이 완비성이 보장되지 않는다면), 이 공간 안에서는 신호를 다루기가 까다로워집니다.

결국 Hilbert 공간 안에서는 벡터를 가지고 아주 이상한 짓을 하지 않는한 웬만해서는 어떤 연산을 하든 이 공간 안에서만 놀 수 있기 때문에 "좋은" 공간이라고 생각하시면 됩니다.

Hilbert space의 예시

결국 이런 좋은 성질들과 제약 덕분에, 이미 소개한 것 처럼 Hilbert 공간은 *함수들도 원소로 갖을 수 있는데요. 예를 들어 다음과 같은 녀석들이 있습니다:
(* 여기서 더 나아가는 것은 함수 해석학에서 배울 내용이니 여기서는 그런 것이 있다고만 알고 넘어가시면 됩니다. 단, 뒤에서도 유용하게 쓰일 녀석을 하나만 소개하자면 이전 글에서도 잠깐 언급되었었던 "the space of square integrable functions" 인데요. 이는 차후 continuous와 discrete-time 신호들 간의 관계를 보여줄 때 유용하게 사용될 것입니다.) 

Finite Euclidean Spaces.

유한한 $N$에 대해 내적이 $\langle \mathbf{x},\mathbf{y}\rangle=\sum^{N-1}_{n=0}x_n ^*y_n$으로 정의된 벡터 공간 $\mathbb{C}^N$은 Hilbert space입니다.

Polynomial Functions. 

functional Hilbert space의 한 예시로써 $[0,1]$ 구간에서 정의된 maximum degree가 $N$인 polynomial 함수들의 공간 $\mathbb{P}_N([0,1])$이 있습니다.

Square Summable Functions. 

또 다른 functional Hilbert space 예시로 square integrable functions이되 유한한 구간에서 정의된 square summable functions 공간이 있습니다. 예를 들어, $L_2([-1,1])$는 finite norm을 가지고 구간 $[-\pi,\pi]$에서 정의된 공간으로서 내적은 아래와 같이 정의됩니다:
$$\langle f,g \rangle = \int_{-1}^1 f^*(t)g(t)dt.$$
따라서 $f(t)$의 norm은 자연스럽게
$$||f(t)|| = \sqrt{\int_{-1}^1 |f(t)|^2dt}$$
로 정의되며 $L_2([-1,1])$에 속하는 $f(t)$는 모두 $||f||<\infty$를 만족해야합니다.

Inner Products and Distances

이제 앞서 유클리드 공간에서 소개했던 개념들을 하나씩 확장해보겠습니다.

먼저 내적을 조금 더 살펴보죠. 내적은 벡터 공간에서 벡터간의 "거리"라는 개념을 표현할 때 필수적인 요소입니다. 이를 이해할 때 기하적인 접근을 하면 훨씬 받아들이기가 쉬운데요. 예를 들어 $\mathbb{R}^N$ 유클리드 공간에서 $\mathbf{x}$ 벡터와 $\mathbf{y}$ 벡터가 있을 때 둘의 내적 $\langle \mathbf{x},\mathbf{y}\rangle$은 $\mathbf{y}$를 $\mathbf{x}$에 대해 orthogonal projection한 값이라고 할 수 있습니다.

정사영을 생각해보면 orthogonal projection이 $\mathbf{x}$의 점 중 $\mathbf{y}$에 가장 가까운 점을 찾는 방법임을 쉽게 알 수 있습니다.
$$\langle \mathbf{x},\mathbf{y}\rangle=||\mathbf{x}|| ||\mathbf{y}|| \cos\theta$$
여기서 $\theta$는 두 벡터 사이의 각도인데, 각도가 90도가 되면 cos 값이 0이 되면서 내적도 0이 되죠. 따라서 이런 관점에서, 내적은 두 벡터 간의 각도 차(혹은 두 벡터가 이루는 모양의 차이)를 바탕으로 유사도를 측정하는 방법이라 할 수 있습니다.

이런 내적은 신호처리에서 마주할 수 있는 다양한 상황에서 사용되는데요. 우리가 알고 싶은 내용에 따라 다른 이름으로 불리곤 합니다. 여러 신호 중 특정 신호를 찾고 싶을 때는 correlation이라는 용어로 사용되기도 하고, 신호를 바꾸거나 다른 신호로 근사하고 싶을 때는 filtering이라고 부르는데, 결국에는 모두 다 내적을 사용하여 두 신호 혹은 벡터 간의 유사성을 정량적으로 측정하는 것입니다.

위와 같은 맥락으로 이해하면 신호들 간에 orthogonality는 자연스럽게 두 신호가 완벽하게 구별이 가능하다는 뜻으로 이해할 수 있게됩니다. 즉, 두 신호의 생김새가 완전히 다른 것이죠.

이렇듯 유사성을 정량적으로 측정하기 위해 *내적으로부터 "거리"라는 개념이 나오고 우리가 잘 아는 유클리디안 거리가 나오는 것입니다.
$$ d(\mathbf{x},\mathbf{y})=\langle\mathbf{x}-\mathbf{y},\mathbf{x}-\mathbf{y}\rangle^{1/2}=||\mathbf{x}-\mathbf{y}||$$ 신호처리 분야에서는 이런 유클리디안 거리를 "root mean square error"라고 부르고 $\mathbf{y}$를 $\mathbf{x}$로 근사할 때 전반적인 "goodness of fit"을 정량적으로 측정하는 것에 많이 쓰입니다.
* 물론 여러가지 거리에 대한 정의들 중 내적이랑 관련이 없는 녀석도 있는데요: $ d(\mathbf{x},\mathbf{y})=\max_{0\leq n<N}|\mathbf{x}_n-\mathbf{y}_n|$. 이 녀석은 superemum norm을 바탕으로 정의되는 거리로 $||\mathbf{x}-\mathbf{y}||_\infty$로 표현되기도 합니다. 하지만 이에 대응하는 내적이 없기 때문에 이를 natural norm으로 갖는 Hilbert space는 존재하지 않습니다. 

Hilbert 공간에서는 위와 같이 유클리드 공간에서 자연스럽게 이해가 되는 내적이란 개념을 일반적인 함수에 대해 적용했을 때 아무런 문제 없이 확장이 가능합니다. 예를 들어 $L_2[-1,1]$ 공간에서 내적은 앞서 다음과 같이 정의된다고 말씀드렸었죠: $$\langle f,g \rangle = \int_{-1}^1 f^*(t)g(t)dt.$$ 이런 공간에 있는 함수 중에 다음과 같이 주기가 서로 다른 (즉, 전혀 다르게 "생긴") 두 함수에 대해 내적을 계산해보면 어떻게 될까요? 

재미있게도 이 두 함수가 정의에 따라 서로 orthogonal한 것을 확인할 수 있습니다. 

이를 엄밀하게 계산해볼 수도 있겠지만 위와 같이 간단하게 눈으로 확인해 볼 수도 있습니다. 빨간색으로 표현된 영역과 파란색으로 표현된 영역들이 서로 부호가 다르지만 넓이가 같은 짝이 있어서 서로서로 상쇄되어 결과적으로 적분을 하면 값이 0이 되는 것을 확인할 수 있습니다.

마찬가지로 거리 개념 역시도 확장하여 다음과 같이 나타내고 계산하는 것이 가능합니다: $$||f(t)-g(t)||^2 = \int_{-1}^1 |f(t)-g(t)|^2dt.$$

다음글 Preview

글이 좀 길어졌는데요. 여기서 잠시 끊고 다음 글에서 이어 확장해보도록 하겠습니다.

다음 글에서는 bases와 관련된 개념들을 소개할 것입니다. 여기서는 subspace라든가 projection 그리고 Parseval's identity나 Bessel's inequality와 같이 orthonormal bases들이 갖는 유용한 특성과 그런 bases들이 어떤 것들이 있는지 등을 다룰 것입니다.

한가지 재미있는 점은 이 Parseval's identity나 Bessel's inequality이라 불리는 두 특성이 이름은 서로 다르지만 사실은 우리가 매우 잘 알고 있는 유클리드 공간에서의 피타고라스 정리가 일반화 된 형태일 따름이라는 것이죠.

제가 계속 중간중간 언급을 하여 눈치채셨겠으나 이렇게 좀 기초적인 내용들을 계속 다루는 까닭은 신호처리의 중요한 개념들을 설명할 때 가져다 쓸 기초적인 도구이자 약속이기 때문이기도 하고 이를 바탕으로 좀 더 직관적 이해가 가능하기 때문입니다. 이 장이 익숙하거나 지루하신 분들은 차후 있을 Fourier Analysis 편으로 바로 넘어가셔도 되겠습니다.

그럼 다음 글에서 뵙겠습니다.

같이 읽으면 좋을 참고 문헌

• http://www.math.lsa.umich.edu/~kesmith/infinite.pdf

To be continued ... (planned)

• Preface 
• What is Digital Signal Processing? (1)
• Discrete-Time Signals  (2)
• Signals and Hilbert Spaces 
• Euclidean Spaces and Hilbert Spaces ($\leftarrow$) 
• Subspaces, Bases, Projections, Haar basis (3-2 $\leftarrow$ next to read)
• Fourier Analysis
• Interpolation and Sampling (9-1) 
• Interpolation
• Sampling theorem
• Aliasing
• Multirate Signal Processing
• Downsampling
• Upsampling
• Oversampling

Signal Processing For Communications (2)

이전 글에서 continuous-time과 discrete-time 신호에 대해 짧게 논의했었습니다. 이 장에서는 차후 사용될 기본적인 도구들을 소개하고 discrete-time 신호에 대해 좀 더 자세하게 살펴보겠습니다.

기존의 많은 신호처리 교과서들이 그렇듯이 역사적인 흐름에 따라 소개를 하자면, 먼저 continuous-time 신호를 다루고 나서 discrete-time 신호 그리고 digital 신호를 다루는 것이 순서에 맞을 것입니다. 이에 맞추어 전통적인 관점에서는 discrete-time 신호를 continuous-time 신호의 discrete version으로 생각하기 때문에 sampling을 중요하게 다뤄왔죠.

하지만 요즘 같은 디저털 시대에는 점점 더 sampling보다는 discrete-time 신호를 synthesis하는 것에 더 초점을 맞추어 중요하게 다뤄야할 필요가 있습니다. 이런 관점에서 오히려 역사적 흐름과는 반대로 discrete-time 신호를 중심으로 이야기를 풀어갈 때 훨씬 이해가 쉽다는 것을 차차 느끼실 것이라 생각합니다.

Discrete-Time Signal

앞으로 우리가 다룰 discrete-time signal은 complex-valued sequence입니다. 이는 정수 값을 갖는 인덱스 n에 대한 complex-valued 함수로 표현할 수 있으며, 예를 들어 위 그림에 대한 analytical closed-form은 다음과 같습니다: $$x[n] =((n+5)~\text{mod}~11)-5$$ 이 때, n은 dimensionless time이고 그저 sequence에서의 시간적인 순서를 표현하는 값입니다.

이런 discrete-time signal은 우리 실생활과 매우 밀접하게 연계되어 있는 한편, 우리 인간이 가지고 있는 물리적인 한계를 잘 보여줍니다. 즉, 우리가 어떤 신호를 "보고" 그 값을 아무리 빠르게 "기록"한다고 할지라도 그 사이에는 항상 "받아 적는데 걸리는 시간"이 존재하겠죠.

이와 같이 "받아 적는다"라는 행위가 바로 "sampling" 이고, 이는 아날로그 신호에서 discrete-time 신호를 만들어내는 가장 필수적인 방법입니다.  그렇다면 위와 같은 물리적 한계를 생각할 때 sampling을 하는 과정에서 불가피하게 없어지는 정보들로 인해 우리가 무슨 짓을 해도 신호의 정보를 완벽하게 기록하는 것은 불가능하다는 결론에 이릅니다.

그러면 평소에 우리가 잘만 듣고 있는 라디오나 CD에 녹음된 노래들은 어떻게 이런 한계를 극복한 것일까요? 결론부터 말하자면,

Continuous-time과 discrete-time 세계 사이를 오갈 때 이 사이의 간극으로 인한 정보 손실이 전혀 없이 넘나드는 방법이 있습니다! 

어떤 면에서는 말이 안 되는 것 같은 이 결론이, 바로 우리가 앞으로 신호 처리를 공부할 때 배우게 될 주요 테마입니다. 지금은 전혀 말도 되지 않아보이지만 이에 대한 수학적 증명은 sampling tehorem을 공부할 때 알게 될 것입니다. 그 장에 이르기까지 좀 더 도구를 갖춰야 엄밀하게 이해할 수 있겠으나 저 같이 성질이 급한 분은 저번 글을 통해 조금이나마 그 과정을 엿볼 수 있었을 것이라 생각합니다.

어찌 되었건 이 사실을 받아들이고 넘어가면, discrete-time 신호가 갖는 강력한 장점 하나를 알 수 있습니다. 어떻게든 discrete-time 세계로 신호를 넘기고 나면, 이 후부터는 "측정 간의 시간"이라는 개념 자체가 사라진다는 점입니다. 즉, 우리가 가진 신호는 그저 값들이 나열된 순서가 있는 수열일 따름이고, 그렇기 때문에 신호를 어떻게 얻었는가와 전혀 상관이 없어진다는 것입니다. 이 부분이 바로 매번 시스템과 신호의 물리적인 성질을 고려해야 하는 아날로그 세계와는 크게 다른 discrete 세계의 장점이 되겠습니다. (같은 얘기에 대한 좀 더 자세한 예시는 이전 글을 참고해주세요.)

Elementary Operators

Sampling 된 신호를 가지고 여러가지 계산을 수행할 수 있을텐데, 여기서는 몇몇 기본적인 계산에 대해 소개하겠습니다. 매우 지루한 부분이지만 나중에 사용된 필터 부분의 기본적인 배경이 되기 때문에 꼭 알아야 할 중요한 개념이기도 합니다.

Shift. 

수열 $x[n]$를 정수 k만큼 shift하는 것은 간단히 $$y[n]=x[n-k]$$라고 표현할 수 있습니다. 여기서 k가 양수이면 오른쪽으로 음수이면 왼쪽으로 신호가 shift되는 것을 알 수 있고, 따라서 delay operator는 $$\cal{D}_k\{x[n]\}= x[n-k]$$라고 표현할 수 있습니다.

Scaling.

수열 $x[n]$를 factor $a\in\mathbb{C}$만큼 scaling하는 것은 $$y[n]=ax[n]$$이라 표현됩니다. 여기서 a가 실수이면 신호의 amplification($a>1$) 혹은 attenuation($a<1$)을 각각 표현할 수 있고 만약 a가 복소수이면 amplification과 attenuation에 더해 phase shift가 추가되었다는 것을 알면 되겠습니다. 

Sum. & Product.

수열 $x[n]$와 수열 $w[n]$을 더하거나 곱하는 것은 elementwise로 수행합니다: $$y[n]=x[n]+w[n], \quad y[n]=x[n]w[n]$$

Integration.

Discrete-time에서의 integration은 다음과 같이 합으로 정의됩니다: $$y[n]=\sum_{k=-\infty}^{n}x[k]$$

Differentiation. 

Discrete-time 신호에 대한 미분은 어떻게 하면 될까요? 미분의 기초적인 정의를 생각해보면 차분의 비율이죠. 하지만 이미 sampling 간격이 정수로 정해져 있는 discrete-time signal에서 continuous-time의 differentiation을 적용하는 것은 맞지 않아보입니다. 따라서 discrete-time에서는 differentiation을 dfference로 근사하여 사용하는데 가장 간단한 *1st order approximation은 다음과 같이 나타낼 수 있습니다:  $$y[n]=x[n] - x[n-1]$$ 예를 들어 Unit step은 discrete-time impulse를 integration operator에 통과시키면 만들 수 있고 반대로 unit step을 differentiation operator에 통과시키면 impluse를 얻을 수 있겠습니다.
* 차후에 "정확한" 근사는 $H(e^{j\omega})=j\omega$라는 filter로 나타내진다는 사실을 배울 것입니다. 하지만 보통 1st order difference만으로도 적용하는 것에는 문제가 없습니다.

The Reproducing Formula

위와 같은 기본적인 operations들에 더하여 앞으로 자주 보게 될 수식을 하나 더 소개하겠습니다. $$x[n]=\sum_{k=-\infty}^\infty x[k]\delta[n-k]$$

즉, 임의의 discrete-time 신호는 shifted impulse들의 선형 결합으로 표현이 가능하다는 것. 이렇게 매우 자명한 식을 굳이 한 번 더 강조하는 까닭은 앞으로 나올 discrete-time signal의 특징들을 얘기할 때 거듭해서 이 식이 자주 보일 것이기 때문입니다. 

Energy and Power

Discrete-time signal의 energy는 다음과 같이 정의됩니다: $$E_x=||x||^2_2=\sum_{n=-\infty}^\infty \left|x[n]\right|^2$$ 이 식에서 바로 알 수 있듯이 에너지는 위 식의 sum이 수렴할 때만 finite하죠. 다른 말로 하자면 $x[n]$이 square-summable 해야지만 에너지가 유한합니다. 이런 성질을 갖는 신호를 finite energy signal이라고 하고 가장 간단한 예시로 주기 함수는 모든 값이 0이 아닌한 square summable하지 않습니다. 이렇듯 신호의 summability는 무한한 길이의 신호를 다룰 때 중요한 성질인데, 여기서 absolute summability는 좀 더 강한 조건이고,  square summability (finite energy)는 그에 비해 좀 더 약한 조건이라고 할 수 있습니다.

이제 energy가 정의되었으니 시간에 대한 energy의 비율로 power를 정의할 수 있습니다: $$P_x=\lim_{N\rightarrow \infty}\frac{1}{2N}\sum^{N-1}_{-N}\left|x[n]\right|^2$$ 유한한 energy를 갖는 신호는 total power가 0이라는 것을 알 수 있습니다. Decay하지 않는 exponential 수열들의 경우는 infinite power를 갖는 것을 알 수 있지만, 주의할 점은 infinite energy를 갖는 모든 신호들이 그러하진 않다는 점입니다. 예를 들어 사인파와 같은 주기 신호의 경우 finite power를 갖는데 이 경우 위 식에서 limit가 잘 정의되지 않으므로 주기가 있는 신호에서는 average energy over a period로 power를 나타냅니다: $$P_x=\frac{1}{N}\sum^{N-1}_{n=0}\left|s[n]\right|^2.$$

Discrete-time 신호의 종류 네 가지

Finite-length signals

앞서도 보았지만 길이 N의 신호를 나타낼 때, 이를 벡터 형태로 표현할 수도 있고: $$x=[x_0, x_1, \cdots, x_{N-1}]^T$$ 다음과 같이 수열로 표현할 수도 있겠습니다: $$x[n], \quad n=0,\cdots,N-1$$ * 벡터로 표현하는 법은 몇몇 신호처리 operation들의 기하적인 성질을 이해할 때 유용할 수 있고, 수열로 표현하는 방법은 대수적인 성질을 표현할 때 유용하게 사용되므로 앞으로도 이 둘을 왔다갔다 하면서 사용하겠습니다. 신호를 벡터로 다루면서 얻을 수 있는 기하학적인 직관은 때로는 훨씬 간단하면서도 쉽게 신호 처리를 배울 수 있도록 도와주기 때문에, 이에 관한 기초적인 도구들은 다음 장에서 더 자세히 다룰 것이고 뒷 장에서도 계속 이 도구들을 이용할 것입니다.

여기서 한 가지 finite-length signal을 다룰 때 염두에 둘 점이 있습니다. $x[n]$이라는 신호가 support 바깥($n<0$ or $n>N-1$)에서는 정의되지 않는다는 것. 이런 경우 "앞서 배웠던 shift 같은 것을 finite length signal에서는 어떻게 정의해야할 것인가?"와 같은 문제가 생깁니다. 따라서 보통은 이런 "border effects"와 같은 문제를 없애기 위해 우리가 얻은 유한한 신호를 적절한 수열에 embedding하여 사용하게 됩니다.

* 대표적으로는 circular shift를 사용하여 finite-length signal을 N-periodic signal로 바꾼다거나 이 대신 support 바깥에 zero padding을 하여 finite-support signal로 바꾸는 방법 등이 있겠습니다. 각각의 방법은 특징이 있는데 그로 인해 생기는 현상도 서로 다릅니다. 예를 들어 circular shift를 사용하는 경우는 shifted sequence와 original signal 간의 equivalence가 존재하지만 zero padding의 경우는 그렇지 않죠. 특히 circular shift의 경우 discrete-time signal의 frequency domain 표현에 대해 배울 때 자연스럽게 등장할 것입니다.

Infinite-length signals: Aperiodic

대부분의 일반적인 discrete-time 신호는 finite할 수밖에 없기 때문에 무한정 긴 심지어 주기가 없는 이런 형태의 신호가 어떤 의미가 있는가 싶을 수 있죠. 하지만 가장 일반화된 형태인만큼 이론적으로 분석하기에는 매우 기본적인 바탕이 됩니다. 

Infinite-length signals: Periodic

주기 N을 갖는 주기 수열은 다음과 같이 표현될 수 있습니다. 

$$\tilde{x}[n] = \tilde{x}[n+kN], \quad k\in \mathbb{Z}.$$

앞으로 주기 수열을 표현할 때는 항상 물결 표시를 쓰도록 하겠습니다. Periodic 수열은 길이는 무한하지만 정보가 유한한 수의 샘플들 안에 모두 포함되어 있다는 점에서 유한 길이의 신호와 무한 길이의 신호 간의 가장 기본적인 다리 역할을 한다고 생각할 수 있습니다. 

그저 길이만 무한한 신호(aperiodic)는 함수와 같이 표현이 가능하므로 수학적인 일반화 혹은 추상화에 도움이 될 수는 있겠지만, 이를 처음부터 다루는 것은 실질적이지도 않고 우리가 저장하거나 다루기가 어렵기 때문에 일반적인 교과 과정에서 주기 함수를 중요하게 다루고 먼저 배우는 것이라고도 생각됩니다.

* Periodic extensions:  주기 수열은 무한한 길이를 갖지만 정보량 자체는 유한하죠. 이런 점을 이용하여 finite-length 신호 $x[n]$을 periodic sequence로 embedding하여 표현할 수 있습니다: 

$$\tilde{x}[n] = x[n~mod~N], \quad n\in \mathbb{Z}.$$

이를 finite-length 신호의 "periodic extension"이라고 부르는데, 주기적인 성질 덕분에 아래 수식에서 볼 수 있듯이 shifted sequence와 original signal 간의 equivalence가 존재합니다. 이를 circular shift라고 합니다. 

Infinite-length signals: Finite-support

무한한 길이를 갖는 또 다른 형태의 신호로는 일정 범위 안에서만 값을 갖고 (finite-support ) 그 밖에서는 모두 값이 0인 신호가 있겠습니다.

$$\exists N,M\in \mathbb{Z},\quad \bar{x}[n] = 0 \quad \text{for } n<M~\text{and } N>M+N-1.$$

쉽게 눈치챌 수 있지만, 이 역시도 finite-length 신호를 무한한 길이를 갖는 신호로 embedding을 할 수 있는 또다른 방법으로써, 앞서와 다른 점은 더이상 shift된 신호가 본 신호와의 equivalence가 없다는 점입니다. 

지금까지 간단하게 우리가 다룰 신호들의 종류와 성질 그리고 각 종류별 신호들 간의 관계들에 대해 알아보았습니다. 이렇게 각각의 신호를 다루는 방식에 대한 자세한 내용은 앞으로 차차 다루게 될 것이므로 여기서는 이런 것들이 있다고만 언급하고 넘어가겠습니다.

그럼 다음 글에서 뵙죠.

To be continued ... (planned)

• Preface 
• What is Digital Signal Processing? (1)
• Discrete-Time Signals ($\leftarrow$)
• Signals and Hilbert Spaces 
• Euclidean Spaces and Hilbert Spaces (3-1) 
• Subspaces, Bases, Projections, Haar basis (3-2)
• Fourier Analysis 
• Interpolation and Sampling (9-1) 
• Interpolation
• Sampling theorem
• Aliasing
• Multirate Signal Processing
• Downsampling
• Upsampling
• Oversampling

Signal Processing For Communications (9-1)

모든 textbook들은 보통 재미있는 부분이 가장 뒷 chapter에 몰려있고, 여기서 할 얘기를 위해 필요한 도구들을 소개하느라 공부하는 사람의 진을 다 빼곤합니다. 학문적 측면에서 그리고 완결된 설명을 위해서는 이런 방식의 presentation이 맞는 것이겠으나 개인적으로는 앞 부분에서 지루한 내용들만 쭉 이어지는 형태가 불만이었습니다.

도대체 무엇을 위해 이런 지루한 내용들을 배워야하는지도 알려주지 않은 채로 학습 과정을 따라가야 하는 경우, 지친 나머지 정작 중요한 내용에 갈 때쯤엔 (심지어는 학기 중 진도가 느려져서 가지도 못하고!) 힘이 다 빠져서 아무래도 좋을 상태가 되곤 했는데요.

그래서 이번에는 제 마음대로 가장 뒤에 챕터에서 우리가 어떤 것을 알기 위해 이 모든 지루한 얘기들을 배우는 것인지를 먼저 확인한 후, 그 내용을 더 제대로 이해하기 위해 필요한 도구들을 살피러 앞으로 돌아오는 순서로 소개를 해볼까 합니다.

이 방식이 싫으시다면, 목차 자체는 일반적인 학습 순서대로 되어있으니 이 글타래가 완성된 이후, 순서대로 읽으시면 되겠습니다.

Interpolation and Sampling

이전 글에서 continuous-time과 discrete-time 신호 간의 간극에 대한 논의를 짧게 한 바 있습니다. 간단히 말해 interpolation과 sampling은 정보 손실 없이 continuous-time과 discrete-time, 이 두 세계 사이를 오가는 방법에 대한 이야기입니다.

Interpolation은 discrete-time 신호를 continuous-time 신호로 바꿀 때 사용하는데요. Interpolation이 중요한 이유는 아날로그 시스템인 우리 인간이 인지할 수 있는 신호의 형태가 결국 아날로그이기 때문입니다. 또한 전자기기에 사용되는 아날로그 회로를 가장 잘 모델링 하는 방법이 real variable에 대한 함수, 즉 continuous-time 함수로 표현하는 것이기 때문이기도 합니다.

Sampling은 반대로 continuous-time 신호를 discrete-time 신호로 바꿀 때 사용하는 방법이죠. 가장 간단한 sampling 방식은 일정 주기로 반복하여 기록을 하는 것이 되겠습니다. Sampling 방법은 random부터 radial 등 여러가지가 있지만, 가장 간단한 방식이 uniform한 주기 $T_s$로 샘플을 얻는 uniform sampling이며 여기서는 이를 기준으로 설명을 하겠습니다. 중요한 것은 어떤 sampling 방식이든 관계없이 continuous-time의 임의의 값과 해당하는 discrete-time 수열의 점(points) 사이에는 언제나 어떤 대응(correspondence) 혹은 관계가 만들어진다는 것입니다.

그러므로 interpolation과 sampling 둘은 결국 동전의 양면과 같이 떼어낼 수 없는 사이라는 점을 알아야겠지요. 앞으로 다룰 내용을 간략히 소개하자면,

• Interpolation: "이 행위(interpolation)로 인하여 기존 함수와 interpolated 함수 사이의 spectral 성질이 어떻게 달라지는가?"에 대한 것이며, 
• Sampling: "이 행위(sampling)로 인해 정보 손실이 생기는가?" 그리고 "손실이 있다면 얼마나 생기며 이를 피할 수 있는가?"가 되겠습니다. 

여기서 만약 sampling의 첫번째 질문에 대한 답이 (최소한 특정 신호에 대해) "없다"라면, 이는 우리가 discrete-time domain에서 개발한 모든 신호 처리 도구들을 고스란히 continuous-time 신호에도 적용할 수 있다는 것을 뜻합니다. 이는 직관적으로는 잘 와닿지 않는 매우 흥미로운 점이지요.

당연하지만 interpolation 함수의 가장 필수충족 요소는 샘플 주기 $T_s$에 대해 아래가 성립해야한다는 것입니다:
$$x(t)\bigg\rvert_{t=nT_s}=x[n]$$ 이렇게 각 instants에서의 값이 같다는 것을 제외하고 나면 남은 문제는 이 "값들 사이사이를 어떻게 채울 것인가?"가 되겠습니다.

Local Interpolation

임의의 discrete-time sequence $x[n]$에 대한 continuous-time 함수 $x(t)$를 만드는 가장 간단한 방법은 $t=nT_s$에 대해 $x(t)$의 값이 $x[n]$과 같도록 한 후 그 사이를 이웃하는 sequence 값들에 대한  임의의 선형 조합으로 나타내는 것입니다.

일반적으로 local interpolation 방식은 다음과 같이 표현할 수 있습니다: $$\begin{align}x(t)=\sum^\infty_{n=-\infty} x[n]I\left (\frac{t-nT_s}{T_s}\right) \end{align}$$ 여기서 $I(t)$는 interpolation 함수를 뜻하며 $I_N(t)$와 같이 표현된 경우 $N$은 $x(t)$을 보간할 때, 현재 instants에 대응하는 샘플 외에 N개의 discrete-time 샘플을 사용하였다는 것을 말합니다.
** 여기서 식 (1)을 잘 살펴보면 신호 $x(t)$가 하나의 interpolation 함수 $I(t)$의 shifted version들의 선형 조합으로 나타내진다고 이해할 수 있다. 이런 해석은 차후 유용하게 사용될 수 있는 관점이므로 염두에 두고 넘어갈 필요가 있다. 
** 또 한 편으로 이 식이 재미있는 이유는 두 신호를 convolution 하는 것으로 생각하되, 하나는 discrete-time signal $x[n]$이고 다른 하나는 continuous-time "impulse response" $I(t)$인 "mixed-domain" convolution으로 생각할 수 있다는 점이다. 

$I(t)$에 어떤 함수를 사용하느냐에 따라 신호 $x(t)$에 대한 interpolation 성격이 정해지는데 어떤 $I(t)$이든 interpolation 함수라면 다음과 같은 성질을 만족해야 합니다:
$$\begin{align}\begin{cases} I(0)=1 \\  I(k)=0 \quad \text{for} \quad k\in\mathbb{Z}\setminus\{0\} \\ \end{cases} \end{align}$$ 두 번째 조건이 뜻하는 것은 $I(t)$가 몇 개의 support를 갖는지와는 상관없이 절대로 다른 interpolation instants에 영향을 주어서는 안 된다는 것이죠.

아래 그림은 기본적으로 사용되는 $I(t)$입니다. 하나씩 하나씩 살펴보겠습니다.

Zero-order $I(t)$ and First-order $I(t)$

Zero-Order Hold

가장 쉽게 생각할 수 있는 interpolation 방식은 piecewise-constant interpolation입니다. 즉, 샘플값 사이를 상수로 interpolation 하는 것이죠: $$x(t) = x[n], \quad \text{for} \quad\left(n-\frac{1}{2}\right)T_s\leq t \leq \left(n+\frac{1}{2}\right)T_s$$

Zero-order hold

Interpolation 함수가 불연속 함수기 때문에, 당연하지만 결과가 절대 부드럽지는 않습니다: $$I_0(t)=\text{rect}(t)$$

아래 첨자 0에서 알 수 있듯, $x(t)$ 값이 현재 discrete-time 샘플 값에만 영향을 받습니다. 

First-Order Hold

그 다음으로 생각해볼 수 있는 interpolation은 선형 interpolator가 되겠습니다. 두 샘플들 간에 일직선을 그어 보간을 하는 것으로 아래 그림과 같이 조금은 더 부드러운 모습을 볼 수 있죠. 

$$ I_1(t)=\begin{cases} 1-|t| \quad \text{if}~|t|<1 \\  0 \quad\qquad \text{otherwise} \\ \end{cases} $$

First-order hold

Higher-Order Interpolators

$I_0(t)$와 $I_1(t)$는 각각 zero-order와 first-order B-spline 함수라고 불리는데요. 이를 $N$-th-order로 확장한 것이 $t$에 대한 $N$-th-order polynomial $I_N(t)$이며 앞선 예시에서 유추할 수 있듯이 order가 커질수록 더 부드러운 보간이 가능해집니다.

이러한 local interpolation의 장점은 실제 적용이 간단하다는 점이지만, N번째 미분부터는 불연속 함수가 되기 때문에 그 이상의 부드러운 보간이 불가능하다는 단점이 존재합니다. 이를 spectral 관점에서 얘기하자면, 불연속성이 곧 high frequency에 대응하고 이는 보통 원치않는 결과를 부르기 때문에 여러가지 의미에서 좋지 않습니다.

Polynomial Interpolation

Local interpolation에서 문제가 되는 lack of smoothness는 우리가 유한한 길이의 discrete-time 샘플들을 보간해야한다면 쉽게 우회할 수 있습니다. 이렇게 신호의 범주를 유한한 길이로 제한을 두는 순간, 이 문제는 전통적인 polynomial을 이용한 보간 문제로 치환이 가능해지고 우리는 이에 대한 optimal solution을 알고 있습니다: Lagrange interpolation.

Polynomial interpolation이 좋은 점은 유한한 갯수의 점에 대한 polynomial interpolation은 모든 미분에 대해 언제나 연속을 보장한다는 것이죠. 즉, interpolated 함수가 maximally smooth한 함수가 된다는 강력한 장점을 갖고 있다는 것! (polynomials are infinitely many times differentiable.)

$2N+1$ 길이의 discrete-time signal $x[n],~(n=-N\cdots,N)$을 생각해보겠습니다. 모든 $2N+1$ 점 $(t_n,x[n])$을 지나는 $2N$-차 polynomial $P(t)$는 유일(unique)하고, 이는 Lagrange interpolator라는 것은 잘 알려져 있습니다.
** $P(t)$의 existence는 construction 자체로 자명하고 uniqueness 증명은 contradiction으로 쉽게 알 수 있다.

이런 polynomial의 coefficients는 다음과 같은 $2N+1$개의 방정식을 풀면 구할 수 있으며: $$\{P(t_n)=x[n]\}_{n=-N,\cdots,N}$$ 이보다 더 쉬운 방법은 $P(t)$를 $2N+1$ 개의 Lagrange polynomials (of degree $2N$)로 나타내는 것입니다: $$\begin{align*}L^{(N)}_n(t) &=\prod_{\substack{k=-N\\k\neq n}}^N \frac{t-t_k}{(t_n-t_k)} \\
&=\prod_{\substack{k=-N\\k\neq n}}^N \frac{t/T_s-k}{(n-k)}, \quad n=-N, \cdots, N\end{align*}$$ 이런 polynomial이 글 서두에 소개한 식 (2)의 interpolation의 성질을 만족하는 것은 자명합니다. 예를 들어 점 4개를 보간할 때 $L^{(N)}_n(t)$를 보면 아래 그림과 같습니다 (wikipedia의 그림이 좋아 그대로 빌려왔기에 notation이 안 맞을 수 있습니다.) :

$P(x)$ (dashed, black), which is the sum of the scaled basis polynomials $y_0ℓ_0(x), x_1 ℓ_1(x), y_2ℓ_2(x),~and~~y_3 ℓ_3(x)$. The interpolation polynomial passes through all four control points, and each scaled basis polynomial passes through its respective control point and is 0 where x corresponds to the other three control points. 

Wikipedia "Lagrange polynomial"

따라서 "global" Lagrange interpolator는 Lagrange polynomial들의 선형 조합으로 표현되며: $$P(t)=\sum_{n=-N}^Nx[n]L^{(N)}_n(t)$$ 여기서 global은 $x(t)=P(t)$는 interpolation을 할 때 언제나 모든 샘플들을 고려한다는 뜻입니다. 즉, 유한한 길이를 가진 discrete-time 신호 $x[n]$에 대해 Lagrange polynomials는 global interpolating 함수이며 이렇게 보간된 함수 $x(t)$는 maximally smooth합니다 ($x(t)\in C^\infty$).

Sinc Interpolation

본격적으로 Sinc interpolation에 대해 알아보기에 앞서, 지금까지 살펴본 local & global interpolation에 대해 장단점을 비교해보겠습니다.

Local interpolation 방식의 멋진 점은 interpolated 함수가 interpolation 함수 $I(t)$의 shifted version들 간의 선형 조합으로 표현할 수 있다는 것이죠: "An interpolated function is simply a linear combination of shifted versions of the same prototype $I(t)$." (식 (1)을 보라) 다만 smoothness에 한계가 있다는 단점이 있겠습니다.

반면에 polynomial interpolation은 완벽하게 부드러운 보간이 가능하지만 finite-length 신호에 대해서만 적용이 가능하며 다른 길이를 갖는 신호에 대해 서로 다른 interpolation 함수가 필요하다는 단점이 있습니다.

이 두 가지 방식의 장점만 쏙쏙 빼면 참 좋을텐데...에 대한 답이 바로 Sinc Interpolation입니다! 이제 지금까지 설명한 내용들을 바탕으로 infinite discrete-time 신호에 대해 maximally smooth한 interpolation 방법을 소개할 준비가 되었습니다.

앞서 살펴본 Lagrange polynomial of degree N에 대해 N을 무한대로 보내면: $$\begin{align*} \lim_{N\rightarrow\infty}L_n^{(N)}(t) &= \prod_{\substack{k=-\infty\\k\neq n}}^\infty \frac{t/T_s-k}{n-k} = \prod_{\substack{m=-\infty\\m\neq0}}^\infty \frac{t/T_s-n+m}{m}\\
&=\prod_{\substack{m=-\infty\\m\neq0}}^\infty \left(1+\frac{t/T_s-n}{m}\right)\\
&=\prod_{m=1}^\infty \left(1-\left(\frac{t/T_s-n}{m}\right)^2\right)\\
\end{align*}
$$
두번째 등호는 $m=n-k$를 사용하여 변수를 치환한 것입니다. 이후 전개는 아래와 같은 sine 함수에 대한 오일러의 infinite product expansion을 사용할 것인데: $$sin(\pi\tau) = (\pi\tau) \prod_{k=1}^\infty\left(1-\frac{\tau^2}{k^2}\right)$$ 이를 정리하면 최종적으로 아래 식을 얻을 수 있습니다: $$\lim_{N\rightarrow\infty}L_n^{(N)}(t) = \text{sinc}\left(\frac{t-nT_s}{T_s}\right) $$
포인트는 차수가 증가할 수록 Lagrange polynomial $L_0^{(N)}(t)$는 점차 sinc 함수로 수렴한다는 것인데요. 즉, 점의 갯수가 무한이 되면서 모든 Lagrange polynomial은 각각 sinc 함수에 대한 shifted version으로 수렴하게 된다는 점입니다. 따라서 식 (1)과 같이 $I(t)=sinc(t)$를 사용하여 무한수열 x[n]에 대해 $$x(t)=\sum_{n=-\infty}^\infty x[n] sinc\left(\frac{t-nT_s}{T_s}\right)$$로 표현하는 것이 가능해집니다.

Spectral Properties of the Sinc Interpolation

Interpolation을 할 때 주안점을 둘 부분이 바로 spectral 영역에서 interpolated 신호가 어떤 식으로 달라지는지 확인하는 것이라고 말한 바 있습니다. 이제 이게 어떤 의미인지 얘기할 준비물이 대략 갖춰졌습니다.

지금까지 interpolation 방법들 여럿을 살펴보았으나 일반화하면서 결국 마지막에 다다른 것은 Sinc interpolation입니다. 이렇게 얻은 Sinc interpolation은 spectral 영역에서 보면 재미있는 분석이 가능해지는데, 간단히 말하면 시간 영역의 Sinc 함수에 대응하는 주파수 영역의 형태는 ideal low-pass filter로써 0을 기준으로 한 사각형 박스처럼 생겼습니다.

그러므로 discrete-time sequence에 대한 Sinc interpolation은 continuous-time 신호가 band-limited low-pass filtering이 된 것과 정확히 일치합니다 (수식적으로도 그러하다). 즉, DTFT $X(e^{j\omega})$가 존재하면 interpolated function $X(j\Omega)$의 spectrum은 다음과 같이 얻을 수 있습니다: $$\begin{align*}X(j\Omega)
&= \int^\infty_{-\infty} \sum_{n=-\infty}^\infty x[n] sinc \left(\frac{t-nT_s}{T_s}\right) e^{-j\Omega t} dt\\
&= \sum^\infty_{n=-\infty} x[n] \int_{-\infty}^\infty sinc \left(\frac{t-nT_s}{T_s}\right) e^{-j\Omega t} dt \\
\end{align*}$$
Sinc 함수에 대한 Fourier Transform을 해주고 여기에 $T_s = \pi/\Omega_N$를 대체하면,
$$\begin{align*}X(j\Omega)
&= \left(\frac{\pi}{\Omega_N}\right)\text{rect}\left(\frac{\Omega}{2\Omega_N}\right)\sum_{n=-\infty}^\infty x[n]e^{-j\pi(\Omega/\Omega_N)} \\
&= \begin{cases} \frac{\pi}{\Omega_N}X(e^{-j\pi\Omega/\Omega_N}) \quad \text{for}~|\Omega|\leq\Omega_N \\ 0 \qquad \qquad\qquad\quad \text{otherwise}\end{cases}\end{align*}$$이를 다르게 말하면, 임의의 continuous-time 신호가 애초부터 bandlimited 신호인 경우 이 신호에 대한 적절한 sampling을 하므로써 어떠한 정보 손실도 전혀 없이 discrete-time 신호를 얻는 것이 가능하다는 뜻입니다.

이런 사실은 이후에 Fourier transform을 살펴본 다음에 자명하게 수식적으로 보일 수 있겠지만, 이렇게 미리 살짝 엿보는 것까지는 굳이 복잡한 Fourier transform 내용을 배우지 않고도 가능합니다.

이제 신호처리 초반에 왜 여러가지 복잡한 내용을 공부하는지 그리고 어째서 Sinc 함수와 같이 이상하게 생긴 것을 굳이 배워야하는지 조금은 감이 생기셨으리라 생각합니다.

여기에 대한 더 자세한 설명 및 Sampling Theorem 그리고 Aliasing 현상에 관한 내용은 Fourier transform 등의 수학적 도구를 더 든든히 갖춘 다음에 돌아와 살펴보겠습니다.

To be continued ... (planned)

• Preface
• What is Digital Signal Processing? (1)
• Discrete-Time Signals (2 $\leftarrow$ next to read)
• Signals and Hilbert Spaces
• Fourier Analysis
• Interpolation and Sampling (9-1 $\leftarrow$)
• Interpolation 
• Sampling theorem
• Aliasing
• Multirate Signal Processing
• Downsampling
• Upsampling
• Oversampling

참고 문헌

• https://math.stackexchange.com/questions/1343904/are-polynomials-infinitely-many-times-differentiable
• https://www.youtube.com/watch?v=ygcQJqcHdOM
• http://home.iitk.ac.in/~pranab/ESO208/rajesh/03-04/interpolation.pdf

Signal Processing For Communications (0)

이 시리즈는 signal processing을 학부 때 배웠으나 여러 이유로 이해를 잘 하지 못하다가 뒤늦게서야 유용성을 깨닫고 개인적으로 공부하며 정리한 흔적입니다.

어느날 문득 결국 machine learning을 하든 deep learning을 하든 모두 신호를 다루기 위한 도구일 따름이고, 주로 다루는 신호가 이미지라는 형태를 띄고 있을뿐 근본적으로 디지털 신호 처리에서 다루는 내용에서 벗어나지 않는다는 생각이 들었습니다.

이런 맥락에서 신호 처리에 대해 좀 더 잘 알고 싶다는 생각에 정리를 시작하였는데, 대부분의 글은 주로 EPFL의 Martin Vetterli 교수님의 textbook을 기반으로 요약하되 제가 여기저기서 찾아 이해한 내용들로 주석을 달거나 내용을 추가했습니다.

앞으로 쓸 글들은 (얼마나 걸릴지는 모르겠지만) 모두 신호처리의 기본에 대해 대학교 학부생을 위한 기초 수준으로 작성될 것입니다. 제 스스로가 그 이상을 설명할만큼 잘 알고 있다고 생각하지도 않는만큼, 차후 시간이 흘러 다시 이 글을 봤을 때도 이해가 쉽게 하겠다는 목적을 갖고 글을 정리해보고자 합니다.

약간의 선형대수학, 신호처리에 대한 기초 지식 그리고 더 나가서 해석학을 들어본 적이 있다면 보다 깊은 이해에 도움이 될 것이지만, 그런 선행 지식이 없이도 어렵지 않게 이해할 수 있는 수준으로 작성하고자 노력하였습니다.

간단한 예시 그리고 덜 형식적인 설명을 바탕으로 신호처리라는 딱딱한 주제에 대해 쉽게 접근할 수 있도록 작성하였으며, 이해하기 쉬운 설명을 위해 수학적 엄밀성 강조하지는 않겠지만 최소한 틀리지 않는 정확한 설명을 하는 것에 주안점을 두었습니다. 계획된 목차는 아래와 같습니다.

목차 (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 (3-2)
• Fourier Analysis
• Interpolation and Sampling (9-1) 
• Interpolation
• Sampling theorem
• Aliasing
• Multirate Signal Processing
• Downsampling
• Upsampling
• Oversampling

다만, 꼭 순서대로 글이 작성되리라는 보장은 없으며, 각 글의 제목 뒤에 붙은 숫자는 책에서 해당 내용이 다뤄진 chapter를 따랐습니다. 따라서 모든 chapter를 정리하지는 않을 예정이므로 숫자가 다 채워질 이유도 순서대로 나열될 이유도 없지요. 이 preface 글의 목차는 글을 써가면서 매번 업데이트 될 예정입니다.

마찬가지로 읽는 분도 원하시는 것만 골라 읽으실 수도 있을 것이고, 순서대로 차근차근 읽으실 수도 있을 것이나, 제가 염두에 두고 쓴 순서를 추천드리자면, 먼저 (1)을 읽으시고 (9-1)로 넘어가신 후 다시 (2)로 돌아가서 쭉 순서대로 읽으시는 것을 권해드립니다. 개인적으로는 그렇게 하는 것이 신호처리를 배우는 목적을 이해하고 전체적인 감을 잡는 것에 훨씬 도움이 된다고 생각합니다.

현재 이 글은 서문과 같은 역할이므로 chapter 0라 임의로 칭했고, 따라서 제목이 다음과 같습니다; Signal Processing For Communications (0)

Signal Processing For Communications (1)

What Is Digital Signal Processing?

신호(signal)와 신호 처리(signal processing) 대해서 정의를 내리자면 각각 다음과 같습니다:

신호: 시간 혹은 공간에 대해 변화하는 현상에 대한 formal description
신호 처리: 신호에 들어있는 정보를 바꾸거나 분석하는 any operation.

예를 들어 주변 온도를 우리가 Celsius degree라는 물리적 변수를 기준으로 시간에 따른 온도의 변화를 기록하는 경우, 이렇게 만들어진 data set은 온도 "신호"가 될 것입니다. 이 신호에 대한 가장 단순한 "처리"로는 월간 온도 평균과 같은 어떤 파라미터를 계산하는 것이 있겠죠.

또한 신호 처리는 어떤 물리적인 값 자체에 직접 가해지는 것이 아니라 물리적인 값의 "abstract representation"을 기반으로 수행된다는 점이 중요합니다. 이런 abstract representation의 방식에 따라서 신호 처리의 기본 단위(unit)가 정해지게 됩니다.

한편 "디지털 (digital)"이라는 수식어구는 라틴어 digitus에서 유래한 것으로 손가락을 의미하는데, counting은 가장 기초적이고 오래된 abstraction이라 합니다. 즉, 디지털 신호 처리는 시간을 포함한 모든 것들에 정수(integer number)와 같이 countable한 abstraction representation을 사용한다는 것을 의미합니다.

좀 더 구체적 예시로는, 주변 온도를 측정한 각각의 관측(instants)이 셀 수 있는 집합(the days in a month)을 이루고 각 관측값(measure)들 역시도 온도계의 눈금 단위와 같이 유한한 수의 집합으로 표현되는 것을 생각해보면 되겠습니다.

재미있는 점은 디지털 신호 처리에서는 신호가 "어디서 유래한 것인가에 관계없이" 이를 "정수로 표현 가능한" abstract representation을 사용한다는 것인데요. 지금 당장은 이 사실이 별달리 중요해보이지 않을 수 있으나, 이 특징이 디지털 신호처리가 지금과 같이 크게 발전할 수 있었던 큰 동력이라는 점은 차차 글이 진행됨에 따라 분명해지리라 생각합니다.

Analog vs. Digital worlds

세계에 대한 "digital" 혹은 정수를 이용한 표현 방식은 우리가 다루는 문제가 가축이나 날짜를 세는 것과 같이 간단할 때까지는 아무 문제가 없이 잘 동작했으나, 점차 세상이 복잡해지고 이를 설명하는 모델 역시도 복잡해질 필요가 생기면서 한계에 부닥쳤습니다.

신호 처리 쪽 용어로 얘기하자면, 정수로 표현되는 세계가 "analog"와 같이 연속적인 세계를 설명하는 잣대로 사용하기에는 너무 초보적이고 거칠어서 마치 정밀한 시계를 다루는 시계공이 못을 박는 망치를 들고 있는 것과 같다는 것입니다.

문제는 무한대와 무한소로 나눠질 수 있는 연속적인 analog 세계의 analytical 모델을 사용하면 이론적으로 분석하기는 편할지언정, 실제로 이를 사용하기 위해서는 언제나 유한하고 이산적인 digital 세계로 내려와야한다는 점입니다.

예를 들어 온도를 측정하는 것만해도, 우리가 얻을 수 있는 것은 언제나 일정 간격(time)을 두고 측정한 관측값들일 뿐 임의의 시간에 대해 해당하는 온도에 대한 관계를 보여주는 analytical 모델이 아니죠.

따라서 analog와 digital representation이 서로 만족할만한 합의에 이르기 위해 부단한 노력들이 있어 왔고, series expansion이나 numerical integration 등의 알고리즘들이 analytic 결과를 practically computable한 형태로 만들기 위한 노력의 예시들이라 하겠습니다.

디지털 신호 처리가 멋진 것은 이렇게 양분된 두 세계가 서로 가장 만족스러운 형태로 합의에 이를 수 있도록 한다는 점입니다.

Discrete Time

아날로그 기록 방식의 가장 큰 문제점은 신호를 추상화 하여 기록하는 것이 아닌 하나의 물리적인 현상을 또 다른 물리적 현상으로 옮기는 것에 불과하다는 점인데요. 이 때문에 근본적으로 아날로그 신호는 기록(recording)의 형태에 따라 각각 다른 신호 처리 시스템이 필요하게 됩니다. 예를 들어 우리가 온도 변화 함수 $f(t)$를 알고 있고,

Analytical and empirical averages

일정 간격 $[T_0, T_1]$ 사이에 일어난 온도 변화의 평균값을 알고싶다면 이에 대한 analytical solution은 다음과 같은 적분 방적식을 푸는 것이 됩니다: $$\bar{C} = \frac{1}{T_1-T_0}\int_{T_0}^{T_1} f(t) dt.$$ 그러나 analytic model이 없는 현실에서는 어떤 기기를 사용하여 온도를 측정, 기록하였을 것이고 그 데이터를 가지고 평균 온도를 계산할텐데요. 만약 온도가 thermograph를 이용하여 그래프의 형태로 기록되었다면 plainmeter라는 면적을 구하는 기계적 도구를 사용하여 면적을 알 수 있을 것입니다. 그러나 온도 변화가 thermocouple과 같이 전압을 이용하여 기록을 하는 경우 학부 전자기초 시간에 배우는 RC 네트워크로 voltage integration 회로를 만들어 평균값을 계산해야 할테죠. 이렇듯 아날로그 신호에서는 평균을 구하는 매우 단순한 예에서도 각 경우마다 특정한 디자인이 필요하기에 범용적으로 사용할 수 있는 방식을 고안하기 어렵다는 것을 알 수 있습니다.

한편, 디지털 방식과 같이 하루에 한 번씩 측정한 온도에 대해 평균을 구하는 것은 매우 쉽습니다: $$\hat{C}=\frac{1}{D}\sum^D_{n=1}c_n.$$ 단순히 초보적인 덧셈과 나눗셈만 수행하면 원하는 값을 얻을 수 있죠! 그렇다면,

"$\bar{C}$와 $\hat{C}$의 차이가 (만약 있다면) 얼마나 될까요?"

만약 저 자연계 어딘가에 $f(t)$라는 온도 함수가 있다는 것을 받아들인다면 하루 주기($T_s$)마다 측정한 $c_n$ 온도 측정값들은 이 함수의 $samples$라고 할 수 있습니다: $$c_n=f(nT_s).$$ 이런 맥락에서 보면 $\hat{C}$는 $\bar{C}$의 Riemann approximation이라고 할 수 있으며 앞선 질문은 이 approximation의 질 즉, continuous-time 함수에서 일부 샘플들만 취함으로써 우리가 얼마나 정보를 버렸는지에 대해 묻는 것과 같습니다.

이에 대한 정답은 놀랍게도 해당 물리적 현상이 "그렇게 빨리 변하지 않는다"는 가정 하에, 두 representation이 "완벽히 일치한다"는 것입니다. 즉, continuous-time function과 우리가 얻은 측정 샘플들 간의 정보 손실이 전혀 없다는 뜻이죠.

잠시 가정에 대한 걱정을 내려놓고, 이 사실이 얘기해주는 것에만 집중해보면 매우 놀랍게도

1. 아날로그와 디지털 세계가 완전히 공존하는 것이 가능하다는 뜻이며 
2. 우리가 두 세계 사이를 오갈 수 있는 매우 강력한 도구를 갖고 있다는 것입니다 (sampling theorem). 

20세기 초에 발견된 이 놀라운 정리는 우리가 가진 샘플들을 바탕으로 임의의 continous-time function를 알아내는 것이 가능하다는 것을 말해주는데요:
$$f(t)=\sum_{n=-\infty}^\infty c_n \frac{\sin(\pi(t-nT_s)/T_s)}{\pi(t-nT_s)/T_s}.$$ 따라서 이론적으로는 우리가 측정값들을 가지고만 있다면 이를 바탕으로 continous-time 형태로 표현하는 것이 가능하며, 이것은 이어서 우리가 갖고 있는 매우 강력한 수학적 도구인 미분을 사용하여 함수를 분석하는 것이 가능해진다는 것을 뜻합니다.

더 좋은 점은 continous-time에서 이루어진 미분과 같은 분석이 항상 discrete-time에 대응하는 방식이 존재하여 굳이 우리가 얻은 측정값들을 가지고 continous domain으로 옮겨서 분석한 후, 다시 discrete domain으로 내려오는 복잡한 방식을 취할 것 없이 discrete domain에서 바로 분석을 하면 된다는 것입니다.

Discrete과 continuous representations 사이의 equivalence는 우리가 샘플을 얻는 속도에 비해 다루는 신호가 얼마나 충분히 "느린가"에 달려 있습니다. 즉, 연속된 샘플을 측정하는 사이에 신호가 갑자기 이상하게 움직이지 않고 충분히 부드럽게 (smooth and well behaved) 움직인다면 문제가 없다는 뜻입니다.

그래서 sampling theorem이 해주는 역할은 (좀 더 쉽게 설명하자면) 신호가 갖는 최대 주파수와 우리가 얼마나 자주 혹은 빨리 샘플을 얻어야 하는지에 대한 정량적인 기준을 알려주는 것입니다. 대다수의 학부 수준 디지털 신호 처리 과목의 반절 혹은 그 이상은 이 sampling theorem을 배우기 위한 준비와 theorem의 의미에 대해 공부하는 것이겠습니다. 특히 주파수 영역은 Fourier transform을 사용하여 알아낼 수 있기에 이를 신호 처리 과목에서 중요하게 다루며 배우는 것이라 할 수 있는데, 재미있는 점은 Fourier transform이라는 것 자체가 주기성을 띄는 함수들을 "셀 수 있는" 값들로 표현하기 위한 도구로서 사용된다는 것입니다. 도구만 달라졌을뿐 앞에 손가락으로 숫자를 세던 것이 생각나지 않으시나요?

"Everything comes together."

Discrete Amplitude

시간 연속성에 대한 문제는 sampling theorem으로 어느 정도 해결이 되었지만, 여전히 남아있는 문제가 하나 있습니다. 현실 세계의 한계로 인해 실제 측정을 할 때 생기는 오차는 우리가 어찌 할 수 없는 문제이지요.

만약 우리가 analytical model을 다룬다면 시간축뿐만 아니라 함수 값 역시도 연속적인 성격을 갖고 있는데요. 그러나 현실에서는 절대로 이와 같은 무한대의 정밀성을 얻을 수 없다는 것은 자명합니다. (아무리 온도계의 눈금을 잘게 쪼개어 기록을 하더라도 한계가 있는 것처럼)

따라서 실제로는 우리가 얻는 측정값들도 결국 유한한 숫자들의 집합이고, 그렇다면 이들은 셀 수 있기에 정수로 mapping하는 것이 가능해집니다. 이러한 과정을 quantization이라고 부르고 이는 sampling과 함께 digital signal을 얻는데 필수적인 요소가 되는데요.

Quantization은 정보 손실을 어쩔 수 없는 것으로 받아들인다는 점에서 연속체 문제를 시간에 비해 매우 거칠게 해결하는 것이라 할 수 있습니다. 여기에는 그럴 수 밖에 없는 이유가 있는데 그게 바로 신호 처리를 하다보면 언제나 만나게 되는 "noise"입니다.

우리가 어떠한 기계적 기록 장치를 쓴다고 해도 아날로그 기록을 하는 기기라면 언제나 noise가 함께하게 됩니다. Noise는 자연에서 오는 것이고 이를 완전히 제거하는 것은 불가능하기 때문에 신호 처리를 할 때 일정 수준의 정밀성으로 만족하는 정도로 합의를 하는 것이죠.

문제는 noise가 단순히 측정에서만의 문제가 아니라 처리를 할 때도 함께한다는 점입니다.
여기서 디지털 신호 처리의 또 다른 장점이 나오는데, 디지털 신호 처리는 언제나 셀 수 있는 정수의 수열을 다루기 때문에 디지털 영역에서는 processing으로 인한 noise가 생기지 않습니다.

매우 자명한 예로 신호를 복제하는 것을 생각해보면, 테이프를 복사하는 것은 원본 테이프를 복사본과 그 복사본을 이용한 다음 복사본으로 넘어갈 때마다 추가적인 nosie가 더해져서 점점 음질이 열화되지만 mp3의 경우 원본과 복사본이 근본적으로 차이가 없다는 것을 알 수 있습니다.

Terminology

마지막으로 용어에 대해 한가지 짚고 넘어가겠습니다. Amplitude에 대한 정확성은 사실 하드웨어에 달린 문제로, 예를 들자면 CD와 DVD는 서로 precision 즉 샘플 당 담을 수 있는 정보량에 차이가 있습니다. 이렇게 amplitude에 대한 정밀성은 하드웨어에 의존적이므로 사실상 신호 처리 이론에 대해 배우거나 개발할 때는 quantization을 고려하지 않고 마치 연속된 실수 값인 것 마냥 취급하게 됩니다. 따라서 사실상 우리가 앞으로 배우는 것은 엄밀히 말하자면 모두 discrete-time signal processing이라 불러야 맞고 digital signal processing은 실제 기기의 영역에서 이뤄지는 일임을 알아야 합니다. 그러나 quantization을 고려하지 않는 것이 좀 더 이론적으로 다루기도 쉽고 일반적인 분석이 가능하기 때문에 이를 잘 구별하지 않고 digital signal processing이라 얘기한다는 점을 분명히 알아야겠습니다.

아 마지막으로 글을 읽는데 순서를 추천드리자면 이 다음에 (9-1)로 넘어가시는 것을 권해드립니다. 그렇게 하는 것이 신호처리를 배우는 목적을 이해하고 전체적인 감을 잡는 것에 훨씬 도움이 된다고 생각합니다. 

To be continued ... (planned)

• Preface 
• What is Digital Signal Processing? ($\leftarrow$)
• Discrete-Time Signals (2)
• Signals and Hilbert Spaces
• Euclidean Spaces and Hilbert Spaces (3-1) 
• Subspaces, Bases, Projections, Haar basis (3-2)
• Fourier Analysis
• Interpolation and Sampling (9-1 $\leftarrow$ next to read)
• Interpolation
• Sampling theorem
• Aliasing
• Multirate Signal Processing
• Downsampling
• Upsampling
• Oversampling