Nearly Linear Time Algorithms for Solving Inverse Symmetric M-Matrices

on YouTube ↗51m

" summary

Provides algorithms that recover and solve three hard cases—perturbed Laplacians, Laplacian pseudoinverses, and inverse symmetric M-matrices—by producing a spectral approximation and then preconditioning to solve linear systems in roughly n^2 time while making only polylogarithmic matrix‑vector multiplies. Uses a matrix‑recovery SDP framework (packing/covering solvers), iterative preconditioning with a decreasing regularization parameter, and sparse edge decompositions. Works in an oracle model (only matvecs); proofs give poly(1/γ) iteration bounds. Open: faster than n^2 and nonadaptive queries.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 1:08Motivation
3. 2:42Laplacian System Solving
4. 6:00Beyond Laplacian Systems?
5. 8:33Directed Graphs and Asymmetric Systems
6. 10:38Perturbed Laplacians
7. 14:02Laplacian Pseudoinverse
8. 16:52Inverse M-Matrices
9. 19:24Hold up!
10. 20:12Our Results
11. 23:47Rest of Talk
12. 26:47How to Solve?
13. 28:55Picture
14. 30:52Idea #1 - Linear Sketch
15. 36:04Idea #2 - Optimize
16. 37:27General Problem
17. 45:04Pseudoinverse Problem
18. 46:50Inverse Symmetric M-Matrices
19. 47:39Open Problems

" related talks

• 44mScalable Algorithmic Primitives for Data ScienceRichard Peng · Randomized Numerical Linear Algebra and Applications 2018
• 35mConvergence Theory for Iterative EigensolversMark Embree · Randomized Numerical Linear Algebra and Applications 2018
• 29mImplementing Randomized Matrix Algorithms in Parallel and Distributed EnvironmentsMichael Mahoney · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 29mRecent Advances in Positive Semidefinite Matrix ApproximationCameron Musco · Randomized Numerical Linear Algebra and Applications 2018
• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 01h 31mPast, Present and Future of Randomized Numerical Linear Algebra IIMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)