调和矩阵

在图论中，调和矩阵（harmonic matrix），也称拉普拉斯矩阵或拉氏矩阵（Laplacian matrix）、离散拉普拉斯（discrete Laplacian），是图的矩阵表示。

调和矩阵也是拉普拉斯算子的离散化。换句话说，调和矩阵的缩放极限是拉普拉斯算子。它在机器学习和物理学中有很多应用。

定义
若G是简单图，G有n个顶点，A是邻接矩阵，D是度数矩阵，则调和矩阵是

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），则

\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,

随机漫步
L^\text{rw} := D^{-1}L = I - D^{-1}A

L^\text{rw}_{i,j} := \begin{cases}
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}.
\end{cases}

动力学和微分方程
例如，离散的冷却定律使用调和矩阵

\begin{align}
\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.
\end{align}

使用矩阵矢量

\begin{align}
\frac{d\phi}{dt} &= -k(D - A)\phi \\
&= -kL \phi
\end{align}

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

解是

\begin{align}
\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\\
\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}
0 & \text{if} & \lambda_i > 0 \\
1 & \text{if} & \lambda_i = 0
\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代码
N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(NN, NN);%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 0 && newy

应用
*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).