When Does Learning Beat Random?

The Johnson-Lindenstrauss Lemma Against PCA and Neural Networks A theorem from 1984 claims you can throw a random matrix at high-dimensional data and preserve its geometry almost perfectly, with no