解决最优随机投影嵌入维度与稀疏性猜想，逼近理论极限。
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
- 提出迭代解耦分析技术，改进高阶矩估计
- 实现每列仅需约 $\tilde O(\log d/ε)$ 个非零元的嵌入矩阵
- 适用于大规模线性回归加速，性能逼近理论最优
我们证明了Nelson和Nguyen在2013年提出的关于无意识子空间嵌入最优维数与稀疏性的猜想，精度达到次多项对数因子范围内：对任意 $n \geq d$ 且 $ε \geq d^{-O(1)}$，存在一个随机的 $\tilde O(d/ε^2) \times n$ 矩阵 $Π$，其每列仅有 $\tilde O(\log d/ε)$ 个非零元素，使得对任意 $A \in \mathbb{R}^{n \times d}$，以高概率满足：对所有 $x \in \mathbb{R}^d$，有 $(1-ε)\|Ax\| \leq \|ΠAx\| \leq (1+ε)\|Ax\|$。其中 $\tilde O(\cdot)$ 仅隐藏次多项对数因子。本结果首次实现了此类嵌入在规模 $\tilde O(d/ε^2)$ 下的快速矩阵乘法归约，适用于广泛的 $n \times d$ 线性回归任务。分析核心为新提出的矩阵浓度技术‘迭代解耦’，可精细调控现有随机矩阵普遍性工具（Brailovskaya & van Handel, GAFA 2024）所能达到的高阶迹矩界。
原文摘要 · Abstract (English)
We give a proof of the conjecture of Nelson and Nguyen [FOCS 2013] on the optimal dimension and sparsity of oblivious subspace embeddings, up to sub-polylogarithmic factors: For any $n\geq d$ and $ε\geq d^{-O(1)}$, there is a random $\tilde O(d/ε^2)\times n$ matrix $Π$ with $\tilde O(\log(d)/ε)$ non-zeros per column such that for any $A\in\mathbb{R}^{n\times d}$, with high probability, $(1-ε)\|Ax\|\leq\|ΠAx\|\leq(1+ε)\|Ax\|$ for all $x\in\mathbb{R}^d$, where $\tilde O(\cdot)$ hides only sub-polylogarithmic factors in $d$. Our result in particular implies a new fastest sub-current matrix multiplication time reduction of size $\tilde O(d/ε^2)$ for a broad class of $n\times d$ linear regression tasks. A key novelty in our analysis is a matrix concentration technique we call iterative decoupling, which we use to fine-tune the higher-order trace moment bounds attainable via existing random matrix universality tools [Brailovskaya and van Handel, GAFA 2024].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。