Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms

DOI10.1137/16M1062053zbMath1379.65016arXiv1602.01768OpenAlexW2295492468MaRDI QIDQ4598334

Peter Richtárik, Robert M. Gower

Publication date: 20 December 2017

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.01768

zbMATH Keywords

preconditioningiterative methodsminimal residual methodstochastic methodsmatrix inversionquasi-NewtonCholesky decompositionstochastic convergenceNewton-Schulz methoddirect inversion methodBroyden-Fletcher-Goldfarb-Shanno

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Direct numerical methods for linear systems and matrix inversion (65F05) Preconditioners for iterative methods (65F08)

Related Items (16)

Beyond the EM algorithm: constrained optimization methods for latent class model ⋮ Rates of superlinear convergence for classical quasi-Newton methods ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Unifying relations between iterative linear equation solvers and explicit Euler approximations for associated parabolic regularized equations ⋮ slimTrain---A Stochastic Approximation Method for Training Separable Deep Neural Networks ⋮ Towards explicit superlinear convergence rate for SR1 ⋮ An overview of stochastic quasi-Newton methods for large-scale machine learning ⋮ Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ Batched Stochastic Gradient Descent with Weighted Sampling ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ Stochastic quasi-gradient methods: variance reduction via Jacobian sketching ⋮ On Adaptive Sketch-and-Project for Solving Linear Systems ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Greedy Quasi-Newton Methods with Explicit Superlinear Convergence

Uses Software

• L-BFGS
• SparseMatrix
• LIBSVM

Cites Work

• Unnamed Item
• Variable metric random pursuit
• A family of iterative methods for computing the approximate inverse of a square matrix and inner inverse of a non-square matrix
• A randomized Kaczmarz algorithm with exponential convergence
• A comparative study of sparse approximate inverse preconditioners
• Broyden updating, the good and the bad!
• Positive definite matrices
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Probabilistic Interpretation of Linear Solvers
• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• Randomized Sketches of Convex Programs With Sharp Guarantees
• The university of Florida sparse matrix collection
• Randomized Hessian estimation and directional search
• On A Class of Limited Memory Preconditioners For Large Scale Linear Systems With Multiple Right-Hand Sides
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• Modification Methods for Inverting Matrices and Solving Systems of Linear Algebraic Equations
• Randomized Iterative Methods for Linear Systems
• Updating Quasi-Newton Matrices with Limited Storage
• Stability of Methods for Matrix Inversion
• Variable Metric Method for Minimization
• Factorized Sparse Approximate Inverse Preconditionings I. Theory
• Sparse Approximate-Inverse Preconditioners Using Norm-Minimization Techniques
• Approximate Inverse Preconditioners via Sparse-Sparse Iterations
• Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms
• Frobenius norm minimization and probing for preconditioning
• A Class of Methods for Solving Nonlinear Simultaneous Equations
• A Rapidly Convergent Descent Method for Minimization
• A Family of Variable-Metric Methods Derived by Variational Means
• Variations on Variable-Metric Methods
• Conditioning of Quasi-Newton Methods for Function Minimization
• A New Method for Obtaining the Inverse Matrix

This page was built for publication: Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms