# Efficient Inverse Maintenance and Faster Algorithms for Linear Programming

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2015.

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

- [Classification with abstention but without disparities](https://mlsanity.com/paper/2102.12258/) (2021)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization](https://mlsanity.com/paper/2312.03218/) (2023)
- [Score Design for Multi-Criteria Incentivization](https://mlsanity.com/paper/2410.06290/) (2024)

## Abstract (arXiv)

In this paper, we consider the following inverse maintenance problem: given A ∈ ℝn× d and a number of rounds r, we receive a n× n diagonal matrix D(k) at round k and we wish to maintain an efficient linear system solver for ATD(k)A under the assumption D(k) does not change too rapidly. This inverse maintenance problem is the computational bottleneck in solving multiple optimization problems. We show how to solve this problem with tildeO(nnz(A)+dω) preprocessing time and amortized tildeO(nnz(A)+d2) time per round, improving upon previous running times for solving this problem. Consequently, we obtain the fastest known running times for solving multiple problems including, linear programming and computing a rounding of a polytope. In particular given a feasible point in a linear program with d variables, n constraints, and constraint matrix A∈ℝn× d, we show how to solve the linear program in time tildeO(nnz(A)+d2)√dlog(ε-1)). We achieve our results through a novel combination of classic numerical techniques of low rank update, preconditioning, and fast matrix multiplication as well as recent work on subspace embeddings and spectral sparsification that we hope will be of independent interest.