Nyström method得到样本在核空间的近似表示

 

前言

\quad 对于一个样本集合{$x_1,x_2,...,x_n$},以及它们的核矩阵$K\in {\mathbb{R}}^{n\times n}$。Nyström 方法[1,2] 可通过采样的方式，构建一个低秩矩阵$\tilde{K}\in {\mathbb{R}}^{n\times n}$去近似表示原核矩阵，降低核矩阵在计算中的运算代价。同时，也可以得到核空间中样本的向量表示。
 

核空间样本近似表示

\quad 首先，通过采样得到含有 $m$ 个样本的集合：{$c_1,c_2,...,c_m$} 。然后，可以构建全样本核矩阵 $K$ 的近似表示 $\tilde{K}$：

$$\tilde{K}=S{X}^{+}{S}^T\approx K$$

其中，$S_{i,j}=k(x_i,c_j)$, $X_{i,j}=k(c_i,c_j)$，$X^{+}$是 $X$ 的伪逆矩阵。同时，我们可以得到任意一个样本 $x_i$ 在核空间的近似表示：

$$z(x_i)={\tilde{D}}_r^{-\frac{1}{2}}{V}_r^T(k(x_i,c_1),...,k(x_i,c_m){)}^T$$

其中，$D$ 和 $V$ 是核矩阵$X$的特征值以及特征向量，且${\tilde{D}}_r=diag({\tilde{\lambda }}_1,...,{\tilde{\lambda }}_r)$，$V_r=(v_1,...,v_r)$。
 

Nyström 近似表示的示例代码：https://github.com/Kai-Xuan/NYS-Apx/ [link]
 

如果这个内容对于您的研究工作有帮助，我们将非常感激您可以引用我们的文章：[1].

 
参考:

---

1. Chen K X, Wu X J, Wang R, et al. Riemannian kernel based Nyström method for approximate infinite-dimensional covariance descriptors with application to image set classification[C]//2018 24th International conference on pattern recognition (ICPR). IEEE, 2018: 651-656. [link]
2.Yang T, Li Y F, Mahdavi M, Jin R, Zhou Z H. Nyström method vs random fourier features: A theoretical and empirical comparison[C]//Advances in neural information processing systems. 2012: 476-484.