[yorwba]

Johnson-Lindenstrauss is an example of a probabilistic existence argument: the probability of a random projection having low error is nonzero, therefore a low-error projection must exist. That doesn't mean any given random projection can be expected to have low error, although if you keep rerolling often enough, you'll eventually find one.

The existence argument does only provide a lower bound on the number of dimensions that can be represented with low error, but there's not necessarily much room for improvement left.