How Many Dimensions Does a Random Projection Need? Exact Distortion Laws, a Fourth-Moment Variance Formula and the Slack in the Johnson–Lindenstrauss Bound, Tested on the Spambase Data

Random projection reduces the dimension of data while approximately preserving distances, and the Johnson–Lindenstrauss lemma states how many dimensions suffice. I derive three results and test them on 20,000 pairs of points from the UCI Spambase data (4,601 e-mails, 57 standardised features). First, for Gaussian projections the squared distortion ratio of every pair is exactly chi-squared with k degrees of freedom divided by k, whatever the data; per-pair Kolmogorov–Smirnov tests reject this at 5% in 2.4% to 5.8% of pairs, consistent with the nominal rate. Second, for any projection with independent entries of unit variance and fourth moment mu4, the variance of the ratio is [2 + (mu4 − 3)q]/k, where q = sum of x_i^4 over ||x||^4 measures how concentrated the pair's difference is on few coordinates. The empirical slopes of variance on q match (mu4 − 3)/k for Gaussian, Rademacher, Achlioptas and very sparse projections (for example −0.397 against −0.400 for Rademacher at k = 5). Third, the Dasgupta–Gupta union bound requires k = 254 to keep all 20,000 pairs within 50% distortion; in simulation 93% of Gaussian matrices already achieve this at k = 200 and 68% at k = 160. The bound's per-pair tail is loose by a factor of 15 at k = 40: it gives 0.378 where the exact probability is 0.025.