Random Projections, Feature Agglomeration, and Compression

Take a corpus that exists and can be downloaded. RCV1-v2 is 804,414 Reuters newswire documents over 47,236 stemmed-word features and 103 Topic categories, described in a benchmark paper in 2004; scikit-learn ships it as fetch_rcv1 and reports the feature matrix as 0.16% non-zero. Pushing 47,236 sparse dimensions through a fixed random matrix costs no fitting pass, no covariance estimate and no second read of the data. Memory and transform time fall. What comes out has no loadings to narrate and no axis anyone can name. It can still be the right engineering choice. Dimensionality reduction does not always need to discover interpretable axes.

Compression strategies differ in what they preserve and whether the mapping is learned from data.

“Random matrix” is vaguer than the literature needs to be. The entries can be coin flips. Achlioptas proved in 2003 that the same guarantee survives when every entry is drawn from {-1, 0, +1} with probabilities 1/6, 2/3, 1/6. Two thirds of the matrix is then zero, and the projection reduces to additions and subtractions: “probability distribution (2) gives an additional threefold speedup as we only need to process a third of all attributes for each of the k coordinates”, in his own words. scikit-learn ships that setting in SparseRandomProjection as density=1/3. Its actual default is sparser still, the 1/sqrt(n_features) recommended in 2006.

The test should reflect the relation and rare evidence that downstream systems need. Note that two of the five steps below are not measurements at all. They are settings you have to write down before you can compute anything: the tolerance eps, and the matrix or table you sampled.

Different mappings fail in different ways. The clearest evidence comes from systems that published their numbers.

The hashing case is the most instructive, because the compression itself turned out to be free. A spam experiment published in 2009 covered 3.2 million emails from 433,167 users, 40 million unique tokens after tokenization, and a personalized feature space of about 16 trillion possible features. The team hashed all of it into 2^22 dimensions. At that table size the global classifier's error converged and “hash collisions have no impact on the classification error”; the hashed model matched the unhashed baseline. What the hashing bought was the per-user personalization that 16 trillion features had made infeasible: “Figure 2 shows that despite aggressive hashing, personalization results in a 30% spam reduction once the hash table is indexed by 22 bits.” A 2018 paper gives the tight account of when collisions stop being harmless.

Both create linear lower-dimensional coordinates. They use different evidence and they promise different things.

PCA minimises average squared reconstruction error over the data it was fitted on. A Johnson-Lindenstrauss transform bounds worst-case pairwise distortion instead. And it is sampled from the source dimension, the number of vectors and the tolerance alone — never from the data. Freksen draws the practical consequence: “This allows us to sample a JLT without having access to the input data, e.g. to compute the JLT before the data exists, or to compute the JLT in settings where the data is too large to store on or move to a single machine”. That is why johnson_lindenstrauss_min_dim takes only n_samples and eps as arguments. There is no data matrix to hand it.

The dimension it demands is not slack in the proof that a cleverer sampled matrix could win back. Dasgupta and Gupta flagged the limit in their own introduction — “In recent work, Noga Alon has shown that this result is essentially tight” — and Larsen and Nelson closed the remaining gap in 2017. For any integers d, n >= 2 and any eps with 1/(min{n,d})^0.4999 < eps < 1, they exhibit a set of n vectors in R^d for which any embedding preserving all pairwise distances to within (1 +/- eps) must use m = Omega(eps^-2 lg n) dimensions. The eps^-2 log n price is a floor, not a first attempt.

PCA offers loadings, feature agglomeration offers groups, and random projection offers a simple reproducible mapping with geometric guarantees. The most interpretable method for an engineer may not be the most interpretable for a domain expert.

Choose reduction according to the evidence the system must preserve and explain. Record approximation error rather than treating lower dimension as an improvement by itself. The bound scikit-learn ships is not a rule of thumb. johnson_lindenstrauss_min_dim implements Theorem 2.1 of Dasgupta and Gupta, which fixes k >= 4(eps^2/2 - eps^3/3)^-1 ln n, and the library cites them by name. The User Guide states the contract: “Knowing only the number of samples, the johnson_lindenstrauss_min_dim estimates conservatively the minimal size of the random subspace to guarantee a bounded distortion introduced by the random projection”.

Then read what the formula returns. For one million points it gives 663 target dimensions at 50 percent tolerance, 11,841 at 10 percent and 1,112,658 at 1 percent. The library's own Gaussian example is smaller and no kinder: a 100-row, 10,000-column matrix at the default eps=0.1 projects to 3,947 components. The bound moves with the number of points and the tolerance, never with the original dimension. And because it is conservative, it is the ceiling to argue down from with measurements, not a number to quietly ignore.