調和矩陣

在圖論中，調和矩陣（harmonic matrix），也稱拉普拉斯矩陣或拉氏矩陣（Laplacian matrix）、離散拉普拉斯（discrete Laplacian），是圖的矩陣表示。

調和矩陣也是拉普拉斯算子的離散化。換句話說，調和矩陣的縮放極限是拉普拉斯算子。它在機器學習和物理學中有很多應用。

## 定義

若G是簡單圖，G有n個頂點，A是鄰接矩陣，D是度數矩陣，則調和矩陣是

$$L = D - A$$

$$L_{i,j} := \begin{cases} <pre> \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise} </pre> \end{cases}$$

### 動機

這跟拉普拉斯算子有什麼關係？若f 是加權圖G的頂點函數，則

$$E(f) = \sum w(uv)(f(u)-f(v))^2 / 2 = f^t L f$$

w是邊的權重函數。u、v是頂點。f = (f(1), ..., f(n)) 是n維的矢量。上面泛函也稱為Dirichlet泛函。

### 接續矩陣

而且若K是接續矩陣（incidence matrix），則

$$K_{ev} = \left\{\begin{array}{rl} <pre> 1, & \text{if } v = i\\ -1, & \text{if } v = j\\ 0, & \text{otherwise}. </pre> \end{array}\right.$$

$$L = K^tK$$

Kf 是f 的圖梯度。另外，特徵值滿足

$$\begin{align} <pre> \lambda_i & = \mathbf{v}_i^\textsf{T} L \mathbf{v}_i \\ & = \mathbf{v}_i^\textsf{T} M^\textsf{T} M \mathbf{v}_i \\ & = \left(M \mathbf{v}_i\right)^\textsf{T} \left(M \mathbf{v}_i\right) \\ </pre> \end{align}$$

## 舉例

圖｜度矩陣｜鄰接矩陣｜調和矩陣

<image>

｜$\left(\begin{array}{rrrrrr} 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ \end{array}\right)$｜$\left(\begin{array}{rrrrrr} 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ \end{array}\right)$｜$\left(\begin{array}{rrrrrr} 2 & -1 & 0 & 0 & -1 & 0\\ -1 & 3 & -1 & 0 & -1 & 0\\ 0 & -1 & 2 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & -1\\ -1 & -1 & 0 & -1 & 3 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\\ \end{array}\right)$

## 其他形式

### 對稱正規化調和矩陣

$$L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$$

$$L^\text{sym}_{i,j} := \begin{cases} <pre> 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. </pre> \end{cases}$$

注意

$$<pre> \lambda \ = \ \frac{\langle g, L^\text{sym}g\rangle}{\langle g, g\rangle} \ = \ \frac{\left\langle g, D^{-\frac{1}{2}} L D^{-\frac{1}{2}} g\right\rangle}{\langle g, g\rangle} \ = \ \frac{\langle f, Lf\rangle}{\left\langle D^\frac{1}{2} f, D^\frac{1}{2} f\right\rangle} \ = \ \frac{\sum_{u \sim v}(f(u) - f(v))^2}{\sum_v f(v)^2 d_v} \ \geq \ 0, </pre>$$

### 隨機漫步

$$L^\text{rw} := D^{-1}L = I - D^{-1}A$$

$$L^\text{rw}_{i,j} := \begin{cases} <pre> 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. </pre> \end{cases}$$

## 動力學和微分方程

例如，離散的冷卻定律使用調和矩陣

$$\begin{align} <pre> \frac{d \phi_i}{d t} &= -k \sum_j A_{ij} \left( \phi_i - \phi_j \right) \\ &= -k \left( \phi_i \sum_j A_{ij} - \sum_j A_{ij} \phi_j \right) \\ &= -k \left( \phi_i \ \deg(v_i) - \sum_j A_{ij} \phi_j \right) \\ &= -k \sum_j \left( \delta_{ij} \ \deg(v_i) - A_{ij} \right) \phi_j \\ &= -k \sum_j \left( \ell_{ij} \right) \phi_j. </pre> \end{align}$$

使用矩陣矢量

$$\begin{align} <pre> \frac{d\phi}{dt} &= -k(D - A)\phi \\ &= -kL \phi </pre> \end{align}$$

$$\frac{d \phi}{d t} + kL\phi = 0$$

解是

$$\begin{align} <pre> \frac{d\left(\sum_i c_i \mathbf{v}_i\right)}{dt} + kL\left(\sum_i c_i \mathbf{v}_i\right) &= 0 \\ \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i L \mathbf{v}_i\right] &= \\ \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i \lambda_i \mathbf{v}_i\right] &= \\ \frac{dc_i}{dt} + k \lambda_i c_i &= 0\\ </pre> \end{align}$$

$$c_i(t) = c_i(0) e^{-k \lambda_i t}$$

$$c_i(0) = \left\langle \phi(0), \mathbf{v}_i \right\rangle$$

### 平衡舉動

當$\lim_{t \to \infty}\phi(t)$的時候。

$$\lim_{t\to\infty} e^{-k \lambda_i t} = \left\{\begin{array}{rlr} <pre> 0 & \text{if} & \lambda_i > 0 \\ 1 & \text{if} & \lambda_i = 0 </pre> \end{array}\right\}$$

$$\lim_{t\to\infty}\phi(t) = \left\langle c(0), \mathbf{v^1} \right\rangle \mathbf{v^1}$$

$$\mathbf{v^1} = \frac{1}{\sqrt{N}} [1, 1, ..., 1]$$

$$\lim_{t\to\infty}\phi_j(t) = \frac{1}{N} \sum_{i = 1}^N c_i(0)$$

### MATLAB代碼

```matlab
N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix

%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
   for y = 1:N
       index = (x-1)*N + y;
       for ne = 1:length(dx)
           newx = x + dx(ne);
           newy = y + dy(ne);
           if newx > 0 && newx <= N && newy > 0 && newy <= N
               index2 = (newx-1)*N + newy;
               Adj(index, index2) = 1;
           end
       end
   end
end

%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);

C0V = V'*C0;%Transform the initial condition into the coordinate system 
%of the eigenvectors
for t = 0:0.05:5
   %Loop through times and decay each initial component
   Phi = C0V.*exp(-D*t);%Exponential decay for each component
   Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
   Phi = reshape(Phi, N, N);
   %Display the results and write to GIF file
   imagesc(Phi);
   caxis([0, 10]);
   title(sprintf('Diffusion t = %3f', t));
   frame = getframe(1);
   im = frame2im(frame);
   [imind, cm] = rgb2ind(im, 256);
   if t == 0
      imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1); 
   else
      imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
   end
end
```

<image>

## 應用

- Kirchoff定理：調和矩陣的行列式
- 人工智慧
- 非線性降維
- 譜聚類
- Cheeger不等式：調和矩陣的第二大的特徵值跟最大割問題有關
- 圖Signal processing

## 閱讀

- B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), , Chapters II.3 (Vector Spaces and Matrices Associated with Graphs), VIII.2 (The Adjacency Matrix and the Laplacian), IX.2 (Electrical Networks and Random Walks).