TCSLib

104 Learning Theory — Rademacher

104.1 Overview

This module establishes the Johnson–Lindenstrauss concentration bound for the Rademacher (random \(\pm 1/\sqrt{k}\)) matrix. It proceeds in two layers: a distribution-agnostic sub-Gaussian concentration theorem (jl_concentration_single_subgaussian) is proved first, and then the explicit Rademacher construction is shown to satisfy its hypotheses, yielding the concrete bound \(\Pr [\varepsilon \lVert x\rVert ^2 \lt \left\lvert \lVert Ax\rVert ^2 - \lVert x\rVert ^2\right\rvert ] \leq 2\exp (-k\varepsilon ^2/8)\).

104.2 Declarations

Theorem 104.1 Distribution-agnostic JL single-vector concentration
✓

Let \((\Omega ,\mu )\) be a probability space, let \(A\colon \Omega \to \mathbb {R}^{k\times d}\) be a random matrix with \(k\ge 1\) rows, and let \(x\in \mathbb {R}^d\) be a nonzero vector. Write \((Ax)_i\) for the \(i\)-th coordinate of the image \(Ax\in \mathbb {R}^k\), and suppose that the \(k\) coordinates \((Ax)_1,\dots ,(Ax)_k\) are measurable and mutually independent, that each is sub-Gaussian with variance proxy \(\lVert x\rVert ^2/k\) — meaning \(e^{t(Ax)_i}\) is \(\mu \)-integrable and \(\mathbb {E}_\mu \! \bigl[e^{t(Ax)_i}\bigr]\le \exp \! \bigl((\lVert x\rVert ^2/k)\, t^2/2\bigr)\) for every \(t\in \mathbb {R}\) — and that each has second moment \(\mathbb {E}_\mu \! \bigl[(Ax)_i^2\bigr]=\lVert x\rVert ^2/k\). Then for every \(\varepsilon \) with \(0\lt \varepsilon \lt 1\),

\[ \mu \! \left(\bigl\{ \, \omega : \varepsilon \lVert x\rVert ^2 \lt \bigl|\, \lVert Ax\rVert ^2-\lVert x\rVert ^2\, \bigr|\, \bigr\} \right) \; \le \; 2\exp \! \Bigl(-\tfrac {k\varepsilon ^2}{8}\Bigr). \]
Definition 104.2 Rademacher distribution on \(\mathbb {R}\)
✓
#

The Rademacher distribution \(\mathrm{Rad}\) on \(\mathbb {R}\) is the measure \(\tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\), placing equal mass \(1/2\) at \(-1\) and at \(+1\).

Lemma 104.3 Finiteness of one-half in the extended nonnegative reals
✓
#

Regarded as an element of the extended nonnegative reals \([0,\infty ]\), the number \(1/2\) is not equal to \(\infty \).

Lemma 104.4 Rademacher samples lie in \([-1,1]\)
✓
#

Let \(\mathrm{Rad} = \tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\) be the Rademacher distribution on \(\mathbb {R}\). Then \(\mathrm{Rad}\)-almost every point \(y\) satisfies \(y \in [-1, 1]\).

Lemma 104.5 Integrability under a scaled Dirac measure
✓
#

Fix a point \(a \in \mathbb {R}\), and let \(\delta _a\) denote the Dirac measure concentrated at \(a\). Then every function \(f : \mathbb {R}\to \mathbb {R}\) is integrable with respect to the finite measure \(\tfrac {1}{2}\, \delta _a\).

Lemma 104.6 Integrability against the Rademacher measure
✓
#

Let \(\mathrm{Rad} = \tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\) be the Rademacher distribution on \(\mathbb {R}\). Then every function \(f \colon \mathbb {R}\to \mathbb {R}\) is integrable with respect to \(\mathrm{Rad}\).

Lemma 104.7 Mean of the Rademacher distribution
✓
#

Let \(\mathrm{Rad} = \tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\) be the Rademacher distribution on \(\mathbb {R}\). Then the mean of the identity function against \(\mathrm{Rad}\) vanishes,

\[ \int _{\mathbb {R}} y \, d\mathrm{Rad}(y) = 0. \]
Lemma 104.8 Second moment of the Rademacher distribution
✓
#

Let \(\mathrm{Rad} = \tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\) be the Rademacher distribution on \(\mathbb {R}\), placing equal mass \(1/2\) at \(-1\) and at \(+1\). Then its second moment equals one:

\[ \int _{\mathbb {R}} y^2 \, d\mathrm{Rad}(y) = 1. \]
Lemma 104.9 Identity is sub-Gaussian with variance proxy one under Rademacher
✓

