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

원문 초록

Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a much smaller, randomly projected problem. While standard subspace embeddings nearly preserve the regression cost, coordinate-wise accuracy is more delicate: rather than the objective value, we want the solution vector itself to be close to the optimum in $\ell_\infty$ norm. Specifically, we seek $x'\in\mathbb{R}^d$ with $\|x'-x^\star\|_\infty\leq\frac{\epsilon}{\sqrt d}\|Ax^\star-b\|_2\|A^\dagger\|_{\mathrm{op}}$, where $A\in\mathbb{R}^{n\times d}$ is the design matrix, $b\in\mathbb{R}^n$ the label vector, $x^\star$ the optimal solution and $A^\dagger$ the pseudo-inverse of $A$. Price, Song and Woodruff introduced this problem and claimed that the subsampled randomized Hadamard transform (SRHT) with $O(\epsilon^{-2}d^{1+\Theta(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee; we point out a gap in the proof. Song, Ye, Yin and Zhang later claimed $O(\epsilon^{-2}d\log^3 n)$ rows, but 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 combining 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 whose noise is independent of the entire sketched design, exactly what Song, Ye, Yin and Zhang's argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(\epsilon^{-2}d\log d)$ rows, using one Hadamard pass with padded internal dimension $N=\widetilde{O}(n+\epsilon^{-2}d^3)$. It is also efficient to apply: $(SA,Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+\epsilon^{-2}d^4)$ time.