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

Sicherheitsmeldung mit Schweregrad noch nicht bewertet. Technische Details im Tab „Originaltext“; empfohlene Schritte in der Checkliste.

Originaltext der Quelle (nicht übersetzt) – die deutsche Zusammenfassung findest du im Tab „Kurzfassung".

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 \mathbb{R}^d$ such that $\|x'-x^*\|_\infty\leq \frac{\epsilon}{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|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(\epsilon^{-2} d^{1+\Theta(\sqrt{\log\log 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}d\log^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$ …

Vollständiger Originalartikel ↗

• Betroffenheit im eigenen Stack prüfen: Versionen/Komponenten abgleichen.
• Originalquelle / Hersteller-Advisory lesen: https://arxiv.org/abs/2608.26552
• Verfügbaren Patch oder Workaround einspielen und dokumentieren.