## Abstract

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^{2}) 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.

Original language | English (US) |
---|---|

Journal | Advances in Neural Information Processing Systems |

Volume | 36 |

State | Published - 2023 |

Event | 37th Conference on Neural Information Processing Systems, NeurIPS 2023 - New Orleans, United States Duration: Dec 10 2023 → Dec 16 2023 |

## ASJC Scopus subject areas

- Computer Networks and Communications
- Information Systems
- Signal Processing