Fast Quantized Johnson - Lindenstrauss Transforms
The paper introduces two fast methods, D-FQJL and P-FQJL, for asymmetric quantized Johnson–Lindenstrauss transforms. These constructions replace dense Gaussian projections with fast structured transforms based on Randomized Hadamard Transforms. They achieve O(d log d) time complexity while maintaining the accuracy guarantees of standard Fast JL, making them applicable to compressing Key-Value caches in large language models.