The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

Technical Summary: The Sharp Dimension Bound in the Johnson–Lindenstrauss Lemma

Problem Statement
The paper addresses the fundamental problem of metric embeddings: determining the smallest integer $r$ such that any set of $n$ points in $d$-dimensional Euclidean space, $X \subseteq \mathbb{R}^d$, can be embedded into $\mathbb{R}^r$ with distortion at most $1+\varepsilon$. The Johnson–Lindenstrauss (JL) lemma established an upper bound of $r = O(\varepsilon^{-2} \log n)$. However, the optimal target dimension across the full range of parameters $n, d, \varepsilon$ remained an open question.

Larsen and Nelson conjectured that the optimal dimension is:
$$\Theta\left( \min \left\{ d, n-1, \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2} \right\} \right)$$
While the lower bound for this conjecture was recently established by Alon and Klartag, the upper bound remained unproven. Specifically, it was unknown whether the term $\log(2 + \varepsilon^2 n)$ could replace the standard $\log n$ in the JL bound, particularly in regimes where $\varepsilon^2 n$ is small relative to $n$.

Methodology
The author resolves the conjecture by proving the upper bound, demonstrating that the target dimension can be achieved via a linear map. The proof relies on a novel rank-halving technique rooted in algorithmic discrepancy theory.

1. Rank-Halving Step (Theorem 1.2): The core technical contribution is a lemma stating that for any set of $m$ unit vectors in $\mathbb{R}^{2r}$, there exists a positive-semidefinite matrix $M$ of rank at most $r$ such that the quadratic forms $u_\ell^T M u_\ell$ approximate 1 with an error bounded by $O\left(\sqrt{\frac{\log(2 + m/r^2)}{r}}\right)$.

   • This improves upon standard random Gaussian projections, which yield an error of $O\left(\sqrt{\frac{\log(2 + m)}{r}}\right)$. The improvement stems from replacing $m$ with $m/r^2$ inside the logarithm.
   • The construction of $M$ utilizes an adaptive random walk (Brownian motion) in the space of symmetric matrices. This process is guided by a "partial-coloring" argument similar to the Lovett–Meka edge-walk used in Spencer's theorem.
   • The process evolves a matrix $Q_t$ starting from 0. It freezes eigendirections once eigenvalues reach $\pm 1$ and freezes specific quadratic forms once they reach a barrier $b$. This ensures that the rank decreases while controlling the distortion of the prescribed forms.

2. Iterative Reduction: The main theorem (Theorem 1.1) is derived by iterating the rank-halving step. Starting from the affine span of the point set (dimension $\min\{d, n-1\}$), the dimension is repeatedly halved. The errors introduced at each step form a geometrically summable sequence, allowing the total distortion to be bounded by $1+\varepsilon$ while reducing the dimension to the target $r \approx \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2}$.

3. Connection to Inner Product Sketching: The paper also applies these results to the problem of $\varepsilon$-inner-product sketching. By combining the linear dimension reduction with existing lower-dimensional covering estimates, the author resolves a conjecture by Alon and Klartag regarding the minimum number of bits required to sketch inner products.

Key Results

• Theorem 1.1 (Main Result): For any $n, d \ge 2$, $0 < \varepsilon < 1/2$, and $X \subseteq \mathbb{R}^d$, there exists a linear map $L: \mathbb{R}^d \to \mathbb{R}^r$ with distortion at most $1+\varepsilon$, where:
  $$r \le C \min \left\{ d, n-1, \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2} \right\}$$
  This confirms the Larsen–Nelson conjecture in the affirmative. Notably, the embedding is induced by a linear operator on the ambient space, a stronger condition than the arbitrary (potentially nonlinear) maps allowed in the conjecture.

• Theorem 1.3 (Inner Product Sketching): For configurations in dimension $k$ where $D(n, \varepsilon) \le k \le n$ (with $D(n, \varepsilon) = \varepsilon^{-2}\log(2+\varepsilon^2 n)$), the minimum number of bits $f(n, k, \varepsilon)$ required for an $\varepsilon$-inner-product sketch is $\Theta(n D(n, \varepsilon))$. This closes the gap between the known lower bounds and the upper bounds in the high-dimensional regime.

Significance and Claims
The paper claims to resolve the Larsen–Nelson conjecture regarding the sharp dimension bound for the Johnson–Lindenstrauss lemma. The significance lies in two primary aspects:

1. Optimality: It establishes that the previously known upper bound of $O(\varepsilon^{-2} \log n)$ is not tight for all parameter regimes. Specifically, when $\varepsilon^2 n \ll \log n$, the required dimension is significantly smaller, scaling with $\log(2 + \varepsilon^2 n)$ rather than $\log n$.
2. Linearity: The result proves that this optimal dimension can be achieved by a linear map. Previous lower bounds by Larsen–Nelson and Alon–Klartag held even for nonlinear embeddings, but the upper bound was previously only known to be achievable by linear maps with the weaker $\log n$ factor. This paper shows that linearity does not incur a penalty in the optimal dimension.

The author notes that the matrix construction can be discretized (following the Lovett–Meka framework) to yield an efficient randomized procedure for constructing the embedding operator. The work also provides a complete characterization of the bit complexity for inner-product sketching, settling a conjecture by Alon and Klartag.