|
|
Johnson–Lindenstrauss引理表明高维数据可以被投影到低维空间中，同时近似保持点对之间的距离。
我们需要构造一个随机线性映射 $f: \mathbb{R}^N \to \mathbb{R}^n$，使得对于给定的 $\epsilon \in (0,1)$ 和 $m$ 个点 $\{x_1, \ldots, x_m\}$，
\[
(1-\epsilon) \|x_i - x_j\|_2^2 \leq \|f(x_i) - f(x_j)\|_2^2 \leq (1+\epsilon) \|x_i - x_j\|_2^2 \quad \forall \quad 1 \leq i < j \leq m.
\] |
|
