106 Learning Theory — Johnson–Lindenstrauss Main
106.1 Overview
This module assembles the complete Johnson–Lindenstrauss flattening lemma. Starting from the distortion predicate and the bad-event definitions, it applies a Gaussian (or sub-Gaussian Rademacher) concentration bound and a union bound to show, via the probabilistic method, that for any finite set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points and any \(0 \lt \varepsilon \lt 1\), a random \(k \times d\) matrix with \(k \ge 32 \log n / \varepsilon ^2\) rows is, with positive probability, an \(\varepsilon \)-JL embedding of \(V\); it then extracts the deterministic witness and provides both squared-distance and distance-form corollaries together with explicit logarithmic dimension bounds.
106.2 Declarations
For \(\varepsilon \in \mathbb {R}\), vectors \(u, v \in \mathbb {R}^d\), and their images \(u', v' \in \mathbb {R}^k\), JLDistortion asserts the two-sided squared-distance inequality
A linear map \(f : \mathbb {R}^d \to _L[\mathbb {R}] \mathbb {R}^k\) is an \(\varepsilon \)-JL embedding of a finite set \(V\) if, for every ordered pair \((u, v) \in V \times V\), the pair \((f(u), f(v))\) satisfies JLDistortion \(\varepsilon \; u\; v\).
Given a \(k \times d\) matrix \(A\) and a finite set \(V \subseteq \mathbb {R}^d\), BadPair \(\varepsilon \; V\; A\) holds when there exists some ordered pair \((u, v) \in V \times V\) whose images under \(A\) fail the distortion predicate, i.e. the projection distorts that pair by more than a factor of \(\varepsilon \).
Let \(A\) be a random \(k \times d\) matrix whose entries are i.i.d. \(\mathcal{N}(0, 1/k)\) (rows mutually independent, entries independent within each row). For any fixed \(x \in \mathbb {R}^d\) and any \(0 \lt \varepsilon \lt 1\),
If the matrix \(A\) does not trigger the bad-single event for the difference \(u - v\), then JLDistortion \(\varepsilon \; u\; v\; (A.toEuclideanLin\; u)\; (A.toEuclideanLin\; v)\) holds; that is, the squared-distance of the images is within a factor of \((1 \pm \varepsilon )\) of the squared-distance of the originals.
Suppose each per-pair bad event satisfies \(\Pr [\text{BadSingle}\; \varepsilon \; A\; \cdot ] \le 2\exp (-k\varepsilon ^2/8)\). Then the probability that some ordered pair in \(V \times V\) is distorted is at most
Let \(A\) be a random Gaussian \(k \times d\) matrix as above. If the union-bound failure probability satisfies \(|V|^2 \cdot 2\exp (-k\varepsilon ^2/8) \lt 1\), then there exists a linear map \(f : \mathbb {R}^d \to _L \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\), extracted from the positive-measure good event.
Sub-Gaussian analogue of johnson_lindenstrauss_of_gaussian: the Gaussian entry hypotheses are replaced by the assumptions that each row projection \((Ax)_i\) is sub-Gaussian with parameter \(\| x\| ^2/k\) and has variance exactly \(\| x\| ^2/k\). Under the same failure-probability bound \(|V|^2 \cdot 2\exp (-k\varepsilon ^2/8) \lt 1\), an \(\varepsilon \)-JL embedding of \(V\) is guaranteed to exist; this covers, for instance, Rademacher (\(\pm 1/\sqrt{k}\)) matrices.
For any measurable map \(A : \Omega \to \mathrm{Matrix}(\mathrm{Fin}\, k, \mathrm{Fin}\, d,\mathbb {R})\), fixed \(x \in \mathbb {R}^d\), and \(\varepsilon \in \mathbb {R}\), the set \(\{ \omega \mid \text{BadSingle}\; \varepsilon \; (A\, \omega )\; x\} \) is measurable. The key step is that each coordinate map \(\omega \mapsto (A\, \omega \cdot \text{toEuclideanLin}\; x)_i\) is measurable, hence so is the squared norm.
For any \(k \gt 0\) and \(d \ge 0\), there exists a probability space \((\Omega , \mathcal{F}, \mu )\) carrying a measurable random matrix \(A : \Omega \to \mathrm{Matrix}(\mathrm{Fin}\, k, \mathrm{Fin}\, d, \mathbb {R})\) whose entries are i.i.d. \(\mathcal{N}(0, 1/k)\), with rows mutually independent and entries within each row jointly independent.
Given \(0 \lt \varepsilon \), \(n \ge 2\), \(k \ge 32 \log n / \varepsilon ^2\), and \(|V| \le n\), this lemma derives (i) \(k \gt 0\) and (ii) \(|V|^2 \cdot 2\exp (-k\varepsilon ^2/8) \lt 1\), the numerical precondition consumed by both johnson_lindenstrauss_of_gaussian and johnson_lindenstrauss_of_subgaussian.
For any \(0 \lt \varepsilon \lt 1\), \(n \ge 2\), \(k \ge 32 \log n / \varepsilon ^2\), and any finite set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points, there exists a linear map \(f : \mathbb {R}^d \to _L \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\), i.e. it satisfies \((1 - \varepsilon )\| u-v\| ^2 \le \| f(u)-f(v)\| ^2 \le (1+\varepsilon )\| u-v\| ^2\) for all \(u, v \in V\).
Rademacher (\(\pm 1/\sqrt{k}\) entries) analogue of johnson_lindenstrauss: same hypotheses on \(\varepsilon \), \(n\), \(k\), and \(V\), same conclusion—an \(\varepsilon \)-JL embedding of \(V\) exists—but now realized by a Rademacher matrix. The proof uses the sub-Gaussian concentration bound jl_concentration_single_subgaussian (which inherits the Hanson-Wright axiom) and the identical union-bound argument.
If \(f\) is an \(\varepsilon \)-JL embedding of \(V\) (in the squared-distance sense), then for all \(u, v \in V\),
obtained by taking square roots of the JLDistortion bounds.
Under the same hypotheses as johnson_lindenstrauss, there exists a linear map \(f : \mathbb {R}^d \to _L \mathbb {R}^k\) such that for all \(u, v \in V\),
Under the same hypotheses as johnson_lindenstrauss_subgaussian, there exists a linear map \(f : \mathbb {R}^d \to _L \mathbb {R}^k\) satisfying the same two-sided distance-ratio bounds as johnson_lindenstrauss_dist, now realized by a Rademacher random matrix.
For any \(0 \lt \varepsilon \lt 1\) and \(n \ge 2\), there exists a threshold \(k_0 \in \mathbb {N}\) such that for every \(k \ge k_0\), every ambient dimension \(d\), and every set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points, an \(\varepsilon \)-JL embedding \(f : \mathbb {R}^d \to _L \mathbb {R}^k\) of \(V\) exists. In particular the target dimension is \(O(\log n / \varepsilon ^2)\).
Sub-Gaussian (Rademacher) analogue of johnson_lindenstrauss_dim_bound: same threshold \(k_0 = O(\log n / \varepsilon ^2)\), same universal conclusion for all \(k \ge k_0\), \(d\), and \(V\) of size at most \(n\), but inheriting the Hanson-Wright axiom from the sub-Gaussian concentration chain.