{"ID":2880854,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14234","arxiv_id":"2508.14234","title":"Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors","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 $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].","short_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 $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 su...","url_abs":"https://arxiv.org/abs/2508.14234","url_pdf":"https://arxiv.org/pdf/2508.14234v2","authors":"[\"Shabarish Chenakkod\",\"Michał Dereziński\",\"Xiaoyu Dong\"]","published":"2025-08-19T19:45:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"math.NA\",\"math.PR\",\"stat.ML\"]","methods":"[]","has_code":false}