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 approachFile | 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.