Let \(\mathrm{Rad}\) denote the Rademacher distribution on \(\mathbb {R}\), placing mass \(1/2\) at each of \(-1\) and \(+1\), and regard the identity map as the real random variable \(X\) with law \(\mathrm{Rad}\). Then \(X\) is sub-Gaussian with variance proxy \(1\): its moment generating function satisfies

\[ \mathbb {E}\! \left[e^{tX}\right] \le e^{t^{2}/2} \qquad \text{for every } t \in \mathbb {R}. \]
Definition 104.10 Rademacher matrix sample space
✓
#

The sample space for the Rademacher matrix is \(\mathrm{Fin}\, k \to \mathrm{Fin}\, d \to \mathbb {R}\), i.e. the type of \(k \times d\) arrays of real numbers, indexed by \((i,j) \in \mathrm{Fin}\, k \times \mathrm{Fin}\, d\).

Definition 104.11 Joint Rademacher product measure
✓
#

The joint measure on \(\mathrm{Rad\Omega }(k,d)\) is the product measure \(\bigotimes _{(i,j)} \mathrm{Rad}\), making all \(k \cdot d\) entries i.i.d. Rademacher.

Definition 104.12 Rademacher matrix
✓
#

The Rademacher matrix \(A : \mathrm{Rad\Omega }(k,d) \to \mathbb {R}^{k\times d}\) maps a sample \(\omega \) to the matrix with entries \(A(\omega )_{ij} = \omega _{ij}/\sqrt{k}\), scaling the raw \(\pm 1\) entries by \(1/\sqrt{k}\).

Lemma 104.13 Measurability of the Rademacher matrix map
✓
#

Equip the sample space \(\Omega = \{ \omega : \mathrm{Fin}\, k \to \mathrm{Fin}\, d \to \mathbb {R}\} \) of \(k \times d\) real arrays with its product \(\sigma \)-algebra, and the space \(\mathbb {R}^{k \times d}\) of matrices likewise. Then the map \(A : \Omega \to \mathbb {R}^{k\times d}\) sending \(\omega \) to the matrix with entries \(A(\omega )_{ij} = \omega _{ij}/\sqrt{k}\) is measurable.

Lemma 104.14 Row marginal of the joint Rademacher measure
✓

Fix natural numbers \(k\) and \(d\) and a row index \(i \in \{ 0, \dots , k-1\} \), and consider the joint measure on the set of \(k \times d\) real arrays under which all \(k \cdot d\) entries are independent Rademacher variables, each taking the values \(-1\) and \(+1\) with probability \(\tfrac 12\) apiece. Then the pushforward of this measure along the map that sends an array to its \(i\)-th row, an element of \(\mathbb {R}^d\), equals the \(d\)-fold product \(\bigotimes _{j=1}^{d} \mathrm{Rad}\) of Rademacher distributions.

Lemma 104.15 Entry marginal of the joint Rademacher measure
✓

Let \(\mathrm{Rad} = \tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\) be the Rademacher distribution on \(\mathbb {R}\), and let \(\mu \) be the product measure on the space of \(k \times d\) real arrays \(\omega = (\omega _{ij})\) under which all \(k \cdot d\) entries are independent and \(\mathrm{Rad}\)-distributed. Then for every index \((i,j) \in \mathrm{Fin}\, k \times \mathrm{Fin}\, d\), the pushforward of \(\mu \) along the coordinate projection \(\omega \mapsto \omega _{ij}\) is exactly \(\mathrm{Rad}\).

Lemma 104.16 Independence of the entries within a row
✓

Draw a \(k \times d\) real matrix \(\omega = (\omega _{ij})\) from the joint measure under which all \(k \cdot d\) entries are independent and identically distributed Rademacher variables, each taking the values \(-1\) and \(+1\) with probability \(1/2\). Then for every fixed row index \(i \in \{ 1,\dots ,k\} \), the family of coordinate maps \(\bigl(\omega \mapsto \omega _{ij}\bigr)_{1 \le j \le d}\) — the \(d\) entries lying in row \(i\) — is mutually independent.

Lemma 104.17 Rows of a Rademacher matrix are mutually independent
✓

Equip the space of \(k \times d\) real arrays \(\omega = (\omega _{ij})\) with the joint Rademacher product measure, under which the \(k \cdot d\) entries are independent and each \(\omega _{ij}\) takes the values \(-1\) and \(+1\) with equal probability \(1/2\). For each index \(i \in \{ 1,\dots ,k\} \), let \(R_i\) be the \(i\)-th row, that is, the \(\mathbb {R}^d\)-valued random variable \(\omega \mapsto (\omega _{ij})_{j}\). Then the family \((R_i)_{i}\) of \(k\) rows is mutually independent.

