6.2. 规范方法的收敛性

有了前面的准备, 我们开始看谱聚类方法的相合性. 首先看规范方法, 由于 $L_{s y m}$ 和 $L_{r w}$ 的第二特征向量之间只差一个变换 $D^{- 1}$ , 而其是对角元为正的对角阵, 故在 $K = 2$ 的情形下的算法是等价的. 这里我们只考虑前者的收敛性, 对后者类似.

6.2.1第一步: 构造与 $L_{n}^{'}$ 对应的 $C (X)$ 上算子 $U_{n}^{'}$
6.2.2第二步: 算子 $U_{n}^{'}$ 与矩阵 $L_{n}^{'}$ 的谱关系
6.2.3第三步: 随机算子序列 ${U_{n}^{'}}$ 的收敛性
6.2.4第四步: 谱的收敛性

6.2.1第一步: 构造与 $L_{n}^{'}$ 对应的 $C (X)$ 上算子 $U_{n}^{'}$

注意到 $L_{n}^{'} = D_{n}^{- 1 / 2} L_{n} D_{n}^{- 1 / 2} = I - D_{n}^{- 1 / 2} W_{n} D_{n}^{- 1 / 2}$ , 我们以相似度函数 $s$ 对 $W_{n}$ 作连续化, 则可作如下构造:

定义 6.2.1.1.

•	度函数 [degree functions] $d_{n} (x) = \int_{X} s (x, y) d P_{n} (y), d (x) = \int_{X} s (x, y) d P (y)$
•	规范化相似度函数 [normalized similarity functions] $h_{n} (x, y) = \frac{s ( x , y )}{d _{n} ( x ) d _{n} ( y )}, h (x, y) = \frac{s ( x , y )}{d ( x ) d ( y )}$
•	积分算子 [integral operators] $T_{n}^{'} : f \mapsto \int_{X} h_{n} (x, y) f (y) d P_{n} (y), T_{n} : f \mapsto \int_{X} h (x, y) f (y) d P_{n} (y), T : f \mapsto \int_{X} h (x, y) f (y) d P (y)$
•	最后得到 $C (X)$ 上的算子 $U_{n}^{'} = I - T_{n}^{'}, U^{'} = I - T,$ 其中 $I$ 为恒等映射.

以上构造具有如下性质:

命题 6.2.1.2. 在问题的预先假设下, 有

1.	$d_{n}, d \in C (X)$ , 并且有一致的下界 $l > 0$ 及上界 $∥ s ∥_{\infty} < + \infty$ ;
2.	$T_{n}^{'}, T_{n}, T$ 的算子范数具有一致的上界 $∥ s ∥_{\infty} / l$ , 且是 $C (X)$ 上的紧算子;
3.	关系式 $L_{n}^{'} \circ ρ_{n} = ρ_{n} \circ U_{n}^{'}$ 成立.

6.2.2第二步: 算子 $U_{n}^{'}$ 与矩阵 $L_{n}^{'}$ 的谱关系

按照前面的分析, 我们希望 $f_{n} \in C (X)$ 是算子 $U_{n} ’$ 的一个特征函数, 即 $U_{n}^{'} f_{n} = λ f_{n}$ , 这样就有 $L_{n}^{'} v_{n} = L_{n}^{'} (ρ_{n} f_{n}) = ρ_{n} (U_{n}^{'} f_{n}) = λ ρ_{n} f_{n} = λ v_{n},$ 即 $v_{n} = ρ_{n} f_{n}$ 为 $L_{n}^{'}$ 关于特征值 $λ$ 的特征向量. 因此, 我们的目标是找到 $U_{n}^{'}$ 关于 $L_{n}^{'}$ 第二特征值 $λ_{2}$ 的特征函数 $f_{n} \in C (X)$ : 将该特征值问题写成 $(1 - λ_{2}) f_{n} (x) = T_{n}^{'} f_{n} (x) = \int_{X} h_{n} (x, y) f_{n} (y) d P_{n} (y) = \frac{1}{n} i = 1 \sum n h (x, X_{i}) f_{n} (X_{i}) = \frac{1}{n} i = 1 \sum n h (x, X_{i}) v_{n}^{i},$ 故只要 $λ_{2} \neq = 1$ , 我们就有 $f_{n} (x) = \frac{\sum _{i = 1}^{n} h ( x , X _{i} ) v _{n}^{i}}{n ( 1 - λ _{2} )} .$ 由于 $v_{n}$ 在每次抽样后可由 $L_{n}^{'}$ 的第二特征向量给出, 故上式给出了 $f_{n} \in C (X)$ 的确切定义.

上述推导过程可以在任意特征值上进行, 结合算子 $T_{n}^{'}$ 的紧性与矩阵 $L_{n}^{'}$ 的对称半正定性, 我们可以总结得到:

命题 6.2.2.1. 算子 $U_{n}^{'}$ 与矩阵 $L_{n}^{'}$ 的谱具有如下对应关系:

1.	具有相同的特征值;
2.	关于同一个特征值 $λ \neq = 1$ 的特征函数 $f \in C (X)$ 及特征向量 $v = (v^{1}, \dots, v^{n}) \in R^{n}$ 具有如下的一一对应关系: $v = ρ_{n} f, f (x) = \frac{\sum _{i = 1}^{n} h ( x , X _{i} ) v ^{i}}{n ( 1 - λ )};$
3.	$U_{n}^{'} = I - T_{n}^{'}$ 的谱 $σ (U_{n}^{'}) = {1} \cup σ (L_{n}^{'})$ 由有限个重数有限的非负特征值和 $σ_{e s s} (U_{n}^{'}) = {1}$ 组成.

对于特征值的非负性, 与矩阵 $L_{n}^{'}$ 的半正定性 $f^{T} L_{n}^{'} f = \frac{1}{2} i, j = 1 \sum n w_{i j} (\frac{f _{i}}{d _{i}} - \frac{f _{j}}{d _{j}})^{2} \geq 0, \forall f \in R^{n}$ 类似地, 我们也可以将 $U_{n}^{'}$ 视为 $L^{2} (P_{n})$ 函数空间上的算子, 利用函数内积 $⟨ U_{n}^{'} f, f ⟩ = \int_{X} (f (x) - \int_{X} h_{n} (x, y) f (y) d P_{n} (y)) f (x) d P_{n} (x) = \int_{X} \int_{X} s (x, y) (\frac{f ( x )}{d _{n} ( x )} - \frac{f ( y )}{d _{n} ( y )}) \frac{f ( x )}{d _{n} ( x )} d P_{n} (y) d P_{n} (x) = \frac{1}{2} \int_{X} \int_{X} s (x, y) (\frac{f ( x )}{d _{n} ( x )} - \frac{f ( y )}{d _{n} ( y )})^{2} d P_{n} (y) d P_{n} (x) \geq 0, \forall f \in L^{2} (P_{n})$ 直接得到算子 $U_{n}$ 的非负性.

同理, 由空间 $X$ 的紧性有 $C (X) \subset L^{2} (P)$ , 于是可以推知, $U^{'} = I - T$ 的谱由至多可数个重数有限的非负特征值组成. 此外还可以得到其本性谱为 $σ_{e s s} (U^{'}) = {1} .$

6.2.3第三步: 随机算子序列 ${U_{n}^{'}}$ 的收敛性

由于紧收敛性能够带来谱的收敛性, 我们考虑证明 ${U_{n}^{'}}$ 紧收敛到 $U^{'} .$ 首先需要证明逐点收敛性, 即对任意的 $f \in C (X)$ , 应有 $∥ U_{n}^{'} f - U^{'} f ∥_{\infty} \to 0 .$ 为此, 我们先考虑几个具有较好性质的函数集:

命题 6.2.3.1. 在预先假设下, 以下 $C (X)$ 的子集 $S H g \cdot H : = {s (x, \cdot) : x \in X} : = {h (x, \cdot) : x \in X} : = {g (\cdot) h (x, \cdot) : x \in X}, \forall g \in C (X)$ 均为 Glivenko-Cantelli 类, 即成立 $f \in F sup ∣ ∣ ∣ ∣ ∣ \int_{X} f (y) d P_{n} (y) - \int_{X} f (y) d P (y) ∣ ∣ ∣ ∣ ∣ n \to \infty 0 a.s., F = S, H, g \cdot H .$

证明. 以

S

为例进行证明, 另两个类似: 首先由

s

是紧度量空间

X

上的连续函数, 可知

s

在

X

上一致连续, 从而对任意

ε > 0

, 都存在

δ > 0

, 只要

x, x^{'} \in X

的距离小于

δ

, 就有

∥ s (x, \cdot) - s (x^{'}, \cdot) ∥_{\infty} < ε / 2 .

而由

X

的紧性可知存在有限个点

x_{1}, \dots, x_{k} \in X

, 使得

X = i = 1 ⋃ k (B_{δ} (x_{i}) \cap X) ⟹ S \subset i = 1 ⋃ k B_{ε / 2} (s (x_{i}, \cdot)) .

若记括号

[l, u]

表示满足

l \leq f \leq u

的函数

f

, 则有

S \subset i = 1 ⋃ k [s (x_{i}, \cdot) - \frac{ε}{2}, s (x_{i}, \cdot) + \frac{ε}{2}],

其中每个括号的

L^{1} (P)

-长度均为

ε

, 故子集

S

的

∥ \cdot ∥_{L^{1} (P)}

-括号数 [bracketing number]

N_{[]} (ε, S, L^{1} (P)) = k < \infty .

由

ε

的任意性, 结合 Glivenko-Cantelli 定理 (参考书 Weak Convergence and Empirical Processes 中定理 2.4.1) 即可得到结论.

$□$

借助此命题我们可以证明:

命题 6.2.3.2. 在预先假设下, $T_{n}^{'} p T$ a.s.

证明. 对任意的 $f \in C (X)$ , 我们有 $∥ T_{n}^{'} f - T f ∥_{\infty} \leq ∥ T_{n}^{'} f - T_{n} f ∥_{\infty} + ∥ T_{n} f - T f ∥_{\infty} .$

•

第二项由定义即为 $∥ T_{n} f - T f ∥_{\infty} = x \in X sup ∣ ∣ ∣ ∣ ∣ \int_{X} h (x, y) f (y) d P_{n} (y) - \int_{X} h (x, y) f (y) d P (y) ∣ ∣ ∣ ∣ ∣,$ 根据 $f \cdot H$ 是 Glivenko-Cantelli 类可知其 a.s. 收敛到 0;

•

对于第一项, 由定义及命题 1.2 中对度函数的下界估计, 我们有

∥ T_{n}^{'} f - T_{n} f ∥_{\infty} \leq ∥ f ∥_{\infty} x \in X sup \int_{X} ∣ h_{n} (x, y) - h (x, y) ∣ d P_{n} (y) \leq ∥ f ∥_{\infty} ∥ s ∥_{\infty} x, y \in X sup ∣ ∣ ∣ ∣ ∣ ∣ \frac{1}{d _{n} ( x ) d _{n} ( y )} - \frac{1}{d ( x ) d ( y )} ∣ ∣ ∣ ∣ ∣ ∣ \leq \frac{∥ f ∥ _{\infty} ∥ s ∥ _{\infty}}{l ^{2}} x, y \in X sup ∣ ∣ ∣ ∣ d (x) d (y) - d_{n} (x) d_{n} (y) ∣ ∣ ∣ ∣ \leq \frac{∥ f ∥ _{\infty} ∥ s ∥ _{\infty}}{l ^{2}} x, y \in X sup ∣ ∣ ∣ ∣ ∣ ∣ \frac{d ( x ) d ( y ) - d _{n} ( x ) d _{n} ( y )}{d ( x ) d ( y ) + d _{n} ( x ) d _{n} ( y )} ∣ ∣ ∣ ∣ ∣ ∣ \leq \frac{∥ f ∥ _{\infty} ∥ s ∥ _{\infty}}{2 l ^{3}} x, y \in X sup ∣ d_{n} (x) d_{n} (y) - d (x) d (y) ∣,

而用同样的拆项技巧, 借助命题 1.2 中对度函数的上界估计, 可以进一步得到

x, y \in X sup ∣ d_{n} (x) d_{n} (y) - d (x) d (y) ∣ \leq x, y \in X sup (∣ d_{n} (x) d_{n} (y) - d_{n} (x) d (y) ∣ + ∣ d_{n} (x) d (y) - d (x) d (y) ∣) = x, y \in X sup (∣ d_{n} (x) ∣ ∣ d_{n} (y) - d (y) ∣ + ∣ d (y) ∣ ∣ d_{n} (x) - d (x) ∣) \leq ∥ s ∥_{\infty} x, y \in X sup (∣ d_{n} (y) - d (y) ∣ + ∣ d_{n} (x) - d (x) ∣) = 2 ∥ s ∥_{\infty} x \in X sup ∣ d_{n} (x) - d (x) ∣ = 2 ∥ s ∥_{\infty} x \in X sup ∣ ∣ ∣ ∣ ∣ \int_{X} s (x, y) d P_{n} (y) - \int_{X} s (x, y) d P (y) ∣ ∣ ∣ ∣ ∣,

进而根据

S

是 Glivenko-Cantelli 类, 可知该项也 a.s. 收敛到 0.

$□$

进一步我们可以得到:

命题 6.2.3.3. 在预先假设下, $T_{n}^{'} c c T$ a.s.

证明. 由命题 3.2 我们已经得到逐点收敛性, 故只需证明存在 $N \in N$ , 使得 $⋃_{n > N} (T_{n}^{'} - T) B_{C (X)}$ a.s. 是相对紧的. 注意到这是一个连续函数集合, 我们考虑利用 Arzela-Ascoli 定理加以证明:

•

一致有界性: 根据命题 1.2 中对 $T_{n} ’, T$ 的范数估计, 可以得到 $n \in N, f \in B_{X} sup ∥ (T_{n}^{'} - T) f ∥_{\infty} = n \in N sup ∥ T_{n}^{'} - T ∥_{L (C (X))} \leq \frac{2 ∥ s ∥ _{\infty}}{l};$

•

等度连续性: 我们需要对足够大的 $n$ 及所有 $f \in B_{C (X)}$ , 估计 $∣ ∣ ∣ ∣ [(T_{n}^{'} - T) f] (x) - [(T_{n}^{'} - T) f] (x^{'}) ∣ ∣ ∣ ∣ \leq ∣ ∣ ∣ ∣ (T f) (x) - (T f) (x^{'}) ∣ ∣ ∣ ∣ + ∣ ∣ ∣ ∣ (T_{n}^{'} f) (x) - (T_{n}^{'} f) (x^{'}) ∣ ∣ ∣ ∣ .$

∘

先看第一项, 按照定义以及各函数的上下界估计可以得到 $∣ ∣ ∣ ∣ (T f) (x) - (T f) (x^{'}) ∣ ∣ ∣ ∣ \leq ∥ f ∥_{\infty} \int_{X} ∣ h (x, y) - h (x^{'}, y) ∣ d P (y) \leq y \in X sup ∣ ∣ ∣ ∣ ∣ ∣ \frac{s ( x , y )}{d ( x ) d ( y )} - \frac{s ( x ^{'} , y )}{d ( x ^{'} ) d ( y )} ∣ ∣ ∣ ∣ ∣ ∣ \leq \frac{1}{l ^{3 / 2}} y \in X sup ∣ ∣ ∣ ∣ s (x, y) d (x^{'}) - s (x^{'}, y) d (x) ∣ ∣ ∣ ∣ \leq \frac{1}{l ^{3 / 2}} y \in X sup ∣ ∣ ∣ ∣ (s (x, y) - s (x^{'}, y)) d (x^{'}) - s (x^{'}, y) (d (x) - d (x^{'})) ∣ ∣ ∣ ∣ \leq \frac{∥ s ∥ _{\infty}}{l ^{3}} ∥ s (x, \cdot) - s (x^{'}, \cdot) ∥_{\infty} + \frac{∥ s ∥ _{\infty}}{2 l ^{2}} ∣ d (x) - d (x^{'}) ∣,$ 从而对任意 $ε > 0$ , 存在 $δ > 0$ , 使得只要 $x, x ’$ 的距离小于 $δ_{1}$ , 就有 $∣ ∣ ∣ ∣ (T f) (x) - (T f) (x^{'}) ∣ ∣ ∣ ∣ < \frac{ε}{3};$

∘

对于第二项, 作同样的处理可得 $∣ ∣ ∣ ∣ (T_{n}^{'} f) (x) - (T_{n}^{'} f) (x^{'}) ∣ ∣ ∣ ∣ \leq \frac{∥ s ∥ _{\infty}}{l ^{3}} ∥ s (x, \cdot) - s (x^{'}, \cdot) ∥_{\infty} + \frac{∥ s ∥ _{\infty}}{2 l ^{2}} ∣ d_{n} (x) - d_{n} (x^{'}) ∣,$ 进一步我们需要将含 $d_{n}$ 的项关于足够大的 $n$ 作一致估计 $∣ d_{n} (x) - d_{n} (x^{'}) ∣ \leq ∣ d_{n} (x) - d (x) ∣ + ∣ d (x) - d (x^{'}) ∣ + ∣ d (x^{'}) - d_{n} (x^{'}) ∣ \leq 2 ∥ d_{n} - d ∥_{\infty} + ∣ d (x) - d (x^{'}) ∣ .$

总之有

∣ ∣ ∣ ∣ [(T_{n}^{'} - T) f] (x) - [(T_{n}^{'} - T) f] (x^{'}) ∣ ∣ ∣ ∣ \leq C_{1} ∥ s (x, \cdot) - s (x^{'}, \cdot) ∥_{\infty} + C_{2} ∣ d (x) - d (x^{'}) ∣ + C_{3} ∥ d_{n} - d ∥_{\infty},

其中前两项由空间

X

的紧性, 可知连续函数

s, d

都是一致连续的; 最后一项在命题 3.2 的证明中已经得到 a.s. 收敛到 0 (由

S

是 Glivenko-Cantelli 类) .

$□$

最后, 根据各收敛性的关系, 可知:

推论 6.2.3.4. 在预先假设下, $T_{n}^{'} c T$ a.s.

6.2.4第四步: 谱的收敛性

现在我们已经得到了算子序列的紧收敛性, 我们的最终目的是得到其特征函数的收敛性.

首先由上一节的结论, 可知对任意 $z \in ρ (T)$ , 有 $T_{n} ’ - z I s T - z I$ a.s., 由此我们称算子 $T$ 的近似序列 ${T_{n} ’}$ 在所有 $z \in ρ (T)$ 处是稳定的 [stable] .

由此, 对于 $U^{'}$ 的孤立特征值 $λ \neq = 1$ , 存在其邻域 $Δ \subset C$ 使得 $n \to \infty lim σ (L_{n}^{'}) \cap Δ = n \to \infty lim σ (U_{n}^{'}) \cap Δ = {λ} .$

但是文章中给出了更强的结果:

定理 6.2.4.1. 在预先假设下, 对于 $U^{'}$ 的孤立特征值 $λ \neq = 1$ , 存在其邻域 $Δ \subset C$ 及 $N \in N$ , 使得当 $n > N$ 时, $σ (L_{n}^{'}) \cap Δ = {λ_{n}}$ , 且 $λ_{n} \to λ$ a.s.

进一步, 令算子 $Pr_{n}^{'} : C (X) \to C (X)$ 是关于 $λ_{n}$ 的谱投影, $Pr^{'}$ 是关于 $λ$ 的谱投影, 则 $Pr_{n}^{'} p Pr^{'}$ a.s.

若 $λ$ 是一个单特征值, 则还有特征向量的收敛性: 设 $v_{n} = (v_{n}^{1}, \dots, v_{n}^{n}) = ρ_{n} f_{n}$ 是 $L_{n}^{'}$ 关于 $λ_{n}$ 的特征向量, $f$ 是 $U^{'}$ 关于 $λ$ 的特征函数, 则存在一列 ${a_{n}} \subset {- 1, 1}$ , 使得 $i = 1, \dots, n sup ∣ a_{n} v_{n}^{i} - f (X_{i}) ∣ = ∥ a_{n} v_{n} - ρ_{n} f ∥_{\infty} \leq ∥ a_{n} f_{n} - f ∥_{\infty} \to 0 a.s.$ 特别地, 对任意 $b \in R$ , 集合 ${a_{n} f_{n} > b}$ 收敛到 ${f > b}$ , 即它们的对称差满足 $P ({a_{n} f_{n} > b} △ {f > b}) \to 0 .$

没有搞明白的问题:

1. 怎么保证在 $n$ 足够大时, 这个邻域就只交出 $L_{n}^{'}$ 的一个特征值?

2. 怎么保证 $λ$ 是单根时, $λ_{n}$ 也是单根? 这样才能通过算子序列的强稳定性给出特征向量的收敛性.

名字空间

视图

6.2. 规范方法的收敛性

6.2.1第一步: 构造与 $L_{n}^{'}$ 对应的 $C (X)$ 上算子 $U_{n}^{'}$

6.2.2第二步: 算子 $U_{n}^{'}$ 与矩阵 $L_{n}^{'}$ 的谱关系

6.2.3第三步: 随机算子序列 ${U_{n}^{'}}$ 的收敛性

6.2.4第四步: 谱的收敛性

6.2.1第一步: 构造与 Ln′​ 对应的 C(X) 上算子 Un′​

6.2.2第二步: 算子 Un′​ 与矩阵 Ln′​ 的谱关系

6.2.3第三步: 随机算子序列 {Un′​} 的收敛性

6.2.4第四步: 谱的收敛性

6.2.1第一步: 构造与 $L_{n}^{'}$ 对应的 $C (X)$ 上算子 $U_{n}^{'}$

6.2.2第二步: 算子 $U_{n}^{'}$ 与矩阵 $L_{n}^{'}$ 的谱关系

6.2.3第三步: 随机算子序列 ${U_{n}^{'}}$ 的收敛性