Structured Semidefinite Programming for Recovering Structured Preconditioners

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: • Diagonal preconditioning. We give an algorithm which, given positive definite K ∈ ℝ^d×d with nnz(K) nonzero entries, computes an ∊-optimal diagonal preconditioner in time (Equation presented), where k^* is the optimal condition number of the rescaled matrix. • Structured linear systems. We give an algorithm which, given M ∈ ℝ^d×d that is either the pseudoinverse of a graph Laplacian matrix or a constant spectral approximation of one, solves linear systems in M in Õ(d²) time. Our diagonal preconditioning results improve state-of-the-art runtimes of Õ(d^3:5) attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of Õ(d^ω) where ω > 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.