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. also specialized variants maintaining symmetry or positive definiteness the iterates. All methods in converge globally linearly (i.e., error decays exponentially), with explicit rates. In special cases, we obtain stochastic block several quasi-Newton updates, including bad Broyden (BB), good (GB), Powell-symmetric-Broyden (PSB), Davidon--Fletcher--Powell (DFP), Broyden--Fletcher--Goldfarb--Shanno (BFGS). Ours are first versions these updates shown to fixed Through dual viewpoint uncover fundamental link between preconditioning. Further, adaptive variant randomized BFGS, where modify distribution underlying stochasticity method throughout iterative process achieve faster convergen...