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

arXiv:2608.26552v1 Announce Type: cross Abstract: Randomized sketch-and-solve algorithms accelerate overconstrained ell_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 ell_infty norm. In particular, we want to find a vector x'in R^d such that |x'-x^*|_inftyleq frac{epsilon}{sqrt d}dot |Ax^star-b|2dot |A^agger|{rm op}. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with O(epsilon^{-2} d^{1+Theta(sqrt{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(epsilon^{-2}dlog^3 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 ell_infty guarantee with m=O(epsilon^{-2}dlog d) rows, uses one Hadamard pass with a padded internal dimension N=widetilde{O}(n+epsilon^{-2}d^3), and is efficient to apply: the sketched pair (SA, Sb) can be computed in O(Ndlog N)=widetilde{O}(nd+epsilon^{-2}d^4) time.

Source: arXiv cs.LG | 2026-08-28

Related