# Faster Dynamic Matrix Inverse for Faster LPs

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

## Built on by (most cited first, 30 of 44)

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understanding](https://mlsanity.com/paper/2306.04933/) (2023)
- [A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Models](https://mlsanity.com/paper/2306.02295/) (2023)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Differentially Private Attention Computation](https://mlsanity.com/paper/2305.04701/) (2023)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Federated Adversarial Learning: A Framework with Convergence Analysis](https://mlsanity.com/paper/2208.03635/) (2022)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [Scalable Decision-Focused Learning in Restless Multi-Armed Bandits with Application to Maternal and Child Health](https://mlsanity.com/paper/2202.00916/) (2022)
- [Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weights](https://mlsanity.com/paper/2310.12462/) (2023)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Fast and Efficient Matching Algorithm with Deadline Instances](https://mlsanity.com/paper/2305.08353/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems](https://mlsanity.com/paper/2103.04730/) (2021)
- [COPS: Controlled Pruning Before Training Starts](https://mlsanity.com/paper/2107.12673/) (2021)
- [Convergence of Two-Layer Regression with Nonlinear Units](https://mlsanity.com/paper/2308.08358/) (2023)
- [Equitable Restless Multi-Armed Bandits: A General Framework Inspired By Digital Health](https://mlsanity.com/paper/2308.09726/) (2023)

## Abstract (arXiv)

Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an n× n real matrix under textitlow-rank updates, with polynomially faster amortized running time. Our data structure is based on a recursive application of the Woodbury-Morrison identity for implementing textitcascading low-rank updates, combined with recent sketching technology. Our techniques and amortized analysis of multi-level partial updates, may be of broader interest to dynamic matrix problems. This data structure leads to the fastest known LP solver for general (dense) linear programs, improving the running time of the recent algorithms of (Cohen et al.'19, Lee et al.'19, Brand'20) from O^*(n^2+ maxfrac16, ω-2, frac1-α2) to O^*(n^2+maxfrac118, ω-2, frac1-α2), where ω and α are the fast matrix multiplication exponent and its dual. Hence, under the common belief that ω ≈ 2 and α ≈ 1, our LP solver runs in O^*(n2.055) time instead of O^*(n2.16).