  We develop and analyze a broad family of stochastic/randomized algorithms for
inverting a 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 AdaRBFGS is highly competitive when compared to the well
established Newton-Schulz and minimal residual methods. In particular, on
large-scale problems our method outperforms the standard methods by orders of
magnitude. 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.
