SAN 阅读笔记
目录

附录 A 精校翻译：概率、线性代数与图论背景材料

附录 A　概率、线性代数与图论背景材料（Background Material from Probability, Linear Algebra and Graph Theory）

A.1　概率（Probability）

A.1.1　概率工具箱（Probability Toolbox）

在下文中，$X$（或 $X_i$）均表示一个随机变量（random variable，r.v.）。

命题 A.1 期望的线性性与指标变量
  • 对常数 $a,b$，$\mathbb{E}(aX+b)=a\mathbb{E}(X)+b$；
  • $\mathbb{E}(X_1+\cdots+X_m)=\mathbb{E}(X_1)+\cdots+\mathbb{E}(X_m)$；
  • 设 $X$ 是随机变量，$A$ 是事件，$1_A(X)$ 是由 $X$ 是否实现事件 $A$ 所定义的指标变量。那么：
$$ \mathbb{E}\bigl(1_A(X)\bigr)=\mathbb{P}(X\in A). $$

定义 A.1 方差（Variance）

随机变量 $X$ 的方差定义为

$$ \operatorname{Var}(X)=\mathbb{E}\bigl((X-\mathbb{E}(X))^2\bigr). $$

命题 A.2 方差的基本公式

我们有以下结果：

  • $\operatorname{Var}(X)=\mathbb{E}(X^2)-(\mathbb{E}(X))^2$；
  • 对常数 $a,b$，$\operatorname{Var}(aX+b)=a^2\operatorname{Var}(X)$；
  • 若 $X_1,\ldots,X_m$ 相互独立，则 $\operatorname{Var}(X_1+\cdots+X_m)=\operatorname{Var}(X_1)+\cdots+\operatorname{Var}(X_m)$；
  • 若不具备这种独立性，则 $$ \operatorname{Var}(X_1+\cdots+X_m) =\operatorname{Var}(X_1)+\cdots+\operatorname{Var}(X_m) +\sum_{i\ne j}\operatorname{Cov}(X_i,X_j), $$ 其中 $\operatorname{Cov}(X_i,X_j)=\mathbb{E}(X_iX_j)-\mathbb{E}(X_i)\mathbb{E}(X_j)$。

A.1.2　基本概率定律（Basic Probability Laws）

定义 A.2 Bernoulli 分布（Bernoulli law）

若随机变量 $X$ 服从参数为 $p\in[0,1]$ 的 Bernoulli 分布，记作 $X\sim\operatorname{Ber}(p)$，则：

  1. $X$ 取值于 $\{0,1\}$；
  2. $\mathbb{P}(X=1)=p$ 且 $\mathbb{P}(X=0)=1-p$。

例 A.1 偏置硬币

Bernoulli 随机变量 $\operatorname{Ber}(p)$ 可以表示抛掷一枚有偏硬币的结果（$p$ 是抛硬币获胜的概率）。

命题 A.3 Bernoulli 随机变量的均值与方差

若 $X\sim\operatorname{Ber}(p)$，则 $\mathbb{E}X=p$ 且 $\operatorname{Var}X=p(1-p)$。

定义 A.3 二项分布（Binomial distribution）

参数为 $n$ 和 $p$ 的二项分布记作 $\operatorname{Bin}(n,p)$，它是 $n$ 次相互独立、参数为 $p$ 的 Bernoulli 试验中成功次数所服从的离散概率分布。

命题 A.4 独立 Bernoulli 和的分布

若 $(X_i)_{i=1,\ldots,n}$ 是一列服从 $\operatorname{Ber}(p)$ 的 $n$ 个独立同分布随机变量，则

$$ \sum_{i=1}^{n}X_i\sim\operatorname{Bin}(n,p). $$

推论 A.1 二项分布的概率质量函数、均值与方差

若 $X\sim\operatorname{Bin}(n,p)$，则

$$ \mathbb{P}(X=k)=\binom{n}{k}p^k(1-p)^{n-k}. $$

此外，$\mathbb{E}X=np$ 且 $\operatorname{Var}X=np(1-p)$。

定义 A.4 几何分布（Geometric distribution）

参数为 $p$ 的几何分布（记作 $\operatorname{Geo}(p)$）描述得到一次成功所需的 Bernoulli 试验次数（每次试验参数均为 $p$）。具体而言，若 $X\sim\operatorname{Geo}(p)$，则 $X\in\{1,2,\ldots\}$，且

$$ \mathbb{P}(X=k)=(1-p)^{k-1}p. $$

命题 A.5 几何分布的均值与方差

若 $X\sim\operatorname{Geo}(p)$，则

$$ \mathbb{E}X=\frac{1}{p},\qquad \operatorname{Var}X=\frac{1-p}{p^2}. $$

A.1.3　随机变量的集中（Concentration of Random Variables）

一阶矩不等式（First moment inequalities）

命题 A.6（Markov 不等式） Markov’s inequality

设 $X$ 是取正值的随机变量，且 $a\in\mathbb{R}_+$。则

$$ \mathbb{P}(X\ge a)\le\frac{\mathbb{E}X}{a}. $$
原书证明 命题 A.6

$\mathbb{E}X\ge\mathbb{E}\bigl(X1_{X\ge a}\bigr)\ge a\mathbb{E}\bigl(1_{X\ge a}\bigr)=a\mathbb{P}(X\ge a)$。

查看学习笔记完整证明

评注 A.1 Markov 不等式的相对阈值形式

