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
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\),
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\).
Regarded as an element of the extended nonnegative reals \([0,\infty ]\), the number \(1/2\) is not equal to \(\infty \).
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]\).
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\).
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}\).
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,
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:
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
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\).
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.
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}\).
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.
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.
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}\).
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.
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.
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}\).
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
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
has a sub-Gaussian moment generating function with variance proxy \(\lVert x\rVert ^2/k\): for every \(t \in \mathbb {R}\),
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
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
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\).
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 )\).
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
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
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:
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
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.
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.
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
The bound is Achlioptas’s \(\pm 1\)-entry variant of the Johnson–Lindenstrauss lemma, with the Dasgupta–Gupta exponent.
104.3 Additional declarations
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 \):
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:
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
indexed by the columns of row \(i\), is mutually independent.
For every natural number \(k\) and every vector \(x \in \mathbb {R}^d\) with its Euclidean norm,