×

Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms. (English) Zbl 1379.65016

Summary: 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.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Benzi and M. T\ruma, {\it Comparative study of sparse approximate inverse preconditioners}, Appl. Numer. Math., 30 (1999), pp. 305-340. · Zbl 0949.65043
[2] R. Bhatia, {\it Positive Definite Matrices}, Princeton Ser. Appl. Math., Princeton University Press, Princeton, NJ, 2008, p. 264. · Zbl 1125.15300
[3] M. D. Bingham, {\it A new method for obtaining the inverse matrix}, J. Amer. Statist. Assoc., 36 (1941), pp. 530-534. · Zbl 0061.27205
[4] C. G. Broyden, {\it A class of methods for solving nonlinear simultaneous equations}, Math. Comp., 19 (1965), pp. 577-593. · Zbl 0131.13905
[5] C. C. Chang and C. J. Lin, {\it LIBSVM: A library for support vector machines}, ACM Trans. Intel. Syst. Tech., 2 (2011), pp. 1-27.
[6] E. Chow and Y. Saad, {\it Approximate inverse preconditioners via sparse-sparse iterations}, SIAM J. Sci. Comput., 19 (1998), pp. 995-1023, . · Zbl 0922.65034
[7] J. J. D. Croz and N. J. Higham, {\it Stability of methods for matrix inversion}, IMA J. Numer. Anal., 12 (1992), pp. 1-19. · Zbl 0748.65021
[8] W. C. Davidon, {\it Variable Metric Method for Minimization}, Tech. rep., A.E.C. Research and Development Report, ANL-5990, Argonne National Laboratory, Lemont, IL, 1959. · Zbl 0752.90062
[9] T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123
[10] B. R. Fletcher and M. J. D. Powell, {\it A rapidly convergent descent method for minimization}, Comput. J., 6 (1963), pp. 163-168. · Zbl 0132.11603
[11] D. Goldfarb, {\it Modification methods for inverting matrices and solving systems of linear algebraic equations}, Math. Comp., 26 (1972), pp. 829-829. · Zbl 0268.65026
[12] D. Goldfarb, {\it A family of variable-metric methods derived by variational means}, Math. Comp., 24 (1970), pp. 23-26. · Zbl 0196.18002
[13] N. I. M. Gould and J. A. Scott, {\it Sparse approximate-inverse preconditioners using norm-minimization techniques}, SIAM J. Sci. Comput., 19 (1998), pp. 605-625, . · Zbl 0911.65037
[14] R. M. Gower, {\it Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices}, Ph.D. thesis, University of Edinburgh, Edinburgh, UK, 2016.
[15] R. M. Gower and J. Gondzio, {\it Action Constrained Quasi-Newton Methods}, preprint, , 2014.
[16] R. M. Gower and P. Richtárik, {\it Stochastic Dual Ascent for Solving Linear Systems}, preprint, , 2015. · Zbl 1342.65110
[17] R. M. Gower and P. Richtárik, {\it Randomized iterative methods for linear systems}, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1660-1690, . · Zbl 1342.65110
[18] R. M. Gower and P. Richtárik, {\it Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms}, preprint, , 2016. · Zbl 1379.65016
[19] S. Gratton, A. Sartenaer, and J. Tshimanga, {\it On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides}, SIAM J. Optim., 21 (2011), pp. 912-935, . · Zbl 1273.65044
[20] B. J. Greenstadt, {\it Variations on variable-metric methods}, Math. Comp., 24 (1969), pp. 1-22. · Zbl 0204.49601
[21] A. Griewank, {\it Broyden updating, the good and the bad!}, Doc. Math., Extra Vol.: Optimization Stories (2012), pp. 301-315. · Zbl 1264.65078
[22] P. Hennig, {\it Probabilistic interpretation of linear solvers}, SIAM J. Optim., 25 (2015), pp. 234-260, . · Zbl 1356.49042
[23] T. Huckle and A. Kallischko, {\it Frobenius norm minimization and probing for preconditioning}, Internat. J. Comput. Math., 84 (2007), pp. 1225-1248. · Zbl 1126.65035
[24] L. Y. Kolotilina and A. Y. Yeremin, {\it Factorized sparse approximate inverse preconditionings \textupI. Theory}, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 45-58, . · Zbl 0767.65037
[25] D. Leventhal and A. S. Lewis, {\it Randomized methods for linear constraints: Convergence rates and conditioning}, Math. Oper. Res., 35 (2010), pp. 641-654. · Zbl 1216.15006
[26] D. Leventhal and A. Lewis, {\it Randomized Hessian estimation and directional search}, Optimization, 60 (2011), pp. 329-345. · Zbl 1219.90191
[27] W. Li and Z. Li, {\it A family of iterative methods for computing the approximate inverse of a square matrix and inner inverse of a non-square matrix}, Appl. Math. Comput., 215 (2010), pp. 3433-3442. · Zbl 1185.65057
[28] Y. Lu, P. Dhillon, D. P. Foster, and L. Ungar, {\it Faster ridge regression via the subsampled randomized Hadamard transform}, in Proceedings of NIPS 2013, Advances in Neural Information Processing Systems 26, 2013, pp. 369-377.
[29] J. Nocedal, {\it Updating quasi-Newton matrices with limited storage}, Math. Comp., 35 (1980), pp. 773-782. · Zbl 0464.65037
[30] M. Pilanci and M. Wainwright, {\it Randomized sketches of convex programs with sharp guarantees}, IEEE Trans. Inform. Theory, 61 (2015), pp. 5096-5115. · Zbl 1359.90097
[31] M. Pilanci and M. J. Wainwright, {\it Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares}, J. Mach. Learn. Res., 17 (2016), pp. 1-33. · Zbl 1360.62400
[32] M. Pilanci and M. J. Wainwright, {\it Newton Sketch: A Linear-Time Optimization Algorithm with Linear-Quadratic Convergence}, preprint, , 2015. · Zbl 1456.90125
[33] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003, . · Zbl 1031.65046
[34] G. Schulz, {\it Iterative berechung der reziproken matrix}, ZAMM Z. Angew. Math. Mech., 13 (1933), pp. 57-59. · JFM 59.0535.04
[35] D. F. Shanno, {\it Conditioning of quasi-Newton methods for function minimization}, Math. Comp., 24 (1971), pp. 647-656. · Zbl 0225.65073
[36] S. U. Stich, C. L. Müller, and B. Gärtner, {\it Variable metric random pursuit}, Math. Program., 156 (2015), pp. 549-579. · Zbl 1342.90137
[37] T. Strohmer and R. Vershynin, {\it A randomized Kaczmarz algorithm with exponential convergence}, J. Fourier Anal. Appl., 15 (2009), pp. 262-278. · Zbl 1169.68052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.