{"id":6241,"date":"2025-08-21T07:04:41","date_gmt":"2025-08-21T07:04:41","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/08\/21\/2508-14234\/"},"modified":"2025-08-21T07:04:41","modified_gmt":"2025-08-21T07:04:41","slug":"2508-14234","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/08\/21\/2508-14234\/","title":{"rendered":"Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors"},"content":{"rendered":"

Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2508.14234v1 Announce Type: cross
\nAbstract: 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.
\n 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].<\/div>\n

\t

\n
<\/BR>
\n Shabarish Chenakkod, Micha{l} Derezi’nski, Xiaoyu Dong
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,413,113,450,451,420,112],"tags":[655,3555,3554],"class_list":["post-6241","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-ds","category-cs-lg","category-cs-na","category-math-na","category-math-pr","category-stat-ml","tag-epsilon","tag-polylogarithmic","tag-sub"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/6241"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=6241"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/6241\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=6241"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=6241"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=6241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}