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

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 systems our algorithms succeed whp. and run in time $\tilde{O}(d^{2} + k^{\omega})$. For solving such regression problems in a matrix $\textbf A \in \mathbb{R}^{n \times d}$ our methods succeed whp. and run in time $\tilde{O}(\mathrm{nnz}(\textbf A) + d^{2} + k^{\omega})$ where $\omega$ is the matrix multiplication exponent and $\mathrm{nnz}(\textbf A)$ is the number of non-zeros in $\textbf 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} + d\,k^{\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.