2022-04-03 加筆しました。
参考文献
- Using the Nyström Method to Speed Up Kernel Machines, https://proceedings.neurips.cc/paper/2000/hash/19de10adbaa1b2ee13f77f679fa1483a-Abstract.html（2022年3月19日参照）
- NIPS 2000（当時は NIPS）の論文であり、カーネル法の文脈での「Nyström 法」の原論文である。
本記事では $K^{(m)}$ が正則であることを仮定する。$K^{(m)}$ が正則になるように部分データを選ぼう。
[1] で「グラム行列の Nyström 近似の性質」といって式 (10) が示されているがその下にグラム行列の Nyström 近似が右下 $(n-m) \times (n-m)$ ブロックを除いて元のグラム行列と必ず一致するとある。のでこれを確認する。なお、本記事では全データに対するグラム行列 $K^{(n)}$ の固有値分解を部分データに対するグラム行列 $K^{(m)}$ の固有値分解から近似するとき右肩に明示的に $(n,m)$ と表記する。つまり、
$l$ 本目の固有ベクトルの第 $j$ 成分は、$k(X_j, X_i)$ の重みでグラム行列 $K^{(m)}$ の $l$ 本目の固有ベクトルの第 $i$ 成分を足し合わせたものである。
となる。$m $ を明記した理由は、以下のように $\tilde{u}_{l, j}^{(n, m)}$ の場合分けをかきたいが、左辺に $m $ がないとわかりにくいためである。なお、部分データは全データの最初の $m $ 個であることを仮定している。$$
\tilde{\lambda}_{l}^{(n, m)} = n \tilde{\gamma}_{l}^{(m)} = \frac{n}{m} \lambda_{l}^{(m)} , \; \; \tilde{u}_{l, j}^{(n, m)} = \frac{\tilde{\psi}_{l}^{(m)}(X_j)}{\sqrt{n}} = \frac{1}{\lambda_{l}^{(m)}} \sqrt{\frac{m}{n}} \sum_{i=1}^m k(X_j, X_i) u_{l, i}^{(m)}
$$
\tilde{\lambda}_{l}^{(n, m)} = n \tilde{\gamma}_{l}^{(m)} = \frac{n}{m} \lambda_{l}^{(m)} , \; \; \tilde{u}_{l, j}^{(n, m)} = \frac{\tilde{\psi}_{l}^{(m)}(X_j)}{\sqrt{n}} = \frac{1}{\lambda_{l}^{(m)}} \sqrt{\frac{m}{n}} \sum_{i=1}^m k(X_j, X_i) u_{l, i}^{(m)}
$$
$j \leqq m $ についてはシンプルになる。カーネルと固有ベクトルの積が固有値と固有ベクトルの積に化ける。
$j > m $ についてはシンプルにならない。
それで、上の場合分けが成り立つので、下の場合分けが成り立つ。2つ目と3つ目には $K^{(m)}$ の直交行列で対角化されること $\sum_{l=1}^{m} u_{l, j}^{(m)} u_{l, i}^{(m)} = \delta_{i=j}$ を用いた。$j > m $ についてはシンプルにならない。
$$
\tilde{u}_{l, j}^{(n, m)} =
\begin{cases}
\displaystyle \sqrt{\frac{m}{n}} u_{l, j}^{(m)} & (j \leqq m)\\
\displaystyle \frac{1}{\lambda_{l}^{(m)}} \sqrt{\frac{m}{n}} \sum_{i=1}^m k(X_j, X_i) u_{l, i}^{(m)} & (j > m)
\end{cases}
$$
\tilde{u}_{l, j}^{(n, m)} =
\begin{cases}
\displaystyle \sqrt{\frac{m}{n}} u_{l, j}^{(m)} & (j \leqq m)\\
\displaystyle \frac{1}{\lambda_{l}^{(m)}} \sqrt{\frac{m}{n}} \sum_{i=1}^m k(X_j, X_i) u_{l, i}^{(m)} & (j > m)
\end{cases}
$$
$$
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, j}^{(n, m)} \tilde{u}_{l, j'}^{(n, m)} =
\begin{cases}
\displaystyle \sum_{l=1}^{m} \lambda_{l}^{(m)} u_{l, j}^{(m)} u_{l, j'}^{(m)} = k(X_j, X_{j'}) & (j \leqq m, j' \leqq m) \\
\displaystyle \sum_{l=1}^{m} \lambda_l^{(m)} u_{l, j}^{(m)} \left( \sum_{i=1}^m \frac{k(X_i, X_{j'}) u_{l, i}^{(m)}}{\lambda_l^{(m)} } \right) = k(X_j, X_{j'}) & (j \leqq m, j' > m) \\
\displaystyle \sum_{l=1}^{m} \sum_{i=1}^{m} \lambda_l^{(m)} \left( \frac{k(X_i, X_{j}) u_{l, i}^{(m)}}{\lambda_l^{(m)}} \frac{k(X_i, X_{j'}) u_{l, i}^{(m)}}{\lambda_l^{(m)}} \right) & (j > m, j' > m) \\
\end{cases}
$$
この場合分けを $K^{(n)}$ の Nyström 近似 $\tilde{K}^{(n,m)}$ に当てはめると、$\tilde{K}^{(n,m)}$ は右下 $(n-m) \times (n-m)$ ブロックを除いて必ず元の $K^{(n)}$ と一致する。右下 $(n-m) \times (n-m)$ ブロックは一般に一致しないが、一致することもある。例えば $j > m, j' > m $ であっても $X_j, X_{j'}$ が $m $ 番目までに登場するデータと重複していれば$(j, j')$ 成分は元の $K^{(n)}$ のそれと一致する。\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, j}^{(n, m)} \tilde{u}_{l, j'}^{(n, m)} =
\begin{cases}
\displaystyle \sum_{l=1}^{m} \lambda_{l}^{(m)} u_{l, j}^{(m)} u_{l, j'}^{(m)} = k(X_j, X_{j'}) & (j \leqq m, j' \leqq m) \\
\displaystyle \sum_{l=1}^{m} \lambda_l^{(m)} u_{l, j}^{(m)} \left( \sum_{i=1}^m \frac{k(X_i, X_{j'}) u_{l, i}^{(m)}}{\lambda_l^{(m)} } \right) = k(X_j, X_{j'}) & (j \leqq m, j' > m) \\
\displaystyle \sum_{l=1}^{m} \sum_{i=1}^{m} \lambda_l^{(m)} \left( \frac{k(X_i, X_{j}) u_{l, i}^{(m)}}{\lambda_l^{(m)}} \frac{k(X_i, X_{j'}) u_{l, i}^{(m)}}{\lambda_l^{(m)}} \right) & (j > m, j' > m) \\
\end{cases}
$$
$$
\begin{align}
\tilde{K}^{(n,m)} &= \begin{pmatrix}
\tilde{u}_{1,1}^{(n, m)} & \tilde{u}_{2,1}^{(n, m)} & \cdots & \tilde{u}_{m,1}^{(n, m)} \\
\tilde{u}_{1,2}^{(n, m)} & \tilde{u}_{2,2}^{(n, m)} & \cdots & \tilde{u}_{m,2}^{(n, m)} \\
\vdots & \vdots & \ddots & \vdots \\
\tilde{u}_{1,n}^{(n, m)} & \tilde{u}_{2,n}^{(n, m)} & \cdots & \tilde{u}_{m,n}^{(n, m)} \\
\end{pmatrix}
\begin{pmatrix}
\tilde{\lambda}_{1}^{(n, m)} & 0 & \cdots & 0 \\
0 & \tilde{\lambda}_{2}^{(n, m)} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \tilde{\lambda}_{m}^{(n, m)} \\
\end{pmatrix}
\begin{pmatrix}
\tilde{u}_{1,1}^{(n, m)} & \tilde{u}_{1,2}^{(n, m)} & \cdots & \tilde{u}_{1,n}^{(n, m)} \\
\tilde{u}_{2,1}^{(n, m)} & \tilde{u}_{2,2}^{(n, m)} & \cdots & \tilde{u}_{2,n}^{(n, m)} \\
\vdots & \vdots & \ddots & \vdots \\
\tilde{u}_{m,1}^{(n, m)} & \tilde{u}_{m,2}^{(n, m)} & \cdots & \tilde{u}_{m,n}^{(n, m)} \\
\end{pmatrix} \\
&= \begin{pmatrix}
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} {\tilde{u}_{l, 1}^{(n, m)}}^2 & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} & \cdots & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \\
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} {\tilde{u}_{l, 2}^{(n, m)}}^2 & \cdots & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} & \cdots & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} {\tilde{u}_{l, n}^{(n, m)}}^2 \\
\end{pmatrix}
\end{align}
$$
話が前後するが、\begin{align}
\tilde{K}^{(n,m)} &= \begin{pmatrix}
\tilde{u}_{1,1}^{(n, m)} & \tilde{u}_{2,1}^{(n, m)} & \cdots & \tilde{u}_{m,1}^{(n, m)} \\
\tilde{u}_{1,2}^{(n, m)} & \tilde{u}_{2,2}^{(n, m)} & \cdots & \tilde{u}_{m,2}^{(n, m)} \\
\vdots & \vdots & \ddots & \vdots \\
\tilde{u}_{1,n}^{(n, m)} & \tilde{u}_{2,n}^{(n, m)} & \cdots & \tilde{u}_{m,n}^{(n, m)} \\
\end{pmatrix}
\begin{pmatrix}
\tilde{\lambda}_{1}^{(n, m)} & 0 & \cdots & 0 \\
0 & \tilde{\lambda}_{2}^{(n, m)} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \tilde{\lambda}_{m}^{(n, m)} \\
\end{pmatrix}
\begin{pmatrix}
\tilde{u}_{1,1}^{(n, m)} & \tilde{u}_{1,2}^{(n, m)} & \cdots & \tilde{u}_{1,n}^{(n, m)} \\
\tilde{u}_{2,1}^{(n, m)} & \tilde{u}_{2,2}^{(n, m)} & \cdots & \tilde{u}_{2,n}^{(n, m)} \\
\vdots & \vdots & \ddots & \vdots \\
\tilde{u}_{m,1}^{(n, m)} & \tilde{u}_{m,2}^{(n, m)} & \cdots & \tilde{u}_{m,n}^{(n, m)} \\
\end{pmatrix} \\
&= \begin{pmatrix}
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} {\tilde{u}_{l, 1}^{(n, m)}}^2 & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} & \cdots & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \\
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} {\tilde{u}_{l, 2}^{(n, m)}}^2 & \cdots & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \\
\vdots & \vdots & \ddots & \vdots \\
\sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \tilde{u}_{l, 1}^{(n, m)} & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} \tilde{u}_{l, n}^{(n, m)} \tilde{u}_{l, 2}^{(n, m)} & \cdots & \sum_{l=1}^{m} \tilde{\lambda}_{l}^{(n, m)} {\tilde{u}_{l, n}^{(n, m)}}^2 \\
\end{pmatrix}
\end{align}
$$
$$
\begin{align}
\tilde{K}^{(n,m)} &= \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} {\tilde{\Lambda}^{(n,m)}}^{-1} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \frac{m}{n} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} {\Lambda^{(m)}}^{-1} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \frac{m}{n} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} U^{(m) \top} U^{(m)} {\Lambda^{(m)}}^{-1} U^{(m) \top} U^{(m)} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \left( \sqrt{\frac{m}{n}} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} U^{(m) \top} \right) {K^{(m)}}^{-1} \left( \sqrt{\frac{m}{n}} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} U^{(m) \top} \right)^{\top} \\
\end{align}
$$
であるが、この ${K^{(m)}}^{-1}$ を挟んでいる行列は $\tilde{K}^{(n,m)}$ を $m $ 列目で打ち切ったものであり、$\tilde{K}^{(n,m)}$ は $m $ 列目までは $K^{(n)}$ と一致していることから式 (10) が成り立つこともわかる。
\begin{align}
\tilde{K}^{(n,m)} &= \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} {\tilde{\Lambda}^{(n,m)}}^{-1} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \frac{m}{n} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} {\Lambda^{(m)}}^{-1} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \frac{m}{n} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} U^{(m) \top} U^{(m)} {\Lambda^{(m)}}^{-1} U^{(m) \top} U^{(m)} \tilde{\Lambda}^{(n,m)} \tilde{U}^{(n,m) \top} \\
&= \left( \sqrt{\frac{m}{n}} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} U^{(m) \top} \right) {K^{(m)}}^{-1} \left( \sqrt{\frac{m}{n}} \tilde{U}^{(n,m)} \tilde{\Lambda}^{(n,m)} U^{(m) \top} \right)^{\top} \\
\end{align}
$$
