6.2. 规范方法的收敛性

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

6.2.1第一步: 构造与 $L_n^{\prime }$ 对应的 $C(\mathcal{X})$ 上算子 $U_n^{\prime }$

注意到 $L_n^{\prime }=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 }_{\mathcal{X}}s(x,y)d{P}_n(y),d(x)={\int }_{\mathcal{X}}s(x,y)dP(y)$$
•	规范化相似度函数 [normalized similarity functions] $$h_n(x,y)=\frac{s(x,y)}{\sqrt{d_n(x)d_n(y)}},h(x,y)=\frac{s(x,y)}{\sqrt{d(x)d(y)}}$$
•	积分算子 [integral operators] $$T_n^{\prime }:f\mapsto {\int }_{\mathcal{X}}{h}_n(x,y)f(y)d{P}_n(y),T_n:f\mapsto {\int }_{\mathcal{X}}h(x,y)f(y)d{P}_n(y),T:f\mapsto {\int }_{\mathcal{X}}h(x,y)f(y)dP(y)$$
•	最后得到 $C(\mathcal{X})$ 上的算子 $$U_n^{\prime }=I-T_n^{\prime },U^{\prime }=I-T,$$其中 $I$ 为恒等映射.

以上构造具有如下性质:

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

1.	$d_n,d\in C(\mathcal{X})$, 并且有一致的下界 $l>0$ 及上界 $\Vert s{\Vert }_{\infty }<+\infty$;
2.	$T_n^{\prime },T_n,T$ 的算子范数具有一致的上界 $\Vert s{\Vert }_{\infty }/l$, 且是 $C(\mathcal{X})$ 上的紧算子;
3.	关系式 $L_n^{\prime }\circ {\rho }_n={\rho }_n\circ U_n^{\prime }$ 成立.

6.2.2第二步: 算子 $U_n^{\prime }$ 与矩阵 $L_n^{\prime }$ 的谱关系

按照前面的分析, 我们希望 $f_n\in C(\mathcal{X})$ 是算子 $U_n’$ 的一个特征函数, 即 $U_n^{\prime }{f}_n=\lambda f_n$, 这样就有$$L_n^{\prime }{v}_n=L_n^{\prime }({\rho }_n{f}_n)={\rho }_n(U_n^{\prime }{f}_n)=\lambda {\rho }_n{f}_n=\lambda v_n,$$即 $v_n={\rho }_n{f}_n$ 为 $L_n^{\prime }$ 关于特征值 $\lambda$ 的特征向量. 因此, 我们的目标是找到 $U_n^{\prime }$ 关于 $L_n^{\prime }$ 第二特征值 ${\lambda }_2$ 的特征函数 $f_n\in C(\mathcal{X})$: 将该特征值问题写成$$\begin{array}{rl}(1-{\lambda }_2)f_n(x)=T_n^{\prime }{f}_n(x)& ={\int }_{\mathcal{X}}{h}_n(x,y)f_n(y)d{P}_n(y)\\ & =\frac{1}{n}\sum _{i=1}^{n}h(x,X_i)f_n(X_i)=\frac{1}{n}\sum _{i=1}^{n}h(x,X_i)v_n^i,\end{array}$$故只要 ${\lambda }_2\ne 1$, 我们就有$$f_n(x)=\frac{{\sum }_{i=1}^{n}h(x,X_i)v_n^i}{n(1-{\lambda }_2)}.$$由于 $v_n$ 在每次抽样后可由 $L_n^{\prime }$ 的第二特征向量给出, 故上式给出了 $f_n\in C(\mathcal{X})$ 的确切定义.

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

命题 6.2.2.1. 算子 $U_n^{\prime }$ 与矩阵 $L_n^{\prime }$ 的谱具有如下对应关系:

1.	具有相同的特征值;
2.	关于同一个特征值 $\lambda \ne 1$ 的特征函数 $f\in C(\mathcal{X})$ 及特征向量 $v=(v^1,\cdots ,v^n)\in {\mathbb{R}}^n$ 具有如下的一一对应关系: $$v={\rho }_{n}f,f(x)=\frac{{\sum }_{i=1}^{n}h(x,X_i)v^i}{n(1-\lambda )};$$
3.	$U_n^{\prime }=I-T_n^{\prime }$ 的谱 $\sigma (U_n^{\prime })=\{1\}\cup \sigma (L_n^{\prime })$ 由有限个重数有限的非负特征值和 ${\sigma }_{ess}(U_n^{\prime })=\{1\}$ 组成.

