78fa

그래프 이론 용어: https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0_%EC%9A%A9%EC%96%B4

해밀턴 경로 (Hamiltonian path): 모든 꼭지점(<-꼭짓점이라고 쓰이기도 하나 여기서는 꼭지점으로 통일)을 단 한번씩 방문하는 경로.

경로(path)와 보행(walk)의 차이에 유의: 경로는 방문하는 꼭지점이 중복될 수 없지만 보행은 중복될 수 있음. 여기서 보행은 같은 꼭지점을 연달아 이어서 방문하는 보행은 포함하지 않음.

$|V|$ 는 그래프 꼭지점의 총갯수를 가르킴.

$A_{\omega }e^{i\omega t}$ 의 $\omega$ 를 각주파수라고 부름.

논문의 두가지 목표:

1. 방향성이 없는 그래프 (<- 즉 그냥 일반 그래프)를 $f(t)$ 로 시그널로 바꾼 뒤, 이 f(t)의 제로 주파수 값이 해밀턴 경로 (Hamiltonian path)의 갯수가 되도록 만들어 주는 것. $f(t)=\sum _{\omega }A_{\omega }e^{i\omega t}$ 여기서 $\omega$ 는 보행(walk)의 각 꼭지점의 방문 횟수를 담고 있는 숫자. 여기선 보행의 각 꼭짓점 방문 횟수를 모두 더했을 때 꼭짓점의 갯수, 즉 $|V|$ 가 되는 경우에만 한정함. 이 $\omega$ 를 알면 각 꼭지점 방문 횟수를 유추할 수 있도록 만드는 것.

$A_{\omega }$ 는 같은 꼭지점의 방문 횟수를 똑같이 공유하는 보행 (walk)의 갯수로 만드는 것.

이것을 어떻게 실현시킬 것인가?

답: 각 꼭지점 (vertex) $i$ 에 $|V|^{i}$ 란 고유 각주파수(angular frequency)를 부여하고 경로의 꼭지점 $i$ 방문횟수가 $a_{i}$ 라면 경로 $p$ 의 각주파수를 $p_{\omega }=\sum _{i}a_{i}|V|^{i}$ 로 만들어주면 됨.

예를 들어 그래프의 꼭지점 갯수가 4개라면, 첫번째 꼭짓점에는 각주파수 (angular frequency) 4를, 두번째 꼭지점엔 $4^{2}=16$ 를, 세번째 꼭지점엔 $4^{3}=64$ 네번째 꼭지점엔 $4^{4}=256$ 를 부여함. 그러면 보행의 총 꼭지점 방문횟수를 $|V|=4$ 로 제한시, 같은 꼭지점을 연달아 방문할 수 없기 때문에 모든 $|V|=4$ 의 총방문횟수를 강진 경로들이 고유한 각주파수/주파수를 가지게 됨.

그렇다면 그래프로부터 어떻게 $x(t)$ 를 쉽게 계산할 것인가? 그 도식이 이 이메일 타래 첫번째 이메일 첨부파일 66페이지의 그림임. 간단히 요약하면 이 원리임: 여기서 $i$ 는 복소수를 가르킴. $(e^{iv_{1}t}+e^{iv_{2}t})e^{iv_{3}t}=e^{i(v_{1}+v_{3})t}+e^{i(v_{2}+v_{3})t}$ -> 즉, 이건 $v_{1}$ 각주파수를 가지고 있는 꼭지점 1과 $v_{3}$ 각주파수를 가진 꼭지점 3이 연결된 보행과 꼭지점 2와 3이 연결된 보행을 합쳐놓은 식이 되는 건데 앞의 수식은 그 뒤 수식보다 빠르게 처리할 수 있음.

이렇게 만들 수 있는게 x(t)인데 여기서 이 x(t)의 시간축/주파수축을 조절하고 해밀턴 경로의 주파수를 0으로 옮겨주면 f(t)가 탄생함. (각주파수 대역을 -1에서 1사이로 바꾸는 작업)

2. 이 f(t)를 계속 가공해서 (전문 용어론 필터링해서) 제로 주파수 값을 알아내는 방법. 이게 어려운 부분임.

요약하면 f(t)의 각주파수 1/2 (-1/2) 에서 1(-1) 영역을 필터 H로 걸러내고 얻어진 아웃풋 샘플을 이용해 추가 샘플을 "추측"(extrapolate)하고 얻어진 샘플을 1,3,5,7,9,..등 중간에 한개씩을 버려서 주파수를 두배로 높인 뒤에 다시 이 샘플들을 필터 H로 걸러내고 또다시 아웃풋 샘플을 이용해 추가 샘플을 추측하고 얻어진 샘플 중 중간에 한개씩을 버린 뒤...를 계속 반복. 이렇게 하면 각주파수 1/2~1, 1/4~1/2, 1/8~1/4을 순차적으로 걸러내면 0을 제외한 마지막 주파수 영역까지 모두 필터링 됨.

그런데 왜 이렇게 필터링 해야되는 가? 이유는 0을 제외하고 나타나는 첫번째 각주파수가 $1/|V|^{|V|}$ 인데, 최대 각주파수가 1이고, 이 영역대를 하나의 디지털 필터가 처리하면 너무나도 많은 f(t)의 샘플을 요구함. 따라서 1/2~1까지 각주파수 영역을 처리하는 필터를 쓰면 필요한 샘플의 숫자를 줄일 수가 있음.

문제는 이럴 경우 우리가 얻어진 필터링 완료된 아웃풋 샘플을 가지고 다음 싸이클에서 필요한 갯수의 샘플만큼을 얻어내야 하는데, 이게 골치아픈 작업임.

어떻게 할 것인가?

각 샘플 간 시간 차가 $\Delta t=1$ 라고 가정함. 예를 들어 $g(t)$ 가 우리가 추측하고 싶은 샘플일 때, $g(t-N_{d}),g(t-N_{d}+1),g(t-N_{d}+2),..g(t-1)$ 까지 샘플이 있으면 이 샘플들을 derivative 필터 (미분 필터)로 집어넣어서 $g'(t-1),g''(t-1),...g^{(N_{\mu }}(t-1)$ 값의 "오차범위" 내 값을 알아냄. 이를 통해 Taylor theorem을 이용해 $g(t)$ 의 추론 값 $g_{n}(t)$ 를 구함. 그 다음 $g(t+1)$ 는 $g(t-N_{d}+1),..,g_{n}(t)$ 를 통해 같은 방법으로 추론된 미분값을 알아내고 이를 통해 $g_{n}(t+1)$ 를 구하고.. 이를 계속 반복하는 거임.

그런데 이게 $t-1$ 에서 추론된 미분값으로 모든 t의 g(t) 값을 추론하는 것과 어떻게 다른 가? 핵심은 우리가 계속 각 t에서 미분값을 재추론함으로서 고주파수 영역으로 인한 미분값 에러를 상쇄시킬 수 있다는 거. 또한 우리가 미분 필터를 각 t에서 계속 이용하기 때문에 미분값 에러와 추론 에러 조차 사인 함수들로부터 나온 것으로 해석시킬 수 있다는 거. 만일 t-1에서 추론된 미분값으로 Taylor theorem를 그대로 써먹으면 에러값은 다항식 형태로밖에 표현이 안 되고, 그러면 사인 함수의 꺾임을 이용할 수 없으며 다항식의 가파른 값 증가 속도란 불이익을 그대로 떠안게 됨.

나머지는 이 아이디어를 수리적으로 더 풀어서 증명하려는 시도인데, 어느만큼 성공적이었는지는... 뭐 시간과 결과가 알려주겠지.