He even attempts to improve on the paper by replacing the random rotation operation which is O(d^2), by a Subsampled Randomized Hadamard Transform which can be computed in O(d*log d).

Hopefully Johnson–Lindenstrauss lemma applies in the same way for SRHTransformed vectors as they do for randomly rotated vectors and the independence of the distribution laws of the coordinates remains and therefore the quantization of each coordinates independently is still theoretically sound.