Chi-Squared Variables and Johnson–Lindenstrauss Embedding

SECTION 01Chi-Squared Variables

Example · Sub-Exponential but Not Sub-Gaussian

Let Z ∼ N(0, 1) and X = Z². Then X has a chi-squared distribution with one degree of freedom. For λ < 1/2,

E [e^{λ (X - 1)}] = \frac{e^{- λ}}{\sqrt{1 - 2 λ}}

The MGF is infinite for λ ≥ 1/2, so X is not sub-Gaussian. However, near zero,

\frac{e^{- λ}}{\sqrt{1 - 2 λ}} \leq e^{2 λ^{2}}, | λ | < \frac{1}{4}

This is the sub-exponential MGF bound with parameters (ν, α) = (2, 4).

Formulation · Concentration of a Chi-Squared Variable

Let Z₁, …, Zₙ be independent standard Gaussian variables. Their squared sum Y = ∑ₖ₌₁ⁿ Zₖ² has a chi-squared distribution with n degrees of freedom. By the independent-sum property, Y is sub-exponential with parameters (2√n, 4), and E[Y] = n. Therefore,

P (| \frac{\sum_{k = 1}^{n} {Z_{k}}^{2}}{n} - 1 | \geq t) \leq 2 e^{- \frac{n t^{2}}{8}}, 0 < t < 1

Concentration of chi-squared variables is useful for analyzing random projections.

SECTION 02Johnson–Lindenstrauss Embedding

Setting · Preserve Distances in Fewer Dimensions

Suppose we have N ≥ 2 distinct vectors u₁, …, u_N in ℝᵈ. When d is large, storing and processing them can be expensive. We seek a map F: ℝᵈ → ℝᵐ, with m much smaller than d, that approximately preserves all pairwise distances.

For a tolerance δ ∈ (0, 1), the goal is

1 - δ \leq \frac{{‖ F (u_{i}) - F (u_{j}) ‖}_{2}^{2}}{{‖ u_{i} - u_{j} ‖}_{2}^{2}} \leq 1 + δ, i \neq j

Formulation · A Gaussian Random Projection

Generate a matrix A ∈ ℝᵐˣᵈ with independent N(0, 1) entries and define

F (u) = \frac{A u}{\sqrt{m}}

Claim · A Dimension Bound for Preserving All Pairwise Distances

For δ, ϵ ∈ (0, 1), if

m > \frac{16}{δ^{2}} \log \frac{N}{ϵ}

then, with probability at least 1 − ϵ over A, the distance guarantee holds for every pair of data points.

Proof of the Embedding Claim

(1) Fix a nonzero u ∈ ℝᵈ. Let aₖ be row k of A. Since aₖ is a standard Gaussian vector, the variables ⟨aₖ, u⟩/‖u‖₂ are independent N(0, 1). Thus

\frac{{‖ A u ‖}_{2}^{2}}{{‖ u ‖}_{2}^{2}} = \sum_{k = 1}^{m} {\frac{⟨ a_{k}, u ⟩}{{‖ u ‖}_{2}}}^{2} \sim χ_{m}^{2}

Apply the chi-squared concentration bound:

P (| \frac{{‖ F (u) ‖}_{2}^{2}}{{‖ u ‖}_{2}^{2}} - 1 | \geq δ) \leq 2 e^{- \frac{m δ^{2}}{8}}

(2) Apply this result to each difference uᵢ − uⱼ. There are $(\binom{N}{2}) = \frac{N (N - 1)}{2}$ distinct pairs. The union bound gives

P (\frac{{‖ F (u_{i} - u_{j}) ‖}_{2}^{2}}{{‖ u_{i} - u_{j} ‖}_{2}^{2}} \notin [1 - δ, 1 + δ] for some i < j) \leq N (N - 1) e^{- \frac{m δ^{2}}{8}}

(3) Since N(N − 1) ≤ N², it suffices to make N² exp(−mδ²/8) smaller than ϵ. Taking logs gives

m > \frac{8}{δ^{2}} (2 \log N + \log \frac{1}{ϵ})

The simpler condition m > (16/δ²) log(N/ϵ) is slightly stronger and therefore sufficient.