1，greedy approach

   通过一个由K的列样本（作为基向量）构成的子空间来估计K。其中基向量的选择是一个最优化问题，嘁优化目标是误差限最小化，为此采用了增量的选择方式（今后将泛读相关的论文），算法采用了probability heuristic方法，其复杂度$O({m}^{2}{n}{l})$,l是从K中随机抽样得到的列的个数，即子空间的基向量个数。

   而在另一个优化后的版本中，采用特征空间中的向量作为子空间的基向量，其算法的复杂度是$O({m}^{2}{n})$。另有一个版本的贪心算法，是乔利斯基分解（Cholesky decomposition）算法的变体。

2，Nystrom method

    给定核矩阵K（大小n*m），从中选m列，于是可用公式${K}={E}{{W}^{-1}}{{E}^{T}}$估算整个K，其中$W \in {R^{m \times m}}$是样本点E的子集。这在上面提到的重要参考文献中有说明。下面也会更详细地叙述该方法。

    这种方法的performance依赖于样本点的选取，而这正是本文着重解决的问题。

3，随机化算法

    这类算法有很多，但都有更广义上的计算目的。但是其中有一个算法（2005）曾用于格拉姆矩阵的估算，与本文的问题是类似的。此算法的基本想法是根据预计算得到的矩阵列向量的二范数服从的概率分布进行抽样。

   Nytrom Method原本是用于求解积分方程的方法。在上一周阅读的文献中，Nystrom Method演化为Nystrom approximation算法，用于估算矩阵及其特征向量。原始积分方程可写成（于上一个不同，多了概率密度函数？）：

$\int {p(y)k(x,y){\phi _i}(y)dy = {\lambda _i}} {\phi _i}(x)$

   其中p(x)是概率密度函数，k是正定核函数，${\lambda _i}$和${\phi _i}$是积分方程的第i个特征值和对应的特征向量。给定q个复合p(x)分布的点的集合${x_1,x_2,x_3,\cdots,x_q}$，类似于Nystrom approximation的推导，可将原始积分方程改写成：

\[\frac{1}{q}\sum\limits_{j = 1}^q {k(x,{x_i}){\phi _i}({x_j})}  = {\lambda _i}{\phi _i}(x)\]

（矩形公式）

   改写成矩阵的形式，为

\[{K^{(q)}}{U^{(q)}} = {U^{(q)}}{\Lambda ^{(q)}}\]

   其中，$K^{(q)}=k(x_i, x_j)$，而${\phi _i}{x_i}={\sqrt q U_{ij}^{(q)}}$, ${\lambda _i} = \Lambda _{ii}^{(q)}/q$

   以上公式我都推导过一遍。上式说明，用Nystrom Method通过大小q不同的样本集，近似计算后都能得到原始积分方程的特征向量和特征值。于是，用很小的q和很大的q，都可以得到特征值和特征向量的估计值。但是误差限是不同的。

   公式

\[{K}={E}{{W}^{-1}}{{E}^{T}} \]

实际上是核Nystrom小秩估计算法的基础，这需要阅读其参考文献方知一二。

    用每个样本点来给离它最近的（原数据集中的）点编号。误差为：

\[\varepsilon  = {\left\| {K - E{W^{ - 1}}{E^T}} \right\|_F}\]

（经推导）

${\left\| {{\varepsilon _{xi,xj}}} \right\|_F} = {\left\| {W + {A_{{\rm{T}}i,{\rm{T}}j}} - (W + {B_{{\rm{T}}i,Z}}){W^{ - 1}}{{(W + {C_{{\rm{T}}i,Z}})}^T}} \right\|_F} \le {\left\| {{A_{{\rm{T}}i,Z}}} \right\|_F} + {\left\| {{B_{{\rm{T}}i,Z}}} \right\|_F} + {\left\| {{C_{{\rm{T}}i,Z}}} \right\|_F} + {\left\| {{B_{{\rm{T}}i,Z}}} \right\|_F}{\left\| {{C_{{\rm{T}}i,Z}}} \right\|_F}{\left\| {{W^{ - 1}}} \right\|_F}$

    用每个样本点来给离它最近的（原数据集中的）点编号。误差为：

    Nystrom approximation的误差限是：

   其中:

${C_X^k}$是依赖于核函数k(x,y)和数据集X的常数。后面说。

$T = \mathop {\max }\limits_k \left| {{S_k}} \right|$,

   考虑

\[\kappa (\left\| {\frac{{x - y}}{\delta }} \right\|)\]

讨论两种不同的核函数：$\kappa (\alpha ) = \exp ( - {\alpha ^2})$和$\kappa (\alpha ) = {(\alpha + \varepsilon )^{ - 1}}$

    利用中值定理和三角不等式，推导得到以下结论：${C_X^k}$可由$\max {[2\kappa '(\xi )/\delta ]^2}$确定。

    对于常用的核，对估计算法最重要的影响因素是e，即用最近的landmark point标记数据集中的点所带来的误差。所以，需要最小化这个误差，才能大大提高Nystrom小秩估计算法的准确度。

    k-means聚类能够找到一个局部最小的量化误差（原因？）。于是，使用由k-means算法得到的k个质心作为抽样点。k越大，使用Nystrom估计算法的准确度越高，当然其计算代价也越高。k-means是很简单的算法，用在核矩阵估计算法上时，能很大程度提高运算效率。

   （k-means聚类是很基础的学习型算法，以后应该阅读参考文献Gersho, A.,Gray, R. 1992. Vector quantization and

signal compression.中相关内容。）

    

后记：

1，本文虽已精读，因为许多推导需要阅读参考文献后才能明白，我将确定阅读这些文献的必要性之后，选择性地阅读，希望对这篇文章有更深入的理解。

2，k-means算法是很基础却很重要的算法，目前仍有许多学者在研究它。今后将继续了解和学习该算法，而不是仅仅到实现KM算法的程度。