COMPX270 — Chapter 7 Supplement
Mathematical Foundations: NN & Dimensionality Reduction
Metric spaces, norms, random Gaussian vectors, matrix-vector products, chi-squared concentration, and the union bound that makes JL work.
Metric Spaces
A metric space is a pair \((X, \text{dist})\) where \(X\) is a set and \(\text{dist} : X \times X \to [0, \infty)\) satisfies:
- Identity of indiscernibles: \(\text{dist}(x, y) = 0 \iff x = y\)
- Symmetry: \(\text{dist}(x, y) = \text{dist}(y, x)\)
- Triangle inequality: \(\text{dist}(x, z) \leq \text{dist}(x, y) + \text{dist}(y, z)\)
Euclidean space: \((\mathbb{R}^d, \ell_2)\) with \(\text{dist}(x, y) = \|x - y\|_2\).
Manhattan space: \((\mathbb{R}^d, \ell_1)\) with \(\text{dist}(x, y) = \|x - y\|_1 = \sum_i |x_i - y_i|\).
Hamming space: \((\{0,1\}^d, \text{Ham})\) with \(\text{Ham}(x, y) = |\{i : x_i \neq y_i\}|\).
Jaccard space: On subsets of \([n]\), \(\text{dist}_J(A, B) = 1 - |A \cap B|/|A \cup B|\).
For \(x, y, z \in \{0,1\}^d\):
- \(\text{Ham}(x, y) = 0 \iff x = y\) (zero differing bits means identical).
- \(\text{Ham}(x, y) = \text{Ham}(y, x)\) (bit differences are symmetric).
- \(\text{Ham}(x, z) \leq \text{Ham}(x, y) + \text{Ham}(y, z)\) (each position where \(x_i \neq z_i\) must have either \(x_i \neq y_i\) or \(y_i \neq z_i\)).
Inner Products & Norms
The standard inner product (dot product) on \(\mathbb{R}^d\) is:
\[\langle x, y \rangle = \sum_{i=1}^{d} x_i y_i\]For \(x \in \mathbb{R}^d\) and \(p \geq 1\):
\[\|x\|_p = \left(\sum_{i=1}^{d} |x_i|^p\right)^{1/p}\]Special cases:
- \(\ell_1\): \(\|x\|_1 = \sum_i |x_i|\) (Manhattan norm)
- \(\ell_2\): \(\|x\|_2 = \sqrt{\sum_i x_i^2} = \sqrt{\langle x, x \rangle}\) (Euclidean norm)
- \(\ell_\infty\): \(\|x\|_\infty = \max_i |x_i|\) (Chebyshev norm)
The \(\ell_p\) distance between \(x\) and \(y\) is simply the \(\ell_p\) norm of their difference:
\[\text{dist}_p(x, y) = \|x - y\|_p\]For Euclidean distance specifically:
\[\|x - y\|_2^2 = \langle x - y, x - y \rangle = \|x\|_2^2 - 2\langle x, y \rangle + \|y\|_2^2\]For unit vectors \(\|x\| = \|y\| = 1\):
\[\|x - y\|_2^2 = 2 - 2\langle x, y \rangle = 2(1 - \cos \alpha)\]where \(\alpha = \arccos(\langle x, y \rangle)\) is the angle between \(x\) and \(y\). Thus:
\[\langle x, y \rangle = \cos \alpha \qquad \text{and} \qquad \|x - y\|_2 = \sqrt{2(1 - \cos \alpha)}\]Random Gaussian Vectors
A random variable \(Z \sim \mathcal{N}(0, 1)\) has probability density:
\[f(z) = \frac{1}{\sqrt{2\pi}} e^{-z^2/2}\]Key properties: \(\mathbb{E}[Z] = 0\), \(\text{Var}[Z] = \mathbb{E}[Z^2] = 1\).
If \(Z_1, Z_2, \ldots, Z_d\) are independent \(\mathcal{N}(0, 1)\), then for any fixed vector \(a = (a_1, \ldots, a_d) \in \mathbb{R}^d\):
\[\sum_{i=1}^{d} a_i Z_i \sim \mathcal{N}\!\left(0, \|a\|_2^2\right)\]That is, a linear combination of independent Gaussians is Gaussian with variance \(\|a\|_2^2\).
Let \(g = (g_1, \ldots, g_d)\) with \(g_i \sim \mathcal{N}(0, 1)\) i.i.d. For any fixed \(u \in \mathbb{R}^d\):
\[\langle g, u \rangle = \sum_{i=1}^{d} g_i u_i \sim \mathcal{N}(0, \|u\|_2^2)\]This is why a random Gaussian vector serves as a natural building block for random projections: the projected length is proportional to the original length.
In the JL construction, we use a \(k \times d\) matrix \(M\) with entries \(M_{ij} \sim \mathcal{N}(0, 1/k)\). Each row \(m_i\) of \(M\) gives:
\[\langle m_i, u \rangle \sim \mathcal{N}(0, \|u\|^2/k)\]The \(1/k\) scaling ensures that \(\mathbb{E}[\|Mu\|^2] = \|u\|^2\), making the projection unbiased.
Matrix-Vector Multiplication as Projection
For a \(k \times d\) matrix \(M\) and a vector \(u \in \mathbb{R}^d\), the product \(Mu \in \mathbb{R}^k\) has components:
\[(Mu)_i = \sum_{j=1}^{d} M_{ij} u_j = \langle m_i, u \rangle\]where \(m_i\) is the \(i\)-th row of \(M\). So \(Mu\) is a vector of \(k\) inner products.
Since matrix multiplication is linear:
\[M(x - y) = Mx - My = \Phi(x) - \Phi(y)\]Therefore, if \(\|Mu\|^2 \approx \|u\|^2\) for all difference vectors \(u = x - y\), then all pairwise distances are approximately preserved.
The squared norm of the projected vector is:
\[\|Mu\|^2 = \sum_{i=1}^{k} \langle m_i, u \rangle^2\]When \(M\) has i.i.d. \(\mathcal{N}(0, 1/k)\) entries, each \(\langle m_i, u \rangle^2\) is \((\|u\|^2/k) \cdot \chi^2(1)\), so:
\[\frac{k \cdot \|Mu\|^2}{\|u\|^2} = \sum_{i=1}^{k} \frac{k \cdot \langle m_i, u \rangle^2}{\|u\|^2} \sim \chi^2(k)\]Concentration of \(\chi^2\) Random Variables
If \(Z_1, \ldots, Z_k\) are i.i.d. \(\mathcal{N}(0, 1)\), then:
\[Y = \sum_{i=1}^{k} Z_i^2 \sim \chi^2(k)\]Properties: \(\mathbb{E}[Y] = k\), \(\text{Var}[Y] = 2k\).
For \(Y \sim \chi^2(k)\) and \(\varepsilon \in (0, 1)\):
\[\Pr\!\left[\left|\frac{Y}{k} - 1\right| > \varepsilon\right] \leq 2\exp\!\left(-\frac{k\varepsilon^2}{8}\right)\]This says \(Y/k\) concentrates around 1 with exponentially decreasing tails.
Connection to JL Lemma
From the previous section, \(k\|Mu\|^2/\|u\|^2 \sim \chi^2(k)\). Setting \(Y = k\|Mu\|^2/\|u\|^2\):
\[\Pr\!\left[\left|\frac{\|Mu\|^2}{\|u\|^2} - 1\right| > \varepsilon\right] = \Pr\!\left[\left|\frac{Y}{k} - 1\right| > \varepsilon\right] \leq 2\exp\!\left(-\frac{k\varepsilon^2}{8}\right)\]Setting \(2\exp(-k\varepsilon^2/8) \leq \delta\) gives:
\[k \geq \frac{8 \ln(2/\delta)}{\varepsilon^2} = O\!\left(\frac{\log(1/\delta)}{\varepsilon^2}\right)\]This is precisely the Distributional JL Lemma (Theorem 36).
If we only used Chebyshev's inequality (\(\Pr[|Y/k - 1| > \varepsilon] \leq 2/(k\varepsilon^2)\)), we would need \(k = O(1/(\delta\varepsilon^2))\), which depends linearly on \(1/\delta\). The sub-exponential concentration gives \(k = O(\log(1/\delta)/\varepsilon^2)\), which is logarithmic in \(1/\delta\). This logarithmic dependence is crucial for the union bound step.
Logarithms & Union Bound
For events \(A_1, A_2, \ldots, A_m\):
\[\Pr\!\left[\bigcup_{i=1}^{m} A_i\right] \leq \sum_{i=1}^{m} \Pr[A_i]\]Application: From One Pair to All Pairs
The Distributional JL Lemma gives: for a single vector \(u\), the projection \(Mu\) preserves \(\|u\|\) within \((1 \pm \varepsilon)\) with probability \(\geq 1 - \delta\), provided \(k = O(\log(1/\delta)/\varepsilon^2)\).
To preserve all \(\binom{n}{2}\) pairwise distances, we apply the union bound:
\[\Pr[\text{any pair fails}] \leq \binom{n}{2} \cdot \delta\]We want this \(\leq \varepsilon_0\) (e.g., \(1/n\)). Setting \(\delta = \varepsilon_0 / \binom{n}{2}\):
\[k = O\!\left(\frac{\log(\binom{n}{2}/\varepsilon_0)}{\varepsilon^2}\right) = O\!\left(\frac{\log n}{\varepsilon^2}\right)\]Suppose \(n = 10{,}000\) points and we want \(\varepsilon = 0.1\). Then:
\[k = O\!\left(\frac{\log 10{,}000}{0.01}\right) = O\!\left(\frac{13.3}{0.01}\right) \approx 1330\]With a constant factor of about 8, this gives \(k \approx 10{,}640\). In practice, much smaller values (e.g., \(k \approx 100\text{--}500\)) often suffice due to conservative bounds.
The \(\log n\) in the JL bound comes from two ingredients:
- Sub-exponential tails: \(\Pr[\text{fail}] \leq e^{-\Theta(k\varepsilon^2)}\), giving \(\delta = e^{-\Theta(k\varepsilon^2)}\), i.e., \(k = O(\log(1/\delta)/\varepsilon^2)\).
- Union bound over \(\binom{n}{2} = O(n^2)\) pairs: We need \(\delta = O(1/n^2)\), so \(\log(1/\delta) = O(\log n)\).
Together: \(k = O(\log n / \varepsilon^2)\). The magic is that the number of dimensions depends on \(\log n\), not on \(n\) or the original dimension \(d\).
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.