29차시 · 그래프 푸리에
그래프 위의 값은 어떻게 매끄럽게 만들까?
라플라시안은 각 꼭짓점의 값과 이웃 값의 차이를 동시에 계산한다.
이웃 차이 계산
\(P_4\)에서 \(x=(1,2,0,1)^\mathsf T\). \((Lx)_2\)는?
둘째 꼭짓점의 이웃: \(v_1,v_3\), 차수는 2
\[L=\begin{bmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{bmatrix},\qquad Lx=\begin{bmatrix}-1\\3\\-3\\1\end{bmatrix}\]
정의와 성질
그래프 라플라시안 \(L=D-A\)
- \(D\): 꼭짓점 차수를 대각에 놓은 행렬
- \(A\): 인접행렬
- 무방향 그래프에서는 \(L=L^\mathsf T\)
\[L\mathbf1=0\]
\[x^\mathsf TLx=\sum_{\{i,j\}\in E}(x_i-x_j)^2\ge0\]
연결그래프에서 고윳값 0의 고유공간은 상수벡터가 만드는 1차원 공간이다.
직접 조작
\(x^{(n+1)}=x^{(n)}-\tfrac14Lx^{(n)}\)의 반복
\[\bar x=\frac14\sum_{i=1}^4x_i=0.75\]
에너지 \(x^\mathsf TLx=6.00\)
각 단계에서 전체 합은 보존되고 이웃 차이는 감소한다.
고유벡터 기저
\(C_4\)의 낮은 주파수와 높은 주파수
\[\begin{aligned}q_0&=(1,1,1,1)\\Lq_0&=0\end{aligned}\]
모든 꼭짓점의 값이 같아 간선별 차이가 0이다.
순수수학 확장
순환이동의 고윳값은 1의 네제곱근
\[\begin{aligned}
S(x_0,x_1,x_2,x_3)&=(x_1,x_2,x_3,x_0)\\
\omega&=e^{2\pi i/4}=i\\
f_k&=\tfrac12(1,\omega^k,\omega^{2k},\omega^{3k})^\mathsf T\\
Sf_k&=\omega^k f_k
\end{aligned}\]
\[\begin{aligned}
L&=2I-S-S^{-1}\\
\lambda_k&=2-\omega^k-\omega^{-k}=2-2\cos(\pi k/2)
\end{aligned}\]
\(k=0\)\(\lambda_0=0\)
\(k=1,3\)\(\lambda=2\), 복소 켤레 쌍
\(k=2\)\(\lambda_2=4\)
응용과 확인
평균을 제거한 \(C_4\) 신호에서 가장 빨리 감쇠하는 모드는?
\[x'(t)=-Lx(t),\qquad c_k(t)=e^{-\lambda_k t}c_k(0)\]
확산은 평균을 보존하면서 높은 그래프 주파수 성분부터 제거한다.
핵심 정리
라플라시안의 고유벡터가 그래프의 주파수 기저를 이룬다.
- \(Lx\): 자기 값과 이웃 값의 차이
- \(\lambda=0\): 연결성분별 상수모드
- 작은 \(\lambda\): 매끄러운 모드, 큰 \(\lambda\): 빠르게 변하는 모드
- \(C_4\): 순환이동의 복소 푸리에 기저와 같은 주파수 구조
L=D−A확산그래프 푸리에