次元削減手法の一つ. 削減後の次元数を \(K\),データ数を \(N\) としたとき,主成分分析や多次元尺度構成法は \(O(N^2K)\) の計算量が必要.これを,削減による歪みは大きくなるが,計算量は \(O(NK)\) で抑えられる
オリジナルのデータを \(\mathbf{x}_i^{(0)}\) とする. 第\(k-1\)次元目までの座標値が計算済みのとき,第\(k\)次元目の座標値を求める.
二つの十分に離れた二つのデータ点 \(\mathbf{x}_a^{(k-1)}\) と \(\mathbf{x}_b^{(k-1)}\) を選ぶ. それ以外の点 \(\mathbf{x}_i^{(k-1)}\) は,\(\mathbf{x}_a^{(k-1)}\) と \(\mathbf{x}_b^{(k-1)}\) を結ぶ直線に垂直に射影し,その垂線の足と \(\mathbf{x}_a^{(k-1)}\) の間の距離を,\(k\)次元目での座標値 \(\mathbf{x}_i^{(k)}\) とする.
\(\mathbf{x}_a^{(k-1)}\) と \(\mathbf{x}_b^{(k-1)}\) に垂直な,\(N-k\)次元の部分空間中で,再度この手続きを\(K\)回繰り返せば次元削減ができる. これには,この部分空間中での距離が必要になるが,これも簡単な幾何的関係から計算できる点がポイント.
-- しましま