- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Optimality of the Johnson-Lindenstrauss Lemma
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Optimality of the Johnson-Lindenstrauss Lemma Larsen, Kasper Green
Description
For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} <\eps<1$, we show the existence of a set of $n$ vectors $X\subset \R^d$ such that any embedding $f:X\rightarrow \R^m$ satisfying $$ \forall x,y\in X,\ (1-\eps)\|x-y\|_2^2 \le \|f(x)-f(y)\|_2^2 \le (1+\eps)\|x-y\|_2^2 $$ must have $$ m = \Omega(\eps^{-2} \lg n). $$ This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL’84]. Furthermore, our lower bound holds for nearly the full range of $\eps$ of interest, since there is always an isometric embedding into dimension $\min\{d, n\}$ (either the identity map, or projection onto $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 $\eps, n, d$ [LN’16]. The best previously known lower bound for general $f$ was $m = \Omega(\eps^{-2}\lg n/\lg(1/\eps))$ [W’74,A’03], which is suboptimal for any $\eps = o(1)$.
Item Metadata
Title |
Optimality of the Johnson-Lindenstrauss Lemma
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2017-03-23T15:48
|
Description |
For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} <\eps<1$, we show the existence of a set of $n$ vectors $X\subset \R^d$ such that any embedding $f:X\rightarrow \R^m$ satisfying
$$
\forall x,y\in X,\ (1-\eps)\|x-y\|_2^2 \le \|f(x)-f(y)\|_2^2 \le (1+\eps)\|x-y\|_2^2
$$
must have
$$
m = \Omega(\eps^{-2} \lg n).
$$
This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL’84]. Furthermore, our lower bound holds for nearly the full range of $\eps$ of interest, since there is always an isometric embedding into dimension $\min\{d, n\}$ (either the identity map, or projection onto $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 $\eps, n, d$ [LN’16]. The best previously known lower bound for general $f$ was $m = \Omega(\eps^{-2}\lg n/\lg(1/\eps))$ [W’74,A’03], which is suboptimal for any $\eps = o(1)$.
|
Extent |
43 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Aarhus University
|
Series | |
Date Available |
2017-09-20
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0355694
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Faculty
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International