提出新方法实现近线性行数的最小二乘坐标精度保证。
Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee
- 结合哈达玛展开、随机置换与高斯分池，构造新型快速稠密变换。
- 在ε⁻²d log d行下达成ℓ∞解精度保证，优于此前结果。
- 适用于需要高精度解向量的科学计算与机器学习场景。
随机压缩-求解算法通过将原始问题替换为更小规模的问题来加速超定ℓ₂回归。标准子空间嵌入仅保证目标函数值近似保留，但解向量的逐坐标精度更难保障：要求解向量本身在ℓ∞范数下接近最优解，即满足‖x′−x⋆‖∞≤ε/√d·‖Ax⋆−b‖₂·‖A†‖ₒₚ。Price、Song和Woodruff首次研究此问题，并证明以O(ε⁻²d¹⁺Θ(√(log log n/log d)))行的子采样随机哈达玛变换（SRHT）可实现该保证。后续工作声称可将行数改进至O(ε⁻²d log³n)，但其证明依赖于不成立的独立性假设，本文给出反例。为此，我们引入一种新的快速稠密随机变换：结合随机哈达玛展开、随机置换与平衡不相交高斯分池。在哈达玛与置换阶段后，压缩后问题等价于噪声与压缩设计独立的精确高斯回归——这正是此前论证缺失的关键条件。该方法以m=O(ε⁻²d log d)行实现ℓ∞保证，仅需一次哈达玛变换，内部维度为N=Õ(n+ε⁻²d³)，且高效可算：(SA, Sb)可在O(Nd log N)=Õ(nd+ε⁻²d⁴)时间内完成。
原文摘要 · Abstract (English)
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ε{\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(ε^{-2} d^{1+Θ(\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(ε^{-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$ guarantee with $m=O(ε^{-2}d\log d)$ rows, uses one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+ε^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+ε^{-2}d^4)$ time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。