对于特征值的非负性, 与矩阵 $L_n^{\prime }$ 的半正定性$$f^T{L}_n^{\prime }f=\frac{1}{2}\sum _{i,j=1}^n{w}_{ij}{\left(\frac{f_i}{\sqrt{d_i}}-\frac{f_j}{\sqrt{d_j}}\right)}^2\ge 0,\forall f\in {\mathbb{R}}^n$$类似地, 我们也可以将 $U_n^{\prime }$ 视为 $L^2(P_n)$ 函数空间上的算子, 利用函数内积$$\begin{array}{rl}⟨U_n^{\prime }f,f⟩& ={\int }_{\mathcal{X}}\left(f(x)-{\int }_{\mathcal{X}}{h}_n(x,y)f(y)d{P}_n(y)\right)f(x)d{P}_n(x)\\ & ={\int }_{\mathcal{X}}{\int }_{\mathcal{X}}s(x,y)\left(\frac{f(x)}{\sqrt{d_n(x)}}-\frac{f(y)}{\sqrt{d_n(y)}}\right)\frac{f(x)}{\sqrt{d_n(x)}}d{P}_n(y)d{P}_n(x)\\ & =\frac{1}{2}{\int }_{\mathcal{X}}{\int }_{\mathcal{X}}s(x,y){\left(\frac{f(x)}{\sqrt{d_n(x)}}-\frac{f(y)}{\sqrt{d_n(y)}}\right)}^{2}d{P}_n(y)d{P}_n(x)\ge 0,\forall f\in L^2(P_n)\end{array}$$直接得到算子 $U_n$ 的非负性.

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

6.2.3第三步: 随机算子序列 $\{U_n^{\prime }\}$ 的收敛性

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

命题 6.2.3.1. 在预先假设下, 以下 $C(\mathcal{X})$ 的子集$$\begin{array}{rl}\mathcal{S}& :=\{s(x,\cdot ):x\in \mathcal{X}\}\\ \mathcal{H}& :=\{h(x,\cdot ):x\in \mathcal{X}\}\\ g\cdot \mathcal{H}& :=\{g(\cdot )h(x,\cdot ):x\in \mathcal{X}\},\forall g\in C(\mathcal{X})\end{array}$$均为 Glivenko-Cantelli 类, 即成立$$\underset{f\in \mathcal{F}}{\sup }\left|{\int }_{\mathcal{X}}f(y)d{P}_n(y)-{\int }_{\mathcal{X}}f(y)dP(y)\right|\stackrel{n\to \infty }{\to }0\text{a.s.},\mathcal{F}=\mathcal{S},\mathcal{H},g\cdot \mathcal{H}.$$

证明. 以 $\mathcal{S}$ 为例进行证明, 另两个类似: 首先由 $s$ 是紧度量空间 $\mathcal{X}$ 上的连续函数, 可知 $s$ 在 $\mathcal{X}$ 上一致连续, 从而对任意 $\epsilon >0$, 都存在 $\delta >0$, 只要 $x,x^{\prime }\in \mathcal{X}$ 的距离小于 $\delta$, 就有$$\Vert s(x,\cdot )-s(x^{\prime },\cdot ){\Vert }_{\infty }<\epsilon /2.$$而由 $\mathcal{X}$ 的紧性可知存在有限个点 $x_1,\cdots ,x_k\in \mathcal{X}$, 使得$$\mathcal{X}=\bigcup _{i=1}^k(B_{\delta }(x_i)\cap \mathcal{X})⟹\mathcal{S}\subset \bigcup _{i=1}^k{B}_{\epsilon /2}(s(x_i,\cdot )).$$若记括号 $[l,u]$ 表示满足 $l\le f\le u$ 的函数 $f$, 则有$$\mathcal{S}\subset \bigcup _{i=1}^k\left[s(x_i,\cdot )-\frac{\epsilon }{2},s(x_i,\cdot )+\frac{\epsilon }{2}\right],$$其中每个括号的 $L^1(P)$-长度均为 $\epsilon$, 故子集 $\mathcal{S}$ 的 $\Vert \cdot {\Vert }_{L^1(P)}$-括号数 [bracketing number] $N_{[]}(\epsilon ,\mathcal{S},L^1(P))=k<\infty .$ 由 $\epsilon$ 的任意性, 结合 Glivenko-Cantelli 定理 (参考书 Weak Convergence and Empirical Processes 中定理 2.4.1) 即可得到结论.

$\square$

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

命题 6.2.3.2. 在预先假设下, $T_n^{\prime }\stackrel{p}{\to }T$ a.s.

证明. 对任意的 $f\in C(\mathcal{X})$, 我们有$$\Vert T_n^{\prime }f-Tf{\Vert }_{\infty }\le \Vert T_n^{\prime }f-T_{n}f{\Vert }_{\infty }+\Vert T_{n}f-Tf{\Vert }_{\infty }.$$

•