令 $a=t\mathbb{E}X$，得到

$$ \mathbb{P}(X\ge t\mathbb{E}X)\le\frac{1}{t}. $$

收敛速度 $1/t$ 相当慢，视具体要求而定，它可能不够强。

推论 A.2（一阶矩方法） First moment method

设 $X$ 是取正值且为整数值的随机变量。则

$$ \mathbb{P}(X\ne0)\le\mathbb{E}(X). $$

一阶矩是整数值随机变量不等于零的概率的一个上界。

原书证明 推论 A.2

由于 $X$ 取整数值，有 $\mathbb{P}(X\ne0)=\mathbb{P}(X>0)=\mathbb{P}(X\ge1)$，于是可使用 Markov 不等式。

查看学习笔记完整证明

应用 A.3（并集界） Union bound

设 $A_1,\ldots,A_m$ 是一族事件。则

$$ \mathbb{P}(A_1\cup\cdots\cup A_m)\le\sum_{i=1}^{m}\mathbb{P}(A_i). $$

可以对 $X=\sum_{i=1}^{m}1_{A_i}$ 使用一阶矩方法，并观察到 $\{X>0\}=A_1\cup\cdots\cup A_m$，从而证明这一点。

查看学习笔记补充证明

评注 A.2 一阶矩方法的适用情形

一阶矩方法通常用于这样的正整数值随机变量序列 $X_n$：$\mathbb{E}X_n\to0$。在这种情况下，$X_n\to0$ 几乎处处。

我们可能天真地以为，如果 $\mathbb{E}X_n\to+\infty$，那么 $\mathbb{P}(X_n>0)\to1$。遗憾的是，这并不成立，下一个例子给出了一个反例。

例 A.2 一阶矩发散但随机变量趋于零

令 $X_n$ 满足：以概率 $1/n$ 取值 $n^2$，其他情况下取值 $0$。于是 $\mathbb{E}(X_n)=n\to+\infty$，但 $X_n\to0$。粗略地说，这是因为 $X_n$ 的方差非常大。事实上，

$$ \operatorname{Var}X_n=n^2(n-1). $$

二阶矩不等式（Second moment inequalities）

命题 A.7（Chebyshev 不等式） Chebyshev’s inequality

设 $X$ 是随机变量，且 $a>0$。则

$$ \mathbb{P}\bigl(|X-\mathbb{E}X|\ge a\bigr)\le\frac{\operatorname{Var}X}{a^2}. $$
原书证明 命题 A.7

对 $Y=(X-\mathbb{E}X)^2$ 应用 Markov 不等式。

查看学习笔记完整证明

例 A.3 Gaussian 比较

设 $X$ 服从 Gaussian 分布 $\mathcal{N}(0,\sigma^2)$。那么 $\mathbb{E}|X|=\sigma\sqrt{2/\pi}$。对 $|X|$ 应用 Markov 不等式可得

$$ \mathbb{P}(X\ge a)\le\sqrt{\frac{2}{\pi}}\frac{\sigma}{a}, $$

而 Chebyshev 不等式给出

$$ \mathbb{P}(X\ge a)\le\left(\frac{\sigma}{a}\right)^2. $$

当 $a$ 较大时，Chebyshev 不等式给出的界更强。

应用 A.4（大数定律的弱形式） Weak law of Large Numbers

设 $X_1,\ldots,X_n$ 是相互独立的随机变量，均值为 $\mu$，方差为 $\sigma^2<+\infty$。则

$$ \mathbb{P}\left(\left|\frac{X_1+\cdots+X_n}{n}-\mu\right|>\varepsilon\right)\longrightarrow0. $$

再做一些工作，我们可以证明不需要 $\sigma^2<+\infty$ 这一条件。此外，大数定律的强形式指出，这里的收敛实际上是几乎处处收敛，而不只是依概率收敛。

原书证明 应用 A.4

对 $U_n=(X_1+\cdots+X_n)/n$ 应用 Chebyshev 不等式；$U_n$ 的均值为 $\mu$，方差为 $\sigma^2$，于是

$$ \mathbb{P}(|U_n|\ge\varepsilon)\le\frac{\sigma^2}{n\varepsilon^2}\longrightarrow0. $$ 查看学习笔记完整证明与校勘说明

推论 A.5（二阶矩方法） Second moment method

设 $X$ 是正随机变量。则

$$ \mathbb{P}(X=0)\le\frac{\operatorname{Var}X}{(\mathbb{E}X)^2} =\frac{\mathbb{E}(X^2)}{(\mathbb{E}X)^2}-1. $$
原书证明 推论 A.5

取 $a=\mathbb{E}X$，应用 Chebyshev 不等式：

$$ \mathbb{P}(X=0)\le \mathbb{P}\bigl(|X-\mathbb{E}X|\ge\mathbb{E}X\bigr) \le\frac{\operatorname{Var}X}{(\mathbb{E}X)^2}, $$

其中第一个不等式成立，是因为 $|X-\mathbb{E}X|\ge\mathbb{E}X$ 蕴含 $X\le0$ 或 $X\ge2\mathbb{E}X$。

查看学习笔记完整证明

评注 A.3 Cauchy–Schwarz 的加强

由 Cauchy–Schwarz 不等式，

$$ \mathbb{E}(X)\le\mathbb{E}\bigl(X1_{X>0}\bigr) \le\sqrt{\mathbb{E}(X^2)}\sqrt{\mathbb{P}(X>0)}, $$

从而

