Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms

Robert M. Gower, Peter Richtárik

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

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 obtain stochastic block variants of several quasi-Newton updates, including bad Broyden (BB), good Broyden (GB), Powell-symmetric-Broyden (PSB), Davidon-Fletcher-Powell (DFP), and Broyden-Fletcher-Goldfarb-Shanno (BFGS). Ours are the first stochastic versions of these updates shown to converge to an inverse of a fixed matrix. Through a dual viewpoint we uncover a fundamental link between quasi-Newton updates and approximate inverse preconditioning. Further, we develop an adaptive variant of randomized block BFGS, where we modify the distribution underlying the stochasticity of the method throughout the iterative process to achieve faster convergence. By inverting several matrices from varied applications, we demonstrate that adaptive randomized BFGS (AdaRBFGS) is highly competitive when compared to the Newton-Schulz method, a minimal residual method and direct inversion method based on a Cholesky decomposition. In particular, on large-scale problems our method outperforms the standard methods by orders of magnitude at calculating an approximate inverse. Development of efficient methods for estimating the inverse of very large matrices is a much needed tool for preconditioning and variable metric optimization methods in the advent of the big data era.

Original languageEnglish (US)
Pages (from-to)1380-1409
Number of pages30
JournalSIAM Journal on Matrix Analysis and Applications
Volume38
Issue number4
DOIs
StatePublished - 2017

Keywords

  • BFGS
  • Iterative methods
  • Matrix inversion
  • Quasi-Newton
  • Stochastic convergence
  • Stochastic methods

ASJC Scopus subject areas

  • Analysis

Fingerprint

Dive into the research topics of 'Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms'. Together they form a unique fingerprint.

Cite this