# Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2018.

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

- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (2023)

## Abstract (arXiv)

In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either the matrix or its inverse. Leveraging this result we obtain faster algorithms for variety of linear algebraic problems. Key results include: bullet A nearly linear time algorithm for solving the inverse of symmetric M-matrices, a strict superset of Laplacians and SDD matrices. bullet An tildeO(n2) time algorithm for solving n × n linear systems that are constant spectral approximations of Laplacians or more generally, SDD matrices. bullet An tildeO(n2) algorithm to recover a spectral approximation of a n-vertex graph using only tildeO(1) matrix-vector multiplies with its Laplacian matrix. The previous best results for each problem either used a trivial number of queries to exactly recover the matrix or a trivial O(nω) running time, where ω is the matrix multiplication constant. We achieve these results by generalizing recent semidefinite programming based linear sized sparsifier results of Lee and Sun (2017) and providing iterative methods inspired by the semistreaming sparsification results of Kapralov, Lee, Musco, Musco and Sidford (2014) and input sparsity time linear system solving results of Li, Miller, and Peng (2013). We hope that by initiating study of these natural problems, expanding the robustness and scope of recent nearly linear time linear system solving research, and providing general matrix recovery machinery this work may serve as a stepping stone for faster algorithms.