$$ \mathbb{P}(X=0)=1-\mathbb{P}(X>0)\le\frac{\operatorname{Var}(X)}{\mathbb{E}(X^2)}, $$

这比推论 A.5 给出的不等式略强。

独立同分布随机变量和的集中（Concentration of sums of i.i.d. random variables）

命题 A.8（Hoeffding 不等式） Hoeffding’s inequality

设 $X_i$ 是相互独立的随机变量，并满足 $a_i\le X_i\le b_i$；令 $S_n=\sum_{i=1}^{n}X_i$。对 $t>0$，有：

$$ \mathbb{P}(S_n\ge\mathbb{E}S_n+t) \le\exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right), $$ $$ \mathbb{P}(S_n\ge\mathbb{E}S_n-t) \le\exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right), $$ $$ \mathbb{P}(|S_n-\mathbb{E}S_n|\ge t) \le2\exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right). $$

关于集中不等式的更多细节，例如可参见 Vershynin（2018）第 2 章。

A.2　图论（Graph Theory）

A.2.1　定义与术语（Definitions, Vocabulary）

定义 A.5 图及其基本术语

图 $G$ 是一个二元组 $(V,E)$，其中 $V$ 是有限集合，其元素称为节点（nodes，也称顶点 vertices 或点 points），$E$ 是有序节点对的集合，称为边（edges，也称连接 links、线 lines 或键 bonds）。此外，我们使用以下术语：

  • 若 $(ij)\in E\Longleftrightarrow(ji)\in E$，则称图为无向图（undirected）；这意味着，如果存在从 $i$ 指向 $j$ 的连接，则反方向也存在同一条连接；
  • 边 $(ii)$ 称为自环（self-loop）。特别地，如果对所有节点 $i$ 都有 $(ii)\notin E$，则称图中没有自环；
  • 若每条边 $(ij)\in E$ 都带有权重 $w_{ij}>0$，则称图为加权图；
  • 节点 $i$ 的入度记作 $d_i^{\mathrm{in}}$，是进入 $i$ 的（可能带权的）边数，即 $$ d_i^{\mathrm{in}}=\sum_{j\in V}w_{ji}. $$ 类似地，节点 $i$ 的出度是从 $i$ 出发的边数，即 $$ d_i^{\mathrm{out}}=\sum_{j\in V}w_{ij}. $$ 对无向图，$d_i^{\mathrm{in}}=d_i^{\mathrm{out}}=d_i$，此时我们简称 $d_i$ 为节点 $i$ 的度。

定义 A.6 路径、圈与连通
  • 长度为 $k$ 的 $G$ 中路径，是边 $e_1,\ldots,e_k$ 的序列，其中 $e_i=(v_{i-1},v_i)$，$v_i$ 是顶点；
  • $k$-圈（$k$-cycle）是一个长度为 $k$、起点和终点为同一顶点的路径；
  • 设 $G$ 是无向图。若存在一条从节点 $u$ 到节点 $v$ 的路径，则称两个节点 $u,v$ 连通，并记作 $u\leftrightarrow v$。

命题 A.9 连通关系是等价关系

关系 $\leftrightarrow$ 对无向图而言是一个等价关系。特别地，我们可以把节点划分为等价类，这些等价类称为连通分量（connected components）。

原书证明 命题 A.9

$u\leftrightarrow u$（长度为 $0$ 的路径）。此外，若 $u\leftrightarrow v$ 且 $v\leftrightarrow z$，则 $u\leftrightarrow z$（把两条路径连接起来即可），这保证了传递性。最后，$u\leftrightarrow v$ 蕴含 $v\leftrightarrow u$（沿同一路径反向行走），这保证了对称性。

查看学习笔记完整证明

评注 A.4 连通分量的路径性质

特别地，这意味着同一个连通分量中的两个节点之间存在一条路径。反过来，属于两个不同连通分量的节点之间没有路径相连。

定义 A.7 连通图与不连通图

如果图 $G$ 在关系 $\leftrightarrow$ 下只有一个等价类，则称 $G$ 是连通的；否则称 $G$ 是不连通的。

特别地，在连通图中，对任意节点 $i,j$，都存在一条从 $i$ 到 $j$ 的路径。

定义 A.8 距离（Distance）

设 $i,j$ 是两个节点。节点 $i$ 与 $j$ 之间的距离记作 $d(i,j)$，定义为连接二者的最短路径长度。如果 $i\not\leftrightarrow j$，则 $d(i,j)=+\infty$。

定义 A.9（直径） Diameter

图的直径定义为任意一对连通顶点之间距离的最大值。

A.2.2　邻接矩阵（Adjacency Matrix）

定义 A.10 邻接矩阵（Adjacency matrix）

设 $G=(V,E)$ 是一个含有 $n$ 个节点的无权图。$G$ 的邻接矩阵（记作 $A$）是二值矩阵 $A\in\{0,1\}^{n\times n}$，满足当且仅当 $(ij)\in E$ 时 $A_{ij}=1$。

我们可以很容易地把这一规定推广到加权图：此时，元素 $A_{ij}$ 等于节点 $i$ 与 $j$ 之间边的权重 $w_{ij}$。

评注 A.5 邻接矩阵与图的对称性

$A$ 对称当且仅当图是无向图。此外，$A$ 的对角元素全为零当且仅当图没有自环。

定义 A.11 度矩阵（Degree matrix）

