A new fast, dense randomized transform combining Hadamard flattening, random permutation, and balanced Gaussian pooling achieves L∞ guarantees with O(ε^-2 d log d) rows

To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform, which combines a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression in which the noise is independent of the entire sketched design; this conditional independence is exactly what the earlier argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(ε^{-2}d\log d)$ rows

http://arxiv.org/abs/2608.26552v1