Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
arXiv:2508.14234v1 Announce Type: cross
Abstract: 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 $ngeq d$ and $epsilongeq d^{-O(1)}$, there is a random $tilde O(d/epsilon^2)times n$ matrix $Pi$ with $tilde O(log(d)/epsilon)$ non-zeros per column such that for any $Ainmathbb{R}^{ntimes d}$, with high probability, $(1-epsilon)|Ax|leq|Pi Ax|leq(1+epsilon)|Ax|$ for all $xinmathbb{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/epsilon^2)$ for a broad class of $ntimes 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].
Abstract: 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 $ngeq d$ and $epsilongeq d^{-O(1)}$, there is a random $tilde O(d/epsilon^2)times n$ matrix $Pi$ with $tilde O(log(d)/epsilon)$ non-zeros per column such that for any $Ainmathbb{R}^{ntimes d}$, with high probability, $(1-epsilon)|Ax|leq|Pi Ax|leq(1+epsilon)|Ax|$ for all $xinmathbb{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/epsilon^2)$ for a broad class of $ntimes 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].
Shabarish Chenakkod, Micha{l} Derezi’nski, Xiaoyu Dong
Go to original source