Lemma 104.18 Rademacher entries are sub-Gaussian with variance proxy one
✓

Let \(\omega = (\omega _{ij})\) be a random \(k \times d\) real array whose entries are independent and identically distributed, each taking the values \(-1\) and \(+1\) with probability \(\tfrac {1}{2}\) apiece. Then for every index \(i \in \{ 1,\dots ,k\} \) and \(j \in \{ 1,\dots ,d\} \), the single entry \(\omega _{ij}\) is sub-Gaussian with variance proxy \(1\); that is, its moment generating function satisfies \(\mathbb {E}\! \left[e^{t\, \omega _{ij}}\right] \le e^{t^2/2}\) for every \(t \in \mathbb {R}\).

Lemma 104.19 Scaled Rademacher entry is sub-Gaussian
✓

Fix natural numbers \(k \gt 0\) and \(d\), a vector \(x \in \mathbb {R}^d\), a row index \(i\), and a column index \(j\). Consider the joint Rademacher product measure on the space of \(k \times d\) real arrays \(\omega = (\omega _{ij})\), under which every entry is an independent \(\pm 1\) Rademacher variable (equal to \(-1\) or \(+1\) with probability \(\tfrac 12\) each). Then the scaled entry \(\omega \mapsto (x_j/\sqrt{k})\, \omega _{ij}\) has a sub-Gaussian moment generating function with variance proxy \(x_j^2/k\); that is, its moment generating function is finite and satisfies

\[ \mathbb {E}\! \left[\exp \! \big(t\, (x_j/\sqrt{k})\, \omega _{ij}\big)\right] \le \exp \! \left(\tfrac {1}{2}\, \frac{x_j^2}{k}\, t^2\right) \qquad \text{for all } t \in \mathbb {R}. \]
Lemma 104.20 Rows of a Rademacher projection are sub-Gaussian
✓

Fix an integer \(k \ge 1\) and a dimension \(d\), let \(x \in \mathbb {R}^d\) (with its Euclidean norm), and fix a row index \(i \in \{ 1,\dots ,k\} \). Draw the entries of the Rademacher matrix \(A(\omega )_{ij} = \omega _{ij}/\sqrt{k}\) by making all \(kd\) signs \(\omega _{ij}\) independent Rademacher variables. Then the real random variable

\[ \omega \; \longmapsto \; (A(\omega )\, x)_i \; =\; \frac{1}{\sqrt{k}}\sum _{j} \omega _{ij}\, x_j \]

has a sub-Gaussian moment generating function with variance proxy \(\lVert x\rVert ^2/k\): for every \(t \in \mathbb {R}\),

\[ \mathbb {E}\! \left[e^{\, t\, (A(\omega )x)_i}\right] \; \le \; \exp \! \left(\frac{t^2}{2}\cdot \frac{\lVert x\rVert ^2}{k}\right). \]
Lemma 104.21 Variance of the identity under the Rademacher distribution
✓

Let \(X\) be a real random variable distributed according to the Rademacher distribution \(\mathrm{Rad} = \tfrac 12\delta _{-1} + \tfrac 12\delta _{+1}\), so that \(X\) takes the values \(-1\) and \(+1\) each with probability \(1/2\). Then the variance of \(X\) is

\[ \mathrm{Var}(X) = 1. \]
Lemma 104.22 Variance of a single Rademacher entry
✓

Let \(\omega \) be a \(k \times d\) random array whose entries are independent and identically distributed with the Rademacher distribution \(\tfrac {1}{2}\delta _{-1} + \tfrac {1}{2}\delta _{+1}\), taking each of the values \(-1\) and \(+1\) with probability \(1/2\). Then for every index \((i,j)\) with \(i \in \{ 0,\dots ,k-1\} \) and \(j \in \{ 0,\dots ,d-1\} \), the single entry \(\omega _{ij}\) has variance

\[ \mathrm{Var}(\omega _{ij}) = 1. \]
Lemma 104.23 Mean of a single Rademacher entry
✓

Let \(\omega = (\omega _{ij})\) be a \(k \times d\) array whose entries are independent Rademacher variables, each taking the values \(-1\) and \(+1\) with probability \(\tfrac 12\) apiece. Then for every pair of indices \(i \in \{ 1,\dots ,k\} \) and \(j \in \{ 1,\dots ,d\} \), the entry \(\omega _{ij}\) has mean zero: \(\mathbb {E}[\omega _{ij}] = 0\).

