Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee

Randomized sketch-and-solve algorithms accelerate overconstrained ℓ2 regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the cost of the regression is nearly preserved, but coordinate-wise accuracy of the solution is more delicate: we want the solution vector itself to be close to the optimal solution in ℓ_∞ norm. In particular, we want to find a vector x'∈ ℝd such that |x'-x^*|_∞≤ fracε√ d· |Ax^star-b|2· |A^dagger|rm op. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with O(ε-2 d^1+Theta(√loglog n/log d)) rows achieves this guarantee. A subsequent work of Song, Ye, Yin and Zhang claimed to improve the row count to O(ε-2dlog3 n). Unfortunately, their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. 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 ℓ_∞ guarantee with m=O(ε-2dlog d) rows, uses one Hadamard pass with a padded internal dimension N=widetildeO(n+ε-2d3), and is efficient to apply: the sketched pair (SA, Sb) can be computed in O(Ndlog N)=widetildeO(nd+ε-2d4) time.