Faster Dynamic Matrix Inverse for Faster LPs

Abstract

Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an $n\times n$ real matrix under $\text{low-rank}$ updates, with polynomially faster amortized running time. Our data structure is based on a recursive application of the Woodbury-Morrison identity for implementing $\text{cascading}$ 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^{\ast }(n^{2+\max \{\frac{1}{6},\omega -2,\frac{1-\alpha }{2}\}})$ to $O^{\ast }(n^{2+\max \{\frac{1}{18},\omega -2,\frac{1-\alpha }{2}\}})$, where $\omega$ and $\alpha$ are the fast matrix multiplication exponent and its dual. Hence, under the common belief that $\omega \approx 2$ and $\alpha \approx 1$, our LP solver runs in $O^{\ast }(n^{2.055})$ time instead of $O^{\ast }(n^{2.16})$.

References in corpus (5)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Powers of Tensors and Fast Matrix Multiplication
• Conditional Hardness of Earth Mover Distance
• Path Finding I :Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves
• Fast Regression with an ${\ell }_{\infty }$ Guarantee

Cited by in corpus (16)

• Optimal Measurement of Field Properties with Quantum Sensor Networks
• Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments
• InstaHide: Instance-hiding Schemes for Private Distributed Learning
• Minimum Cost Flows, MDPs, and ${\ell }_1$-Regression in Nearly Linear Time for Dense Instances
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
• Generalized Leverage Score Sampling for Neural Networks
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• Abstract Interpretation of Fixpoint Iterators with Applications to Neural Networks
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• COPS: Controlled Pruning Before Training Starts
• Minimizing Convex Functions with Rational Minimizers
• A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
• Smoothed Least-Laxity-First Algorithm for EV Charging
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Solving SDP Faster: A Robust IPM Framework and Efficient Implementation