『Pythonではじめる教師なし学習 ―機械学習の可能性を広げるラベルなしデータの利用』
という本の中で、「Johnson–Lindenstraussの補題」と言うものを知ったのでその紹介です。
これは、(高次元の)ユークリッド空間内の要素をそれぞれの要素間の距離をある程度保ったまま、
別の(低次元の)ユークリッド空間へ線型写像で移せることを主張するものです。
英語版のWikipediaに主張があるので、それを日本語訳しました。
Johnson–Lindenstrauss lemma – Wikipedia
$\varepsilon$を$0 < \varepsilon < 1$とし、$X$を $\mathbb{R}^N$内の$m$点の集合とします。さらに、$n$が$n > 8\log(m)/\varepsilon^2$を満たすとします。
すると、線型写像 $f:\mathbb{R}^N \longrightarrow \mathbb{R}^n$であって、
任意の$u, v \in X$ に対して、
$$
(1-\varepsilon)\|u-v\|^2 \leq \|f(u)-f(v)\|^2 \leq (1+\varepsilon)\|u-v\|^2
$$
を満たすものが存在する。
僕の個人的な感想ですが、この補題のすごいところは$n$の条件に元の次元$N$が含まれていないことです。
$N$が非常に大きな数だった場合に、要素間の距離をそこそこ保ったままはるかに小さな次元に埋め込める可能性を秘めています。
その一方で、$N$が小さく、要素数$m$が極端に大きい場合は、次元削減としての効果はあまり得られません。