图 $G$ 的度矩阵记作 $D$，它是一个对角矩阵，其对角元素 $D_{ii}$ 为节点 $i$ 的度。

A.2.3　图 Laplacian（Graph Laplacians）

下文中，我们考虑顶点集为 $V=\{1,\ldots,n\}$ 的无向加权图 $G$。记 $A$ 为 $G$ 的邻接矩阵，$D$ 为其度矩阵。

定义 A.12（图 Laplacian） Graph Laplacian

我们定义：

  • （标准或组合）Laplacian：$L=D-A$；
  • 归一化 Laplacian： $\mathcal{L}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$；
  • PageRank Laplacian：$\mathcal{L}_{\mathrm{PR}}=I-D^{-1}A$。

评注 A.6 孤立节点的约定

如果存在孤立节点（度为 $0$ 的节点），则 $D^{-1/2}$ 和 $D^{-1}$ 没有良好定义。我们可以假设图中没有这样的节点；或者约定：若 $i$ 是孤立节点，则令 $D_{ii}^{-1/2}=D_{ii}^{-1}=0$。

引理 A.6 两个 Laplacian 的元素形式

若节点 $i$ 和 $j$ 是邻居，我们记作 $i\sim j$。此外，假设图没有自环。则

$$ L_{ij}=\begin{cases} d_i,&i=j,\\ -1,&i\sim j,\\ 0,&\text{其他情形，} \end{cases} \qquad \mathcal{L}_{ij}=\begin{cases} 1,&i=j,\\ -\dfrac{1}{\sqrt{d_i d_j}},&i\sim j,\\ 0,&\text{其他情形。} \end{cases} $$
原书证明 引理 A.6

这直接来自 $L$ 与 $\mathcal{L}$ 的定义。

查看学习笔记完整证明

Laplacian 的基本性质（Basic properties of the Laplacians）

命题 A.10 标准 Laplacian 的基本性质

标准 Laplacian $L=D-A$ 具有以下性质：

  1. 对任意向量 $x\in\mathbb{R}^n$，有 $$ x^\top Lx=\frac12\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}(x_i-x_j)^2. $$ 更一般地，对任意矩阵 $X\in\mathbb{R}^{n\times K}$，有 $$ \operatorname{Tr}(X^\top LX)=\frac12\sum_{k=1}^{K}\sum_{i,j}a_{ij}(X_{ik}-X_{jk})^2; $$
  2. $L$ 是对称且半正定的；
  3. $L$ 有 $n$ 个非负实特征值 $0=\lambda_1\le\cdots\le\lambda_n$。此外，$L1_n=0_n$。
原书证明 命题 A.10

1. 回忆 $d_i=\sum_{j=1}^{n}a_{ij}$。可以写成

$$ \begin{aligned} \frac12\sum_{i,j=1}^{n}a_{ij}(x_i-x_j)^2 &=\frac12\left(\sum_{i,j}a_{ij}x_i^2-2\sum_{i,j}a_{ij}x_ix_j+\sum_{i,j}a_{ij}x_j^2\right)\\ &=\frac12\left(\sum_{i=1}^{n}d_i x_i^2-2\sum_{i,j=1}^{n}x_ix_j a_{ij}+\sum_{j=1}^{n}d_jx_j^2\right)\\ &=\sum_{i=1}^{n}d_i x_i^2-\sum_{i,j=1}^{n}x_ix_j a_{ij}\\ &=x^\top Dx-x^\top Ax\\ &=x^\top Lx. \end{aligned} $$

更一般地，对 $X\in\mathbb{R}^{n\times K}$，注意到

$$ \operatorname{Tr}(X^\top LX)=\sum_{k=1}^{K}X_{\cdot k}^{\top}LX_{\cdot k}, $$

其中 $X_{\cdot k}$ 表示 $X$ 的第 $k$ 列；对每一列应用前面的结果即可得到矩阵形式。

2. $L$ 对称，是因为 $D$ 和 $A$ 都对称。由第 1 点，$x^\top Lx\ge0$，因此 $L$ 半正定。

3. $L$ 对称，所以其特征值为实数；$L$ 半正定，所以其特征值非负。最后，利用第 1 点得到的公式可直接验证 $L1_n=0_n$。

查看学习笔记完整证明与二次型核对

命题 A.11 归一化 Laplacian 的基本性质

归一化 Laplacian $\mathcal{L}$ 具有以下性质：

  1. 对任意向量 $x\in\mathbb{R}^n$，有 $$ x^\top\mathcal{L}x =\frac12\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij} \left(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\right)^2. $$ 更一般地，对任意矩阵 $X\in\mathbb{R}^{n\times K}$，有 $$ \operatorname{Tr}(X^\top\mathcal{L}X) =\frac12\sum_{k=1}^{K}\sum_{i,j}a_{ij} \left(\frac{X_{ik}}{\sqrt{d_i}}-\frac{X_{jk}}{\sqrt{d_j}}\right)^2; $$
  2. $\mathcal{L}$ 是对称且半正定的；
  3. $\mathcal{L}$ 有 $n$ 个非负实特征值 $0=\lambda_1\le\cdots\le\lambda_n\le2$。此外，$D^{1/2}1_n$ 是 $\mathcal{L}$ 对应于特征值 $0$ 的一个特征向量。

命题 A.11 的证明与命题 A.10 的证明类似。

查看学习笔记补充证明（非原书 Proof）

标准 Laplacian 与连通分量数（Standard Laplacian and the number of connected components）

