Structured Semidefinite Programming for Recovering Structured Preconditioners

Arun Jambulapati, Christopher Musco, Jerry Li, Kirankumar Shiragur, Aaron Sidford, Kevin Tian

    Research output: Contribution to journalConference articlepeer-review


    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 Õ(d2) time. Our diagonal preconditioning results improve state-of-the-art runtimes of Õ(d3: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.

    Original languageEnglish (US)
    JournalAdvances in Neural Information Processing Systems
    StatePublished - 2023
    Event37th Conference on Neural Information Processing Systems, NeurIPS 2023 - New Orleans, United States
    Duration: Dec 10 2023Dec 16 2023

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Information Systems
    • Signal Processing


    Dive into the research topics of 'Structured Semidefinite Programming for Recovering Structured Preconditioners'. Together they form a unique fingerprint.

    Cite this