第二项由定义即为 $$\Vert T_{n}f-Tf{\Vert }_{\infty }=\underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}h(x,y)f(y)d{P}_n(y)-{\int }_{\mathcal{X}}h(x,y)f(y)dP(y)\right|,$$根据 $f\cdot \mathcal{H}$ 是 Glivenko-Cantelli 类可知其 a.s. 收敛到 0;

•

对于第一项, 由定义及命题 1.2 中对度函数的下界估计, 我们有 $$\begin{array}{rl}\Vert T_n^{\prime }f-T_{n}f{\Vert }_{\infty }& \le \Vert f{\Vert }_{\infty }\underset{x\in \mathcal{X}}{\sup }{\int }_{\mathcal{X}}|h_n(x,y)-h(x,y)|d{P}_n(y)\\ & \le \Vert f{\Vert }_{\infty }\Vert s{\Vert }_{\infty }\underset{x,y\in \mathcal{X}}{\sup }\left|\frac{1}{\sqrt{d_n(x)d_n(y)}}-\frac{1}{\sqrt{d(x)d(y)}}\right|\\ & \le \frac{\Vert f{\Vert }_{\infty }\Vert s{\Vert }_{\infty }}{l^2}\underset{x,y\in \mathcal{X}}{\sup }\left|\sqrt{d(x)d(y)}-\sqrt{d_n(x)d_n(y)}\right|\\ & \le \frac{\Vert f{\Vert }_{\infty }\Vert s{\Vert }_{\infty }}{l^2}\underset{x,y\in \mathcal{X}}{\sup }\left|\frac{d(x)d(y)-d_n(x)d_n(y)}{\sqrt{d(x)d(y)}+\sqrt{d_n(x)d_n(y)}}\right|\\ & \le \frac{\Vert f{\Vert }_{\infty }\Vert s{\Vert }_{\infty }}{2l^3}\underset{x,y\in \mathcal{X}}{\sup }\left|d_n(x)d_n(y)-d(x)d(y)\right|,\end{array}$$而用同样的拆项技巧, 借助命题 1.2 中对度函数的上界估计, 可以进一步得到 $$\begin{array}{rl}\underset{x,y\in \mathcal{X}}{\sup }\left|d_n(x)d_n(y)-d(x)d(y)\right|& \le \underset{x,y\in \mathcal{X}}{\sup }(\left|d_n(x)d_n(y)-d_n(x)d(y)\right|+\left|d_n(x)d(y)-d(x)d(y)\right|)\\ & =\underset{x,y\in \mathcal{X}}{\sup }(|d_n(x)|\left|d_n(y)-d(y)\right|+|d(y)|\left|d_n(x)-d(x)\right|)\\ & \le \Vert s{\Vert }_{\infty }\underset{x,y\in \mathcal{X}}{\sup }(|d_n(y)-d(y)|+|d_n(x)-d(x)|)\\ & =2\Vert s{\Vert }_{\infty }\underset{x\in \mathcal{X}}{\sup }|d_n(x)-d(x)|\\ & =2\Vert s{\Vert }_{\infty }\underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}s(x,y)d{P}_n(y)-{\int }_{\mathcal{X}}s(x,y)dP(y)\right|,\end{array}$$进而根据 $\mathcal{S}$ 是 Glivenko-Cantelli 类, 可知该项也 a.s. 收敛到 0. $\square$

进一步我们可以得到:

命题 6.2.3.3. 在预先假设下, $T_n^{\prime }\stackrel{cc}{\to }T$ a.s.

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

•

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

•

