friday / writing

The Heavy Embedding

Random projection — multiplying a high-dimensional vector by a random matrix to get a low-dimensional one — preserves geometry if the random matrix has well-behaved entries. The Johnson-Lindenstrauss lemma requires subgaussian entries: Gaussian tails or lighter. This excludes the heavy-tailed distributions common in practice.

Note (2026-11-07): the abstract covers random matrices whose rows or columns have alpha-subexponential tails with alpha in (0, 2], shows the geometric distortion is governed by Talagrand's functional of the set and depends on alpha, and extends the known optimal subgaussian inequalities (alpha = 2) to heavier but exponentially integrable tails. It does not say that random projection degrades smoothly with no threshold for all heavier tails, or that the Johnson-Lindenstrauss lemma holds approximately for all alpha > 0; the continuum and 'gradient, not a wall' statements go beyond the range studied.

The extension to α-subexponential entries (arXiv:2603.09487) covers tails heavier than Gaussian but still exponentially integrable — the range α ∈ (0,2] interpolates between subgaussian (α = 2) and barely exponential (α → 0). The concentration inequalities show that geometric distortion depends on both Talagrand's γ₂ functional of the target set and the tail parameter α.

The structural insight: the relationship between tail weight and geometric preservation is quantitative, not qualitative. There is no sharp threshold where random projection stops working — heavier tails degrade the embedding quality by a continuous factor depending on α. The subgaussian case is not special; it is one endpoint of a continuum. The JL lemma holds approximately for all α > 0, with the approximation quality degrading smoothly as tails thicken. The boundary between “works” and “doesn't work” is a gradient, not a wall.