定义 A.13（集合的指标向量） Indicator vector of a set

设 $U$ 是节点集 $V$ 的子集。定义 $1_U$ 为 $n\times1$ 向量：当 $i\in U$ 时 $(1_U)_i=1$，当 $i\notin U$ 时 $(1_U)_i=0$。令 $1_n$ 表示全为 $1$ 的 $n\times1$ 向量。

引理 A.7 $LX=0$ 与分量上的常值性

$LX=0\Longleftrightarrow X$ 在 $G$ 的每个连通分量上为常值。

原书证明 引理 A.7

设 $V_1,\ldots,V_K$ 是 $G$ 的连通分量。假设 $LX=0$。于是 $X^\top LX=0$；由前一命题的公式可知，对所有 $i,j\in V_k$，都有 $x_i=x_j$。因此，$LX=0$ 蕴含 $X$ 在 $G$ 的每个连通分量上为常值。

反过来，直接计算可见，如果 $X$ 在每个 $V_k$ 上为常值，则 $LX=0$。

查看学习笔记完整证明（含逆向计算）

命题 A.12（连通分量数） Number of connected components

设 $G$ 是一个具有非负权重的无向图。那么特征值 $0$ 的重数 $k$ 等于连通分量 $V_1,\ldots,V_k$ 的数量。此外，特征值 $0$ 的特征空间（$\operatorname{Ker}L$）由指标向量 $1_{V_1},\ldots,1_{V_k}$ 张成。

原书证明 命题 A.12

若 $k=1$，这意味着 $0$ 的唯一特征向量是 $X=1_n$，且图是连通的。

现在设 $k>1$。我们可以假设顶点按照所属连通分量排序。于是 $L=\operatorname{diag}(L_1,\ldots,L_k)$，其中 $L_i$ 是第 $i$ 个连通分量的 Laplacian。每个 $L_i$ 都有一个重数为 $1$ 的特征值 $0$，相应的特征向量是全为 $1$ 的常向量。因此，$L1_{V_i}=L_i1_n=0$，每个 $1_{V_i}$ 都是 $L$ 对应于 $0$ 的特征向量。

查看学习笔记完整证明

例 A.4 连通图的零特征空间

假设图是连通的。于是只有一个连通分量（$k=1$），因此 $\dim\operatorname{Ker}L=1$，相应的特征空间由 $1_n$ 张成。

A.3　线性代数（Linear Algebra）

A.3.1　对称矩阵（Symmetric Matrices）

定理 A.8（谱定理） Spectral theorem

若 $M$ 是实对称矩阵，则存在一个由 $M$ 的特征向量构成的标准正交基。此外，$M$ 的特征值都是实数。

反例 A.9（若 $M$ 含复数元素） 复对称矩阵未必可对角化

令

$$ M=\begin{pmatrix}1&i\\ i&-1\end{pmatrix}. $$

该矩阵是对称的，但不可对角化。事实上，直接计算其特征多项式可以看到，它唯一的特征值是 $0$。

定义 A.14 半正定与正定矩阵

若对所有 $x\in\mathbb{R}^n$ 都有 $x^\top Mx\ge0$，则称对称矩阵 $M$ 为半正定（positive semidefinite，PSD）；若对所有 $x\in\mathbb{R}^n$ 都有 $x^\top Mx>0$，则称其为正定（positive definite，PD）。

例 A.5 $M^\top M$ 的正定性

对所有 $M\in\mathbb{R}^{n\times n}$，矩阵 $M^\top M$ 是对称正定矩阵。

引理 A.10 半正定性与特征值

设 $M$ 是对称矩阵，$\lambda_1,\ldots,\lambda_n$ 是它的（实）特征值。$M$ 半正定（分别为正定）当且仅当 $\lambda_i\ge0$（分别为 $\lambda_i>0$）。

A.3.2　范数（Norms）

定义 A.15 范数公理

设 $E$ 是向量空间。若函数 $N:E\to\mathbb{R}$ 满足下列性质，则称 $N$ 为范数：

  1. （正性）$\forall x\in E:N(x)\ge0$；
  2. （定性）$N(x)=0\Rightarrow x=0_E$；
  3. （齐次性）$\forall x\in E,t\in\mathbb{R}:N(tx)\le|t|N(x)$；
  4. （三角不等式）$\forall x,y\in E:N(x+y)\le N(x)+N(y)$。

向量范数（Vector norms）

命题 A.13 $p$-范数（$p$-norms）

令 $E=\mathbb{R}^n$ 且 $p\ge1$，定义 $p$-范数如下：

$$ \|x\|_p=\left(\sum_{i=1}^{n}|x_i|^p\right)^{1/p}. $$
原书证明 命题 A.13

直接验证 $\|\cdot\|_p$ 满足前三个条件即可。三角不等式由 Minkowski 不等式得到。

查看学习笔记补充证明（非原书展开）

例 A.6 $p$-范数的特殊情形

设 $x=(x_1,\ldots,x_n)^\top\in\mathbb{R}^n$。$p$-范数的以下情形尤其常用：

  1. 当 $p=1$ 时，$\|x\|_1=\sum_{i=1}^{n}|x_i|$；
  2. 当 $p=2$ 时，$\|x\|_2=\sqrt{\sum_{i=1}^{n}|x_i|^2}$，这就是 Euclidean 范数；
  3. 当 $p=\infty$ 时，定义 $$ \|x\|_\infty=\lim_{p\to+\infty}\|x\|_p=\max\{|x_1|,\ldots,|x_n|\}。 $$

