Source-linked AI summary
Optimality of the Johnson-Lindenstrauss Lemma
Kasper Green Larsen, Jelani Nelson
TL;DR
The paper addresses the unsettled optimality of the Johnson-Lindenstrauss lemma for general embeddings. It uses a counting argument over a large family of point sets and concludes that JL is optimal across almost the full range of ε considered.
Problem
The optimality of the Johnson-Lindenstrauss lemma had not been settled for general embeddings across a broad range of ε.
Method
A counting argument constructs many distinct point sets and shows that sufficiently low-dimensional spaces cannot contain sufficiently many separated embedded point sets.
Results
The paper finally settles JL optimality and does so for almost the full range of ε.
Takeaways & Limitations
The JL lemma's dimension guarantee is optimal for nearly the full ε range addressed by the paper.
Takeaways & Limitations
A related lower-bound argument incurs a lg(1/ε) factor loss, yielding a weaker bound on m.
Abstract
from arXiv · showhide
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 = Ω(\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 = Ω(\varepsilon^{-2}\lg n/\lg(1/\varepsilon))$ [Wel74, Lev83, Alo03], which is suboptimal for any $\varepsilon = o(1)$.
1 Introduction
The paper settles the optimality of the Johnson–Lindenstrauss lemma for general embeddings across nearly the full relevant ε range, matching its ε^-2 lg n dimension upper bound. It develops a different hard-point-set construction because prior nearly orthogonal constructions admit lower-dimensional nonlinear embeddings in part of this range.
- Motivation: Dimensionality reduction lowers storage, communication bandwidth, and later analysis time while preserving application-relevant geometry.The paper situates the problem in applications including streaming, numerical linear algebra, compressed sensing, graph sparsification, clustering, and nearest-neighbor search.
- Prior bounds: The JL lemma guarantees an embedding into dimension O(ε^-2 lg n), while earlier general-embedding lower bounds fell short by a lg(1/ε) factor.The cited earlier bound is Ω(min{n, ε^-2 lg n / lg(1/ε)}).
- Main result: The lower bound applies over nearly the full ε range because every n-point set has an isometric embedding into dimension at most min{n,d}.The dimension bound follows from the identity map or projection onto the subspace spanned by X.
- Conjecture: The paper conjectures the optimal dimension to be Θ(min{n,d, ε^-2 lg(2+ε^2n)}) for all n, d > 1 and 0 < ε < 1.The conjectured expression differs from the JL upper bound through its lg(2+ε^2n) term.
- Proof approach: The proof uses encoding and counting arguments based on large families of distinct point sets and ε-net size bounds.If the target dimension is too small, R^m cannot contain enough sufficiently different embedded point sets; the construction also encodes rounded vectors by net points.
2 Preliminaries on Covering Convex Bodies
The preliminaries establish covering-number bounds for unit balls and origin-symmetric convex bodies using volume comparison and norm-induced reductions.
- Covering-number bounds: A volume comparison argument yields a standard covering-number bound for unit balls in finite-dimensional normed spaces.The bound is used as the foundational covering result for the section.
- Covering-number bounds: 2^m lg(1+2/ε) translated copies of εB_E suffice to cover the unit ball B_E of any m-dimensional normed space.
- Convex-body reduction: The same covering bound applies to any origin-symmetric convex body T in R^m by using its Minkowski functional as a norm.The body T becomes the unit ball of the norm induced by its Minkowski functional.
3 Lower Bound Proof
The proof constructs many point sets whose embeddings must remain distinguishable, then uses an encoding argument to show that low-dimensional embeddings cannot encode them all. A carefully chosen subspace covering reduces the encoding to O(nm) bits, yielding the optimal lower bound across the stated parameter range.
- Counting strategy: The proof constructs a large family of point sets and argues that their embedded versions must be sufficiently different, while low-dimensional space cannot contain enough such sets.The counting argument assumes all sets embed into R^m and derives a contradiction when m is too small.
- Point-set construction: For each k-subset S, the vector y_S creates a 16ε inner-product gap with e_j depending on whether j belongs to S.Distance preservation implies the mapped inner products remain within an additive 4ε, leaving an 8ε gap.
- Encoding argument: The encoding maps each point set P to an O(nm)-bit string that uniquely determines P, contradicting the number of available encodings when m is too low.The encoding assumes embeddings preserving pairwise distances within the required factor and uses discretized approximations of embedded vectors.
- Encoding argument: The key compression step places the vectors Af(y_S) in an m-dimensional column space and encodes them using a covering of a convex body in that subspace.The covering requires only O(m) bits per y_S, rather than encoding its full d coordinates.
- Final bound: The total encoding length is O(nm), and the resulting bound is m = Ω(ε^-2 lg(ε^2n/lg(1/ε))) in the intermediate analysis.The construction then simplifies this to m = Ω(ε^-2 lg n) for ε > 1/n^0.4999.