Entrywise Approximation for Matrix Inversion and Linear Systems
Abstract
We study matrix inversion and solving linear systems on diagonally dominant matrices. These are associated with random walk quantities such as hitting times and escape probabilities in graphs. Such quantities can be exponentially small, even on undirected unit-weighted graphs. However, their nonnegativity suggests that they can be approximated entrywise, leading to a stronger notion of approximation than vector norm–based error.
Fields of Study & Subjects
Matrix Theory and Algorithms
Random Matrices and Applications
Stochastic Gradient Optimization Techniques
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5199–5210
- Publication date
- 1 January 2026
- Language
- EN