# Structured Semidefinite Programming for Recovering Structured Preconditioners

arXiv: https://arxiv.org/abs/2310.18265 · HTML: https://mlsanity.com/paper/2310.18265/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 112 references that are in the map.
- First posted on arXiv 27 Oct 2023.

## Builds on (most cited first, 12 of 12)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Algorithms for Lipschitz Learning on Graphs](https://mlsanity.com/paper/1505.00290/) (2015)
- [Fast and Near-Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2008.01722/) (2020)
- [Leverage Score Sampling for Faster Accelerated Regression and ERM](https://mlsanity.com/paper/1711.08426/) (2017)
- [Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2209.00809/) (2022)
- [Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU](https://mlsanity.com/paper/1701.01722/) (2017)
- [Learning Networks from Random Walk-Based Node Similarities](https://mlsanity.com/paper/1801.07386/) (2018)
- [Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices](https://mlsanity.com/paper/1812.06295/) (2018)
- [Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent](https://mlsanity.com/paper/2002.04830/) (2020)
- [Interpretable Personalization via Policy Learning with Linear Decision Boundaries](https://mlsanity.com/paper/2003.07545/) (2020)

## Built on by (most cited first, 5 of 5)

- [Model Immunization from a Condition Number Perspective](https://mlsanity.com/paper/2505.23760/) (2025)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Combinatorial Sparse PCA Beyond the Spiked Identity Model](https://mlsanity.com/paper/2603.02607/) (2026)

## Abstract (arXiv)

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 K ∈ ℝd × d with nnz(K) nonzero entries, computes an ε-optimal diagonal preconditioner in time widetildeO(nnz(K) · poly(kappa^star,ε-1)), where kappa^star is the optimal condition number of the rescaled matrix. 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 widetildeO(d2) time. Our diagonal preconditioning results improve state-of-the-art runtimes of Omega(d3.5) attained by general-purpose semidefinite programming, and our solvers improve state-of-the-art runtimes of Omega(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.