此外，如果在两个向量 $x,y\in\mathbb{R}^n$ 之间引入内积 $\langle x,y\rangle=x^\top y$，则 $\|x\|_2^2=x^\top x$。

矩阵范数（Matrix norms，Serre, 2010）

定义 A.16 诱导算子范数

设 $\|\cdot\|$ 是 $\mathbb{R}^n$ 上的一个范数。定义由 $\|\cdot\|$ 诱导的 $\mathbb{R}^{n\times n}$ 上的算子范数 $\|||\cdot|||$ 为

$$ \|||A|||=\sup_{x\in\mathbb{R}^n:\,x\ne0_n}\frac{\|Ax\|}{\|x\|}. $$

滥用记号时，我们常常用 $\|\cdot\|$ 表示算子范数，而不是 $\|||\cdot|||$。

引理 A.11 单位球上的算子范数

设 $A\in\mathbb{R}^{n\times n}$。则

$$ \|||A|||=\sup_{\|x\|=1}\|Ax\|=\sup_{\|x\|\le1}\|Ax\|=\max_{\|x\|\le1}\|Ax\|. $$

例 A.7 诱导范数的四个公式

设 $A\in\mathbb{R}^{n\times n}$。以下是诱导范数：

  1. $$ \|||A|||_1=\sup_{\|x\|_1=1}\|Ax\|_1 =\max_{j=1,\ldots,n}\sum_{i=1}^{n}|A_{ij}| \qquad\text{（最大列和）；} $$
  2. $$ \|||A|||_\infty=\sup_{\|x\|_\infty=1}\|Ax\|_\infty =\max_{i=1,\ldots,n}\sum_{j=1}^{n}|A_{ij}| \qquad\text{（最大行和）；} $$
  3. $$ \|||A|||_2=\sup_{x^\top x=1}\sqrt{x^\top A^\top A x} =\sqrt{\lambda_{\max}(A^\top A)}, $$ 其中 $\lambda_{\max}(A^\top A)$ 表示（对称）矩阵 $A^\top A$ 的最大特征值；
  4. 如果 $A$ 可逆，则 $$ \|||A^{-1}|||_2=\frac{1}{\lambda_{\min}(A^\top A)}, $$ 其中 $\lambda_{\min}(A^\top A)$ 是 $A^\top A$ 的最小特征值（若 $A^{-1}$ 可逆，则该值非零）。
查看学习笔记补充证明（含第 4 条校勘）

命题 A.14 诱导范数的次乘性

设 $\|||\cdot|||$ 是一个诱导算子范数。则对所有 $A,B\in\mathbb{R}^{n\times n}$，

$$ \|||AB|||\le\|||A|||\times\|||B|||. $$

反例 A.12 非诱导矩阵范数不一定次乘

如果范数不是由向量范数诱导的，这个不等式一般不成立。例如，令

$$ N(A)=\max_{i,j}|a_{ij}| $$

（不要把它与 $\|||\cdot|||_\infty$ 混淆），并令

$$ A=\begin{pmatrix}1&1\\1&1\end{pmatrix}。 $$

那么 $N(A^2)=2>N(A)N(A)=1$。

定义 A.17 Frobenius 范数

对 $A\in\mathbb{R}^{n\times n}$，定义

$$ \|A\|_F=\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{n}|A_{ij}|^2} $$

为矩阵 $A$ 的 Frobenius 范数（或 Hilbert–Schmidt 范数）。

A.3.3　Courant–Fischer 极小极大定理（Courant–Fischer Min–Max Theorem）

定理 A.13（Courant–Fischer 极小极大定理） Courant–Fischer min–max theorem

设 $M\in\mathbb{R}^{n\times n}$ 是 $n\times n$ 对称矩阵，$\lambda_1\le\cdots\le\lambda_n$ 是 $M$ 的特征值，对应的归一化特征向量为 $v_1,\ldots,v_n$。我们有

$$ \lambda_1=\min_{\substack{x\in\mathbb{R}^n\\\|x\|=1}}x^\top Mx =\min_{\substack{x\in\mathbb{R}^n\\x\ne0_n}}\frac{x^\top Mx}{x^\top x}, \tag{A.1} $$ $$ \lambda_2=\min_{\substack{x\in\mathbb{R}^n\\\|x\|=1\\x\perp v_1}}x^\top Mx =\min_{\substack{x\in\mathbb{R}^n\\x\ne0_n\\x\perp v_1}}\frac{x^\top Mx}{x^\top x}, \tag{A.2} $$ $$ \lambda_n=\max_{\substack{x\in\mathbb{R}^n\\\|x\|=1}}x^\top Mx =\max_{\substack{x\in\mathbb{R}^n\\x\ne0_n}}\frac{x^\top Mx}{x^\top x}. \tag{A.3} $$

相应的 arg min 分别由 $v_1,v_2$ 和 $v_n$ 取得。

原书证明 定理 A.13

我们给出两个证明：一个通过将矩阵 $M$ 对角化，另一个使用微积分（Lagrange 极小化子）。

（i）第一种证明。由于 $M$ 对称，可以写成 $M=P^\top DP$。令 $y=Px$。注意 $\|y\|=\|x\|$，因此约束 $\|x\|=1$ 变成

$$ \sum_{i=1}^{n}y_i^2=1。 $$

又由于

$$ x^\top Mx=y^\top Dy=\sum_{i=1}^{n}\lambda_i y_i^2， $$