Lemma 104.24 Scaled Rademacher entry lies in \(L^2\)
✓

Fix \(k \gt 0\) and a vector \(x \in \mathbb {R}^d\), and let \(\mu \) be the joint Rademacher product measure on the sample space of \(k \times d\) arrays \(\omega = (\omega _{ij})\). Then for every pair of indices \(i\) and \(j\), the coordinate function \(\omega \mapsto \dfrac {x_j}{\sqrt{k}}\, \omega _{ij}\) is square-integrable with respect to \(\mu \); that is, it belongs to \(L^2(\mu )\).

Lemma 104.25 Variance of a scaled Rademacher entry
✓

Let \(k \gt 0\) and let \(x \in \mathbb {R}^d\). Draw a \(k \times d\) array \(\omega \) whose entries \(\omega _{ij}\) are independent Rademacher variables, each equal to \(-1\) or \(+1\) with probability \(\tfrac {1}{2}\). Then for any indices \(i \in \{ 1,\dots ,k\} \) and \(j \in \{ 1,\dots ,d\} \), the real random variable \(\omega \mapsto (x_j/\sqrt{k})\, \omega _{ij}\) has variance

\[ \mathrm{Var}\! \left[\frac{x_j}{\sqrt{k}}\, \omega _{ij}\right] = \frac{x_j^2}{k}. \]
Lemma 104.26 Variance of a row of a Rademacher projection
✓

Fix an integer \(k \ge 1\), a vector \(x \in \mathbb {R}^d\), and a row index \(i \in \{ 1,\dots ,k\} \). Let \(A\) be the Rademacher matrix drawn from the joint Rademacher product measure, so its \(k \cdot d\) entries \(A_{ij} = \omega _{ij}/\sqrt{k}\) are independent, each equal to \(\pm 1/\sqrt{k}\) with probability \(1/2\). Then the \(i\)-th coordinate of the image \(Ax\) has variance

\[ \mathrm{Var}\! \bigl[(Ax)_i\bigr] = \frac{\lVert x\rVert ^2}{k}. \]
Lemma 104.27 Row projection of the Rademacher matrix has mean zero
✓

Fix integers \(k \gt 0\) and \(d \ge 0\), and let the entries \(\omega _{ij}\), for \(i \in \{ 1,\dots ,k\} \) and \(j \in \{ 1,\dots ,d\} \), be independent Rademacher random variables, each taking the values \(-1\) and \(+1\) with probability \(1/2\). Form the \(k \times d\) random matrix \(M\) with entries \(M_{ij} = \omega _{ij}/\sqrt{k}\). Then for every fixed vector \(x \in \mathbb {R}^d\) and every row index \(i \in \{ 1,\dots ,k\} \), the \(i\)-th coordinate of the image \(Mx\) has expectation zero:

\[ \mathbb {E}\bigl[(Mx)_i\bigr] = 0. \]
Lemma 104.28 Second moment of a single row of a Rademacher projection
✓

Fix integers \(k \gt 0\) and \(d \ge 0\), a vector \(x \in \mathbb {R}^d\), and a row index \(i \in \{ 1, \dots , k\} \). Draw \(\omega \) from the joint Rademacher measure on \(\mathrm{Rad\Omega }(k,d)\), form the Rademacher matrix \(A(\omega ) \in \mathbb {R}^{k \times d}\), and let \((A(\omega )x)_i\) denote the \(i\)-th coordinate of the image of \(x\) under the linear map \(A(\omega )\). Then the second moment of this coordinate is

\[ \mathbb {E}\bigl[\, (A(\omega )x)_i^2\, \bigr] = \frac{\lVert x\rVert ^2}{k}. \]
Lemma 104.29 Independence of the row projections of a Rademacher matrix
✓

Fix natural numbers \(k\) and \(d\), and let the entries of a \(k \times d\) matrix be drawn independently from the Rademacher distribution and each scaled by \(1/\sqrt{k}\), giving a random matrix \(A(\omega ) \in \mathbb {R}^{k \times d}\) whose sample \(\omega \) is distributed according to the joint Rademacher product measure. Then for every fixed vector \(x \in \mathbb {R}^{d}\), the \(k\) real-valued random variables \(\omega \mapsto \bigl(A(\omega )\, x\bigr)_i\), one for each row index \(i \in \{ 1,\dots ,k\} \), are mutually independent.

