The problem of nding sparse solutions to underdetermined systems of linear equa- tions arises in several applications (e.g., signal and image processing, compressive sensing, statistical inference). A standard tool for dealing with sparse recovery is the L-1 regularized least squares approach that has been recently attracting the attention of many researchers. In this paper, we describe an active set estimate (i.e., an estimate of the indices of the zero variables in the optimal solution) for the considered problem that tries to quickly identify as many active variables as possible at a given point, while guaranteeing that some approximate optimality conditions are satis ed. A rele- vant feature of the estimate is that it gives a signi cant reduction of the objective function when setting to zero all those variables estimated to be active. This enables us to easily embed it into a given globally converging algorithmic framework. In particular, we include our estimate into a block coordinate descent algorithm for ` 1 -regularized least squares, analyze the convergence properties of this new active set method, and prove that its basic version converges with a linear rate. Finally, we report some numerical results showing the e ectiveness of the approach

A fast active set block coordinate descent algorithm for ℓ1-regularized least squares / DE SANTIS, MARIANNA; LUCIDI, Stefano; Rinaldi, Francesco. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 26:(2016), pp. 781-809. [10.1137/141000737]

A fast active set block coordinate descent algorithm for ℓ1-regularized least squares

DE SANTIS, MARIANNA;LUCIDI, Stefano;
2016

Abstract

The problem of nding sparse solutions to underdetermined systems of linear equa- tions arises in several applications (e.g., signal and image processing, compressive sensing, statistical inference). A standard tool for dealing with sparse recovery is the L-1 regularized least squares approach that has been recently attracting the attention of many researchers. In this paper, we describe an active set estimate (i.e., an estimate of the indices of the zero variables in the optimal solution) for the considered problem that tries to quickly identify as many active variables as possible at a given point, while guaranteeing that some approximate optimality conditions are satis ed. A rele- vant feature of the estimate is that it gives a signi cant reduction of the objective function when setting to zero all those variables estimated to be active. This enables us to easily embed it into a given globally converging algorithmic framework. In particular, we include our estimate into a block coordinate descent algorithm for ` 1 -regularized least squares, analyze the convergence properties of this new active set method, and prove that its basic version converges with a linear rate. Finally, we report some numerical results showing the e ectiveness of the approach
2016
26
781
809
DE SANTIS, MARIANNA; LUCIDI, Stefano; Rinaldi, Francesco
File in questo prodotto:
File Dimensione Formato  
DeSantis_A-fast-active_2016.pdf

Accesso chiuso

Licenza: Tutti i diritti riservati
Dimensione 2.13 MB
Formato Adobe PDF
2.13 MB Adobe PDF   Richiedi una copia
DeSantis_preprint_A-fast-active_2016.pdf

Accesso chiuso

Licenza: Tutti i diritti riservati
Dimensione 533.22 kB
Formato Adobe PDF
533.22 kB Adobe PDF   Richiedi una copia

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

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1350085
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 19
social impact