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 \(\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.Structured linear systems. We give an algorithm which, given \(\mathbf{M} \in \mathbb{R}^{d \times d}\) that is either the pseudo-inverse 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.