Lemma 104.30 Measurability of a row of the Rademacher projection
✓
#

Fix natural numbers \(k, d\), a vector \(x \in \mathbb {R}^d\), and an index \(i \in \{ 1, \dots , k\} \). Regard the sample space \(\mathrm{Rad\Omega }(k,d)\) of \(k \times d\) real arrays with its product measurable structure, and for a sample \(\omega \) let \(A(\omega )\) be the Rademacher matrix with entries \(A(\omega )_{ij} = \omega _{ij}/\sqrt{k}\), acting as a linear map \(\mathbb {R}^d \to \mathbb {R}^k\). Then the map \(\omega \mapsto (A(\omega )\, x)_i\), sending each sample to the \(i\)-th coordinate of the image of \(x\), is measurable.

Theorem 104.31 Johnson–Lindenstrauss concentration for a single Rademacher projection
✓

Let \(k \ge 1\) be an integer, let \(x \in \mathbb {R}^d\) be a nonzero vector, and fix \(\varepsilon \) with \(0 \lt \varepsilon \lt 1\). Let \(A\) be the \(k \times d\) matrix whose \(kd\) entries are independent, each taking the values \(+1/\sqrt{k}\) and \(-1/\sqrt{k}\) with probability \(1/2\) apiece. Then the squared norm \(\lVert Ax\rVert ^2\) concentrates about \(\lVert x\rVert ^2\), with the probability of a deviation exceeding \(\varepsilon \lVert x\rVert ^2\) bounded by

\[ \Pr \! \bigl[\, \varepsilon \lVert x\rVert ^2 \lt \bigl|\, \lVert Ax\rVert ^2 - \lVert x\rVert ^2\, \bigr| \, \bigr] \; \le \; 2\exp \! \Bigl(-\frac{k\varepsilon ^2}{8}\Bigr). \]

The bound is Achlioptas’s \(\pm 1\)-entry variant of the Johnson–Lindenstrauss lemma, with the Dasgupta–Gupta exponent.

104.3 Additional declarations

Lemma 104.32 Sub-Gaussian parameter scales quadratically under constant multiples
✓
#

Let \(X\) be a real random variable on a measure space \((\Omega ,\mu )\) that is sub-Gaussian with variance proxy \(\sigma \ge 0\), i.e. \(e^{tX}\) is \(\mu \)-integrable and \(\mathbb {E}_\mu [e^{tX}] \le \exp (\sigma t^2/2)\) for every \(t \in \mathbb {R}\). Then for every constant \(c \in \mathbb {R}\), the scaled variable \(\omega \mapsto c\, X(\omega )\) is sub-Gaussian with variance proxy \(c^2\sigma \):

\[ \mathbb {E}_\mu \! \left[e^{t\, cX}\right] \le \exp \! \left(\tfrac {1}{2}\, c^2\sigma \, t^2\right) \qquad \text{for all } t \in \mathbb {R}. \]
Lemma 104.33 Row projection as a sum of scaled entries
✓

Fix natural numbers \(k, d\), a vector \(x \in \mathbb {R}^d\), and a row index \(i \in \{ 1,\dots ,k\} \). For a sample \(\omega \) in the Rademacher sample space \(\mathrm{Rad\Omega }(k,d)\), let \(A(\omega )\) be the Rademacher matrix with entries \(\omega _{ij}/\sqrt{k}\). Then, as functions of \(\omega \), the \(i\)-th coordinate of the image \(A(\omega )x\) equals the sum of the scaled entries:

\[ \bigl(A(\omega )\, x\bigr)_i = \sum _{j} \frac{x_j}{\sqrt{k}}\, \omega _{ij}. \]
Lemma 104.34 Scaled entries within a row are mutually independent
✓

Fix natural numbers \(k, d\), a vector \(x \in \mathbb {R}^d\), and a row index \(i \in \{ 1,\dots ,k\} \). Under the joint Rademacher product measure on \(\mathrm{Rad\Omega }(k,d)\), the family of real random variables

\[ \omega \; \longmapsto \; \frac{x_j}{\sqrt{k}}\, \omega _{ij}, \qquad j \in \{ 1,\dots ,d\} , \]

indexed by the columns of row \(i\), is mutually independent.

Lemma 104.35 Squared norm over \(k\) as a sum of squared coordinates over \(k\)
✓
#

For every natural number \(k\) and every vector \(x \in \mathbb {R}^d\) with its Euclidean norm,

\[ \frac{\lVert x\rVert ^2}{k} = \sum _{j} \frac{x_j^2}{k}. \]