在上述约束下，当除 $y_1=1$ 外所有 $y_i$ 都为零时，该表达式取得最小值；当 $y_n=1$ 且其余 $y_i$ 都为 $0$ 时，取得最大值。如果 $x\perp v_1$，还要施加 $y_1=0$ 这一约束，此时当 $y_2=1$ 且其他 $y_i$ 为零时，$y^\top Dy$ 取得最小值。

（ii）第二种证明。与最小化问题（A.1）（或（A.3））对应的 Lagrange 函数为

$$ \mathcal{L}(x,\lambda)=x^\top Mx-\lambda\bigl(x^\top x-1\bigr)。 $$

令 $\partial\mathcal{L}/\partial\lambda=0$，可恢复约束 $\|x\|=1$。此外，

$$ \frac{\partial\mathcal{L}}{\partial x}=2Mx-2\lambda x。 $$

因此令 $\partial\mathcal{L}/\partial x=0$ 导出 $Mx=\lambda x$。于是 $x$ 是 $M$ 的特征向量，而 $\lambda$ 是相应特征值。由于方程（A.1）是最小化问题，其解是最小特征值；同理，方程（A.3）的解是最大特征值。最后，如果进一步施加 $x\perp v_1$，则解是第二小特征值。

查看学习笔记完整证明与 Rayleigh 商说明

命题 A.15 迹最小化

设 $M\in\mathbb{R}^{n\times n}$ 是对称矩阵，$v_1,\ldots,v_n$ 是与 $\lambda_1\le\lambda_2\le\cdots\le\lambda_n$ 对应的特征向量标准正交基。优化问题

$$ \underset{\substack{H\in\mathbb{R}^{n\times K}\\H^\top H=I_K}}{\arg\min}\ \operatorname{Tr}(H^\top MH) $$

的解为 $H=[v_1,\ldots,v_K]$。

原书证明 命题 A.15

考虑 Lagrange 函数

$$ \mathcal{L}(H,\Lambda)=\operatorname{Tr}(H^\top MH)-\operatorname{Tr}\left(\Lambda^\top(H^\top H-I_K)\right)， $$

其中 $\Lambda\in\mathbb{R}^{K\times K}$ 是对角矩阵，其元素为 Lagrange 乘子。由于

$$ \frac{\partial\mathcal{L}}{\partial H}=2MH-2H\Lambda， $$

条件 $\partial\mathcal{L}/\partial H=0$ 导出 $MH=H\Lambda$。因此，$H$ 的列确实是 $M$ 的特征向量，而 $\Lambda$ 的对角元素是对应的特征值。

查看学习笔记完整证明与最小性核对

A.4　图上的微积分（Calculus on Graphs）

关于本节主题的更多细节，我们请读者参见 Hein et al.（2007）。

A.4.1　基本回顾（Basic Reminders）

考虑函数 $f:\mathbb{R}^n\to\mathbb{R}$。点 $x\in\mathbb{R}^n$ 处的梯度是向量

$$ \nabla f(x)=\operatorname{grad}f(x) =\left(\frac{\partial f}{\partial x_1}(x),\ldots,\frac{\partial f}{\partial x_n}(x)\right)^\top。 $$

对每个 $x\in\mathbb{R}^n$，散度定义为

$$ \operatorname{div}f(x)=\sum_{i=1}^{n}\frac{\partial f}{\partial x_i}(x)， $$

而 Laplacian 算子为

$$ \Delta f(x)=\sum_{i=1}^{n}\frac{\partial^2f}{\partial x_i^2}(x)。 $$

特别地，

$$ \operatorname{div}(\operatorname{grad}f)(x)=\Delta f。 $$

A.4.2　图上的延拓（Extension on Graphs）

本节考虑一个有向加权图 $G=(V,E)$，其权重为 $w_{ij}$，节点集为 $V=\{1,\ldots,n\}$。

图上的函数（Functions on graph）

记 $\mathcal{F}(V)$ 为节点函数 $f:V\to\mathbb{R}$ 的集合。由于 $|V|=n$，任意节点函数都可以表示为 $n\times1$ 向量 $(f(1),\ldots,f(n))^\top$，且 $\mathcal{F}(V)\cong\mathbb{R}^n$。特别地，$\mathcal{F}(V)$ 是一个 $n$ 维 Hilbert 空间，其内积为

$$ \langle f,g\rangle_{\mathcal{F}(V)}=\sum_{v_i\in V}f(i)g(i)， $$

相应的范数为

$$ \|f\|_{\mathcal{F}(V)}=\sqrt{\langle f,f\rangle_{\mathcal{F}(V)}}。 $$

类似地，边函数空间为 $\mathcal{F}(E)=\{F:E\to\mathbb{R}\}$。该空间等价于 $\mathbb{R}^{|E|}$，我们引入内积

$$ \langle F,G\rangle_{\mathcal{F}(E)}=\sum_{(i,j)\in E}F(i,j)G(i,j)， $$

以及范数

$$ \|F\|_{\mathcal{F}(E)}=\sqrt{\langle F,F\rangle_{\mathcal{F}(E)}}。 $$

最后，任意边函数 $F:E\to\mathbb{R}$ 都可以平凡地延拓为函数 $\widetilde F:V\times V\to\mathbb{R}$：如果 $(v_i,v_j)\notin E$，就令 $\widetilde F(v_i,v_j)=0$。略微滥用记号，我们仍用 $F$ 表示延拓后的函数。

