The subsampled randomized Hadamard transform (SRHT) achieves coordinate-wise accuracy guarantees for overconstrained L2 regression with O(ε^-2 d^(1+Θ(√(log log n/log d)))) rows

Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with $O(ε^{-2} d^{1+Θ(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee.

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