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 × d positive definite system our algorithms succeed whp. and run in time tilde O(d2 + kω). For solving such regression problems in a matrix A ∈ ℝn × d our methods succeed whp. and run in time tilde O(nnz(A) + d2 + kω) where ω is the matrix multiplication exponent and nnz(A) is the number of non-zeros in 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(d2.065+kω) or tilde O(d2 + dkω-1) for d× 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.