等度连续性: 我们需要对足够大的 $n$ 及所有 $f\in B_{C(\mathcal{X})}$, 估计 $$|[(T_n^{\prime }-T)f](x)-[(T_n^{\prime }-T)f](x^{\prime })|\le |(Tf)(x)-(Tf)(x^{\prime })|+|(T_n^{\prime }f)(x)-(T_n^{\prime }f)(x^{\prime })|.$$ ∘ 先看第一项, 按照定义以及各函数的上下界估计可以得到 $$\begin{array}{rl}|(Tf)(x)-(Tf)(x^{\prime })|& \le \Vert f{\Vert }_{\infty }{\int }_{\mathcal{X}}|h(x,y)-h(x^{\prime },y)|dP(y)\\ & \le \underset{y\in \mathcal{X}}{\sup }\left|\frac{s(x,y)}{\sqrt{d(x)d(y)}}-\frac{s(x^{\prime },y)}{\sqrt{d(x^{\prime })d(y)}}\right|\\ & \le \frac{1}{l^{3/2}}\underset{y\in \mathcal{X}}{\sup }\left|s(x,y)\sqrt{d(x^{\prime })}-s(x^{\prime },y)\sqrt{d(x)}\right|\\ & \le \frac{1}{l^{3/2}}\underset{y\in \mathcal{X}}{\sup }\left|(s(x,y)-s(x^{\prime },y))\sqrt{d(x^{\prime })}-s(x^{\prime },y)\left(\sqrt{d(x)}-\sqrt{d(x^{\prime })}\right)\right|\\ & \le \sqrt{\frac{\Vert s{\Vert }_{\infty }}{l^3}}\Vert s(x,\cdot )-s(x^{\prime },\cdot ){\Vert }_{\infty }+\frac{\Vert s{\Vert }_{\infty }}{2l^2}|d(x)-d(x^{\prime })|,\end{array}$$从而对任意 $\epsilon >0$, 存在 $\delta >0$, 使得只要 $x,x’$ 的距离小于 ${\delta }_1$, 就有 $$|(Tf)(x)-(Tf)(x^{\prime })|<\frac{\epsilon }{3};$$ ∘ 对于第二项, 作同样的处理可得 $$|(T_n^{\prime }f)(x)-(T_n^{\prime }f)(x^{\prime })|\le \sqrt{\frac{\Vert s{\Vert }_{\infty }}{l^3}}\Vert s(x,\cdot )-s(x^{\prime },\cdot ){\Vert }_{\infty }+\frac{\Vert s{\Vert }_{\infty }}{2l^2}|d_n(x)-d_n(x^{\prime })|,$$进一步我们需要将含 $d_n$ 的项关于足够大的 $n$ 作一致估计 $$\begin{array}{rl}|d_n(x)-d_n(x^{\prime })|& \le |d_n(x)-d(x)|+|d(x)-d(x^{\prime })|+|d(x^{\prime })-d_n(x^{\prime })|\\ & \le 2\Vert d_n-d{\Vert }_{\infty }+|d(x)-d(x^{\prime })|.\end{array}$$ 总之有 $$|[(T_n^{\prime }-T)f](x)-[(T_n^{\prime }-T)f](x^{\prime })|\le C_1\Vert s(x,\cdot )-s(x^{\prime },\cdot ){\Vert }_{\infty }+C_2|d(x)-d(x^{\prime })|+C_3\Vert d_n-d{\Vert }_{\infty },$$其中前两项由空间 $\mathcal{X}$ 的紧性, 可知连续函数 $s,d$ 都是一致连续的; 最后一项在命题 3.2 的证明中已经得到 a.s. 收敛到 0 (由 $\mathcal{S}$ 是 Glivenko-Cantelli 类) . $\square$

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

推论 6.2.3.4. 在预先假设下, $T_n^{\prime }\stackrel{c}{\to }T$ a.s.

6.2.4第四步: 谱的收敛性

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

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

由此, 对于 $U^{\prime }$ 的孤立特征值 $\lambda \ne 1$, 存在其邻域 $\Delta \subset \mathbb{C}$ 使得$$\underset{n\to \infty }{\lim }\sigma (L_n^{\prime })\cap \Delta =\underset{n\to \infty }{\lim }\sigma (U_n^{\prime })\cap \Delta =\{\lambda \}.$$

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

定理 6.2.4.1. 在预先假设下, 对于 $U^{\prime }$ 的孤立特征值 $\lambda \ne 1$, 存在其邻域 $\Delta \subset \mathbb{C}$ 及 $N\in \mathbb{N}$, 使得当 $n>N$ 时, $\sigma (L_n^{\prime })\cap \Delta =\{{\lambda }_n\}$, 且 ${\lambda }_n\to \lambda$ a.s.

进一步, 令算子 ${\text{Pr}}_n^{\prime }:C(\mathcal{X})\to C(\mathcal{X})$ 是关于 ${\lambda }_n$ 的谱投影, ${\text{Pr}}^{\prime }$ 是关于 $\lambda$ 的谱投影, 则 ${\text{Pr}}_n^{\prime }\stackrel{p}{\to }{\text{Pr}}^{\prime }$ a.s.

若 $\lambda$ 是一个单特征值, 则还有特征向量的收敛性: 设 $v_n=(v_n^1,\cdots ,v_n^n)={\rho }_n{f}_n$ 是 $L_n^{\prime }$ 关于 ${\lambda }_n$ 的特征向量, $f$ 是 $U^{\prime }$ 关于 $\lambda$ 的特征函数, 则存在一列 $\{a_n\}\subset \{-1,1\}$, 使得$$\underset{i=1,\cdots ,n}{\sup }|a_n{v}_n^i-f(X_i)|=\Vert a_n{v}_n-{\rho }_{n}f{\Vert }_{\infty }\le \Vert a_n{f}_n-f{\Vert }_{\infty }\to 0\text{a.s.}$$特别地, 对任意 $b\in \mathbb{R}$, 集合 $\{a_n{f}_n>b\}$ 收敛到 $\{f>b\}$, 即它们的对称差满足$$P(\{a_n{f}_n>b\}△\{f>b\})\to 0.$$

没有搞明白的问题:

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

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