图微分算子（Differential graph operators）

令 $\gamma:\mathbb{R}_+\to\mathbb{R}_+$，满足 $\gamma(0)=0$。$\gamma$ 的选择将在后文讨论。沿有向边 $(i,j)\in E$ 的 $f$ 的图导数为

$$ \frac{\partial f}{\partial j}(i)=\gamma(w_{ij})\bigl(f(j)-f(i)\bigr)， $$

为方便起见记作 $\partial_jf(i)$。特别地，$\partial_if(i)=0$；若 $f(i)=f(j)$，则 $\partial_jf(i)=0$。

节点函数 $f\in\mathcal{F}(V)$ 的图梯度记作 $\operatorname{grad}f$，定义为

$$ \forall(i,j)\in E:\qquad(\operatorname{grad}f)(i,j)=\partial_jf(i)。 $$

因此，$\operatorname{grad}:\mathcal{F}(V)\to\mathcal{F}(E)$ 是一个线性算子。图散度 $\operatorname{div}$ 定义为 $\operatorname{grad}$ 的伴随算子1，即

$$ \langle\operatorname{grad}f,G\rangle_{\mathcal{F}(E)} =\langle f,\operatorname{div}G\rangle_{\mathcal{F}(V)}, \qquad\forall f\in\mathcal{F}(V),\ \forall G\in\mathcal{F}(E)。 $$

引理 A.14 图梯度的散度

梯度算子的散度 $\operatorname{div}:\mathcal{F}(E)\to\mathcal{F}(V)$ 为

$$ (\operatorname{div}G)(i)=\sum_j\gamma(w_{ji})G(j,i)-\gamma(w_{ij})G(i,j)。 $$
原书证明 引理 A.14

我们有

$$ \begin{aligned} \langle\operatorname{grad}f,G\rangle_{\mathcal{F}(E)} &=\sum_{i,j}\gamma(w_{ij})\bigl(f(j)-f(i)\bigr)G(i,j)\\ &=\sum_{i,j}\gamma(w_{ij})f(j)G(i,j)-\sum_{i,j}\gamma(w_{ij})f(i)G(i,j)\\ &=\sum_{i,j}\gamma(w_{ji})f(i)G(j,i)-\sum_{i,j}\gamma(w_{ij})f(i)G(i,j)\\ &=\sum_i f(i)\left(\sum_j\gamma(w_{ji})G(j,i)-\gamma(w_{ij})G(i,j)\right)\\ &=\langle f,\operatorname{div}G\rangle_{\mathcal{F}(V)}。 \end{aligned} $$

对于无向图（$w_{ij}=w_{ji}$），散度化为

$$ (\operatorname{div}G)(i)=\sum_j\gamma(w_{ij})\bigl(G(j,i)-G(i,j)\bigr)。 $$

最后，我们定义图 Laplacian $\Delta_\gamma:\mathcal{H}(V)\to\mathcal{H}(V)$，使得对每个 $f\in\mathcal{F}(V)$ 都有 $\Delta_\gamma f=\operatorname{div}(\operatorname{grad}f)$。

查看学习笔记完整证明

引理 A.15 图 Laplacian 的显式形式

设 $f\in\mathcal{F}(V)$ 且 $i\in V$。则

$$ (\Delta_\gamma f)(i) =\sum_j\left(\gamma(w_{ij})^2+\gamma(w_{ji})^2\right)\bigl(f(i)-f(j)\bigr)。 $$
原书证明 引理 A.15

令 $\gamma_{ij}=\gamma(w_{ij})$。则

$$ \begin{aligned} \operatorname{div}(\operatorname{grad}f)(i) &=\sum_j\gamma_{ji}\operatorname{grad}f(j,i)-\gamma_{ij}\operatorname{grad}f(i,j)\\ &=\sum_j\gamma_{ji}^2\bigl(f(i)-f(j)\bigr)-\gamma_{ij}^2\bigl(f(j)-f(i)\bigr)\\ &=\sum_j\left(\gamma_{ij}^2+\gamma_{ji}^2\right)\bigl(f(i)-f(j)\bigr)。 \end{aligned} $$

对于无向图，Laplacian 算子化为

$$ \Delta_\gamma f(i)=2\sum_j\gamma(w_{ij})^2\bigl(f(i)-f(j)\bigr)。 $$ 查看学习笔记完整证明与因子核对

回忆标准 Laplacian $L=D-A$，令 $f:V\to\mathbb{R}$ 为用 $n\times1$ 向量表示的节点函数。我们有

$$ (Lf)_i=d_if_i-\sum_jw_{ij}f_j=\sum_jw_{ij}\bigl(f_i-f_j\bigr)。 $$

因此，当 $\gamma(x)=\sqrt{x}$ 时，$L=\Delta_\gamma$。类似地，随机游走 Laplacian $L_{\mathrm{rw}}=I-D^{-1}A$ 满足

$$ (L_{\mathrm{rw}}f)_i=f_i-\sum_j\frac{w_{ij}}{d_i}f_j =\sum_j\frac{w_{ij}}{d_i}\bigl(f_i-f_j\bigr)， $$

其中第二个等号成立，是因为 $\sum_j w_{ij}/d_i=1$。因此，如果对所有 $i,j$ 有

$$ \gamma(w_{ij})=\sqrt{\frac{w_{ij}}{d_i}}， $$

则 $L_{\mathrm{rw}}=\Delta_\gamma$。