The Alternating Direction Multipliers Method (ADMM) is a very popular and powerful algorithm for the solution of many optimization problems. In the recent years it has been widely used for the solution of ill-posed inverse problems. However, one of its drawback is the possibly high computational cost, since at each iteration, it requires the solution of a large-scale least squares problem. In this work we propose a computationally attractive implementation of ADMM, with particular attention to ill-posed inverse problems. We significantly decrease the computational cost by projecting the original large scale problem into a low-dimensional subspace by means of Generalized Krylov Subspaces (GKS). The dimension of the projection space is not an additional parameter of the method as it increases with the iterations. The construction of GKS allows for very fast computations, regardless of the increasing size of the problem. Several computed examples show the good performances of the proposed method.

Fast Alternating Direction Multipliers Method by Generalized Krylov Subspaces

Buccini A.
2022

Abstract

The Alternating Direction Multipliers Method (ADMM) is a very popular and powerful algorithm for the solution of many optimization problems. In the recent years it has been widely used for the solution of ill-posed inverse problems. However, one of its drawback is the possibly high computational cost, since at each iteration, it requires the solution of a large-scale least squares problem. In this work we propose a computationally attractive implementation of ADMM, with particular attention to ill-posed inverse problems. We significantly decrease the computational cost by projecting the original large scale problem into a low-dimensional subspace by means of Generalized Krylov Subspaces (GKS). The dimension of the projection space is not an additional parameter of the method as it increases with the iterations. The construction of GKS allows for very fast computations, regardless of the increasing size of the problem. Several computed examples show the good performances of the proposed method.
ADMM; generalized Krylov subspaces; Ill-posed inverse problems
File in questo prodotto:
File Dimensione Formato  
ADMM_GKS.pdf

accesso aperto

Tipologia: versione pre-print
Dimensione 2.71 MB
Formato Adobe PDF
2.71 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11584/325791
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact