Linearly convergent adjoint free solution of least squares problems by random descent

DOI10.1088/1361-6420/AD08EDarXiv2306.01946OpenAlexW4388210167MaRDI QIDQ6141569FDOQ6141569

Lionel Tondji, Felix Schneppe, Dirk A. Lorenz

Publication date: 20 December 2023

Published in: Inverse Problems (Search for Journal in Brave)

Abstract: We consider the problem of solving linear least squares problems in a framework where only evaluations of the linear map are possible. We derive randomized methods that do not need any other matrix operations than forward evaluations, especially no evaluation of the adjoint map is needed. Our method is motivated by the simple observation that one can get an unbiased estimate of the application of the adjoint. We show convergence of the method and then derive a more efficient method that uses an exact linesearch. This method, called random descent, resembles known methods in other context and has the randomized coordinate descent method as special case. We provide convergence analysis of the random descent method emphasizing the dependence on the underlying distribution of the random vectors. Furthermore we investigate the applicability of the method in the context of ill-posed inverse problems and show that the method can have beneficial properties when the unknown solution is rough. We illustrate the theoretical findings in numerical examples. One particular result is that the random descent method actually outperforms established transposed-free methods (TFQMR and CGS) in examples.

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

zbMATH Keywords

randomized algorithmsleast squares problemsstochastic gradient descent

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Convex programming (90C25) Randomized algorithms (68W20) Iterative numerical methods for linear systems (65F10)

Cites Work

• The university of Florida sparse matrix collection
• CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems
• A randomized Kaczmarz algorithm with exponential convergence
• High-Dimensional Probability
• Random gradient-free minimization of convex functions
• Optimization of convex functions with random pursuit
• Title not available (Why is that?)
• Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
• A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
• Randomized Iterative Methods for Linear Systems
• Sequential Monto Carlo techniques for the solution of linear systems
• Title not available (Why is that?)
• Transpose-free formulations of Lanczos-type methods for nonsymmetric linear systems
• A Monte Carlo method for solving unsteady adjoint equations
• Preasymptotic convergence of randomized Kaczmarz method
• Transpose-free Lanczos-type algorithms for nonsymmetric linear systems
• The randomized Kaczmarz method with mismatched adjoint
• Randomized Kaczmarz Converges Along Small Singular Vectors

This page was built for publication: Linearly convergent adjoint free solution of least squares problems by random descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141569)