We propose a novel differentiable reformulation of the linearly-constrained ℓ1 minimization problem, also known as the basis pursuit problem. The reformulation is inspired by the Laplacian paradigm of network theory and leads to a new family of gradient-based methods for the solution of ℓ1 minimization problems. We analyze the iteration complexity of a natural solution approach to the reformulation, based on a multiplicative weights update scheme, as well as the iteration complexity of an accelerated gradient scheme. The results can be seen as bounds on the complexity of iteratively reweighted least squares (IRLS) type methods of basis pursuit.

Bonifaci, V. (2021). A Laplacian approach to L1-norm minimization. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 79, 441-469 [10.1007/s10589-021-00270-x].

A Laplacian approach to L1-norm minimization

Bonifaci, Vincenzo
2021

Abstract

We propose a novel differentiable reformulation of the linearly-constrained ℓ1 minimization problem, also known as the basis pursuit problem. The reformulation is inspired by the Laplacian paradigm of network theory and leads to a new family of gradient-based methods for the solution of ℓ1 minimization problems. We analyze the iteration complexity of a natural solution approach to the reformulation, based on a multiplicative weights update scheme, as well as the iteration complexity of an accelerated gradient scheme. The results can be seen as bounds on the complexity of iteratively reweighted least squares (IRLS) type methods of basis pursuit.
Bonifaci, V. (2021). A Laplacian approach to L1-norm minimization. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 79, 441-469 [10.1007/s10589-021-00270-x].
File in questo prodotto:
File Dimensione Formato  
Bonifaci2021.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: DRM non definito
Dimensione 3.39 MB
Formato Adobe PDF
3.39 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/11590/385257
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact