Structured Semidefinite Programming for Recovering Structured
  Preconditioners
Arun Jambulapati Jerry Li Christopher Musco Kirankumar Shiragur Aaron Sidford Kevin Tian
We develop a general framework for finding approximately-optimal
preconditioners for solving linear systems. Leveraging this framework we obtain
improved runtimes for fundamental preconditioning and linear system solving
problems including the following. We give an algorithm which, given positive
definite $\mathbf{K} \in \mathbb{R}^{d \times d}$ with
$\mathrm{nnz}(\mathbf{K})$ nonzero entries, computes an $\epsilon$-optimal
diagonal preconditioner in time $\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot
\mathrm{poly}(\kappa^\star,\epsilon^{-1}))$, where $\kappa^\star$ is the
optimal condition number of the rescaled matrix. We give an algorithm which,
given $\mathbf{M} \in \mathbb{R}^{d \times d}$ that is either the pseudoinverse
of a graph Laplacian matrix or a constant spectral approximation of one, solves
linear systems in $\mathbf{M}$ in $\widetilde{O}(d^2)$ time. Our diagonal
preconditioning results improve state-of-the-art runtimes of $\Omega(d^{3.5})$
attained by general-purpose semidefinite programming, and our solvers improve
state-of-the-art runtimes of $\Omega(d^{\omega})$ where $\omega > 2.3$ is the
current matrix multiplication constant. We attain our results via new
algorithms for a class of semidefinite programs (SDPs) we call
matrix-dictionary approximation SDPs, which we leverage to solve an associated
problem we call matrix-dictionary recovery.