标题： 接近求解具有低秩结构的密集线性系统的最优性 显示英文标题

标题： Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

摘要： 我们为求解线性系统和回归问题提供了新的高精度随机算法，这些系统和问题除了$k$个大的奇异值外都是良态的。 对于求解这样的$d \times d$正定系统，我们的算法以高概率成功。 运行时间为$\tilde O(d^2 + k^\omega)$。 对于在矩阵$\mathbf{A} \in \mathbb{R}^{n \times d}$中求解此类回归问题，我们的方法以高概率成功。 并且在时间$\tilde O(\mathrm{nnz}(\mathbf{A}) + d^2 + k^\omega)$运行，其中$\omega$是矩阵乘法指数，$\mathrm{nnz}(\mathbf{A})$是$\mathbf{A}$中非零项的数量。我们的方法在密集输入下几乎达到这些问题的自然复杂度限制，并改进了先前方法中的一种权衡，这些方法对于$d\times d$系统的运行时间要么是$\tilde O(d^{2.065}+k^\omega)$，要么是$\tilde O(d^2 + dk^{\omega-1})$。 此外，我们展示了如何在所有但$k$个奇异值具有适当有界广义均值的较弱假设下获得这些运行时间。 因此，我们给出了第一个几乎线性时间算法，用于计算任意稠密矩阵的核范数的乘法近似值。 我们的算法基于三个一般的递归预处理框架，其中矩阵抽样和低秩更新公式被精心调整以适应问题的结构。 显示英文摘要

摘要： We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for $k$ large singular values. For solving such $d \times d$ positive definite system our algorithms succeed whp. and run in time $\tilde O(d^2 + k^\omega)$. For solving such regression problems in a matrix $\mathbf{A} \in \mathbb{R}^{n \times d}$ our methods succeed whp. and run in time $\tilde O(\mathrm{nnz}(\mathbf{A}) + d^2 + k^\omega)$ where $\omega$ is the matrix multiplication exponent and $\mathrm{nnz}(\mathbf{A})$ is the number of non-zeros in $\mathbf{A}$. Our methods nearly-match a natural complexity limit under dense inputs for these problems and improve upon a trade-off in prior approaches that obtain running times of either $\tilde O(d^{2.065}+k^\omega)$ or $\tilde O(d^2 + dk^{\omega-1})$ for $d\times d$ systems. Moreover, we show how to obtain these running times even under the weaker assumption that all but $k$ of the singular values have a suitably bounded generalized mean. Consequently, we give the first nearly-linear time algorithm for computing a multiplicative approximation to the nuclear norm of an arbitrary dense matrix. Our algorithms are built on three general recursive preconditioning frameworks, where matrix sketching and low-rank update formulas are carefully tailored to the problems' structure.