Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms
Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms
We develop and analyze a broad family of stochastic/randomized algorithms for calculating an approximate inverse matrix. We also develop specialized variants maintaining symmetry or positive definiteness of the iterates. All methods in the family converge globally and linearly (i.e., the error decays exponentially), with explicit rates. In special cases, we …