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

DOI10.1088/1361-6420/AD08EDOpenAlexW4388210167MaRDI QIDQ6141569FDOQ6141569

Authors: Dirk A. Lorenz, Felix Schneppe, Lionel Tondji 

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

Recommendations

• A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems
• A two-dimensional randomized extended Gauss-Seidel algorithm for solving least squares problems
• A new randomized Gauss-Seidel method for solving linear least-squares problems
• On the convergence of a randomized block coordinate descent algorithm for a matrix least squares problem
• scientific article; zbMATH DE number 6402625

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Monte Carlo method for solving unsteady adjoint equations
• A Transpose-Free Quasi-Minimal Residual Algorithm for Non-Hermitian Linear Systems
• A randomized Kaczmarz algorithm with exponential convergence
• CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear systems
• High-dimensional probability. An introduction with applications in data science
• Optimization of convex functions with random pursuit
• Preasymptotic convergence of randomized Kaczmarz method
• Random gradient-free minimization of convex functions
• Randomized Kaczmarz Converges Along Small Singular Vectors
• Randomized iterative methods for linear systems
• Randomized methods for linear constraints: convergence rates and conditioning
• Sequential Monto Carlo techniques for the solution of linear systems
• The University of Florida sparse matrix collection
• The randomized Kaczmarz method with mismatched adjoint
• Transpose-free Lanczos-type algorithms for nonsymmetric linear systems
• Transpose-free formulations of Lanczos-type methods for nonsymmetric linear systems

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)