solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3484次
Optimality of the Johnson-Lindenstrauss Lemma. (arXiv:1609.02094v2 [cs.IT] UPDATED)
来源于:arXiv
For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} <
\varepsilon<1$, we show the existence of a set of $n$ vectors $X\subset
\mathbb{R}^d$ such that any embedding $f:X\rightarrow \mathbb{R}^m$ satisfying
$$ \forall x,y\in X,\ (1-\varepsilon)\|x-y\|_2^2\le \|f(x)-f(y)\|_2^2 \le
(1+\varepsilon)\|x-y\|_2^2 $$ must have $$ m = \Omega(\varepsilon^{-2} \lg n).
$$ This lower bound matches the upper bound given by the Johnson-Lindenstrauss
lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of
$\varepsilon$ of interest, since there is always an isometric embedding into
dimension $\min\{d, n\}$ (either the identity map, or projection onto
$\mathop{span}(X)$).
Previously such a lower bound was only known to hold against linear maps $f$,
and not for such a wide range of parameters $\varepsilon, n, d$ [LN16]. The
best previously known lower bound for general $f$ was $m =
\Omega(\varepsilon^{-2}\lg n/\lg(1/\varepsilon))$ [Wel74, Lev83, Alo03], which
is subop 查看全文>>