Let \(k \ge 1\) and let \(A\) be a random \(k \times d\) matrix whose entries \(A_{ij}\) are independent Gaussian random variables, each distributed as \(\mathcal{N}(0, 1/k)\). Then for every fixed vector \(x \in \mathbb {R}^d\) and every \(\varepsilon \) with \(0 \lt \varepsilon \lt 1\), the probability that \(A\) distorts the squared norm of \(x\) by more than a factor \(\varepsilon \) satisfies

Let \((\Omega ,\mu )\) be a probability space, and let \(A\colon \Omega \to \mathbb {R}^{k\times d}\) be a measurable random \(k\times d\) matrix. Fix a finite set \(V\subseteq \mathbb {R}^d\) and a parameter \(\varepsilon \in \mathbb {R}\), and suppose that for every pair \(u,v\in V\) the single-vector bad event for the difference \(u-v\) has probability at most \(2\exp (-k\varepsilon ^2/8)\), that is,

Then the probability of the bad-pair event — that some ordered pair \((u,v)\in V\times V\) fails the two-sided distortion bound \((1-\varepsilon )\| u-v\| ^2 \le \| A(\omega )(u-v)\| ^2 \le (1+\varepsilon )\| u-v\| ^2\) — is at most

Fix dimensions \(d\) and \(k\) with \(k \ge 1\), a distortion parameter \(\varepsilon \in (0,1)\), and a finite set of points \(V \subseteq \mathbb {R}^d\). Let \(A\) be a random \(k \times d\) matrix whose entries \(A_{ij}\) are independent Gaussian random variables, each with mean \(0\) and variance \(1/k\). If the union-bound quantity satisfies

then there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\): for every pair \(u, v \in V\),

Let \(k \ge 1\), and let \(A\) be a random \(k \times d\) real matrix defined on a probability space \((\Omega ,\mu )\), so that for each \(x \in \mathbb {R}^d\) the image \(Ax \in \mathbb {R}^k\) has coordinates \((Ax)_1,\dots ,(Ax)_k\). Suppose that for every \(x \in \mathbb {R}^d\) these \(k\) coordinates are independent, and that each coordinate \((Ax)_i\) is sub-Gaussian with variance proxy \(\| x\| ^2/k\), in the sense that \(t \mapsto e^{t(Ax)_i}\) is integrable and its moment generating function obeys \(\mathbb {E}\! \left[e^{t(Ax)_i}\right] \le \exp \! \bigl(\tfrac {\| x\| ^2}{k}\cdot \tfrac {t^2}{2}\bigr)\) for all \(t \in \mathbb {R}\), and moreover has second moment \(\mathbb {E}\! \left[(Ax)_i^2\right] = \| x\| ^2/k\). Fix \(0 \lt \varepsilon \lt 1\) and a finite set \(V \subseteq \mathbb {R}^d\) satisfying the union bound \(|V|^2 \cdot 2\exp (-k\varepsilon ^2/8) \lt 1\). Then there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\): for all \(u,v \in V\),

Let \(0 \lt \varepsilon \lt 1\) and let \(n \ge 2\) be an integer. Suppose the target dimension \(k\) satisfies \(k \ge 32\, \log n / \varepsilon ^2\). Then for every finite set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\); that is,

for all \(u, v \in V\).

Let \(0 \lt \varepsilon \lt 1\), let \(n \ge 2\) be an integer, and let \(k\) be a target dimension satisfying \(k \ge 32\, \log n / \varepsilon ^2\). Then for every finite set \(V\) of at most \(n\) points in \(\mathbb {R}^d\) there exists a linear map \(f \colon \mathbb {R}^d \to \mathbb {R}^k\) such that every pair \(u, v \in V\) has its squared distance preserved up to a factor \(\varepsilon \):

Let \(\varepsilon \in (0,1)\) and let \(n \ge 2\) be an integer, and suppose the target dimension \(k\) satisfies \(k \ge 32\, \log n / \varepsilon ^2\). Then for every finite set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) such that, for all \(u, v \in V\),

where \(\lVert \cdot \rVert \) denotes the Euclidean norm.

Let \(\varepsilon \in (0,1)\) and let \(n \ge 2\) be an integer. Suppose \(k\) is a natural number with \(k \ge 32\, (\log n)/\varepsilon ^2\), and let \(V\) be a finite set of at most \(n\) points in \(\mathbb {R}^d\). Then there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) such that for all \(u, v \in V\),

Let \(\varepsilon \) be a real number with \(0 \lt \varepsilon \lt 1\), and let \(n \ge 2\) be an integer. Then there is a threshold \(k_0 \in \mathbb {N}\) such that for every target dimension \(k \ge k_0\), every ambient dimension \(d\), and every finite set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points, there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\); that is, for all \(u, v \in V\),

Fix a distortion parameter \(\varepsilon \) with \(0 \lt \varepsilon \lt 1\) and an integer \(n \ge 2\). Then there is a threshold \(k_0 \in \mathbb {N}\) such that for every target dimension \(k \ge k_0\), every source dimension \(d\), and every finite set \(V \subseteq \mathbb {R}^d\) of at most \(n\) points, there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) that is an \(\varepsilon \)-JL embedding of \(V\): that is, \((1-\varepsilon )\, \| u - v\| ^2 \le \| f(u) - f(v)\| ^2 \le (1+\varepsilon )\, \| u - v\| ^2\) for all \(u, v \in V\).