← 研踪 PaperTrailarXiv:2608.26552 · v2
Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee
首次提交 2026-08-27 10:43
版本更新 2026-11-08 00:32
雷达观测 2026-11-10 11:14
摘要
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ε{\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(ε^{-2}d^{1+Θ(\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(ε^{-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(ε^{-2}d\log d)$ rows, using one Hadamard pass with padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$. It is also efficient to apply: $(SA,Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.
作者备注：Improve presentation and add more discussions on prior work. Abstract shortened to meet arxiv requirement
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-08 00:32 · 最新观测版本
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ε{\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(ε^{-2}d^{1+Θ(\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(ε^{-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(ε^{-2}d\log d)$ rows, using one Hadamard pass with padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$. It is also efficient to apply: $(SA,Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.
查看此版本解读 →查看此版本原文 ↗