Краткое содержание

arXiv:2508.14234v2 Тип объявления: replace-cross Аннотация: Мы приводим доказательство гипотезы Нельсона и Нгуена [FOCS 2013] об оптимальной размерности и разреженности oblivious вложений подпространств с точностью до суб-полилогарифмических множителей: для любых \(n\geq d\) и \(\epsilon\geq d^{-O(1)}\) существует случайная матрица \(\Pi\) размером \(\tilde O(d/\epsilon^2)\times n\) с \(\tilde O(\log(d)/\epsilon)\) ненулевыми элементами в столбце такая, что для любой \(A\in\mathbb{R}^{n\times d}\) с высокой вероятностью \((1-\epsilon)\|Ax\|\leq\|\Pi Ax\|\leq(1+\epsilon)\|Ax\|\) для всех \(x\in\mathbb{R}^d\), где \(\tilde O(\cdot)\) скрывает только суб-полилогарифмические множители от \(d\). Наш результат, в частности, подразумевает новое наиболее быстрое суб-текущее приведение времени матричного умножения размера \(\tilde O(d/\epsilon^2)\) для широкого класса задач линейной регрессии размерности \(n\times d\). Ключевым новшеством в нашем анализе является техника матричной концентрации, которую мы называем итеративным развязыванием, и которую мы используем для тонкой настройки границ моментов следов высшего порядка, достижимых с помощью существующих