$$ell _0$$ℓ0-penalized problems arise in a number of applications in engineering, machine learning and statistics, and, in the last decades, the design of algorithms for these problems has attracted the interest of many researchers. In this paper, we are concerned with the definition of a first-order method for the solution of $$ell _0$$ℓ0-penalized problems with simple constraints. We use a reduced dimension Frank–Wolfe algorithm Rinaldi (Optim Methods Softw, 26, 2011) and show that the subproblem related to the computation of the Frank–Wolfe direction can be solved analytically at least for some sets of simple constraints. This gives us a very easy to implement and quite general tool for dealing with $$ell _0$$ℓ0-penalized problems. The proposed method is then applied to the numerical solution of two practical optimization problems, namely, the Sparse Principal Component Analysis and the Sparse Reconstruction of Noisy Signals. In both cases, the reported numerical performances and comparisons with state-of-the-art solvers show the efficiency of the proposed method.

Solving ℓ0-penalized problems with simple constraints via the Frank–Wolfe reduced dimension method / Liuzzi, G.; Rinaldi, F.. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 9:1(2015), pp. 57-74. [10.1007/s11590-014-0757-3]

Solving ℓ0-penalized problems with simple constraints via the Frank–Wolfe reduced dimension method

Liuzzi G.
;
2015

Abstract

$$ell _0$$ℓ0-penalized problems arise in a number of applications in engineering, machine learning and statistics, and, in the last decades, the design of algorithms for these problems has attracted the interest of many researchers. In this paper, we are concerned with the definition of a first-order method for the solution of $$ell _0$$ℓ0-penalized problems with simple constraints. We use a reduced dimension Frank–Wolfe algorithm Rinaldi (Optim Methods Softw, 26, 2011) and show that the subproblem related to the computation of the Frank–Wolfe direction can be solved analytically at least for some sets of simple constraints. This gives us a very easy to implement and quite general tool for dealing with $$ell _0$$ℓ0-penalized problems. The proposed method is then applied to the numerical solution of two practical optimization problems, namely, the Sparse Principal Component Analysis and the Sparse Reconstruction of Noisy Signals. In both cases, the reported numerical performances and comparisons with state-of-the-art solvers show the efficiency of the proposed method.
2015
Frank–Wolfe method; Noisy signals; Sparse problems; SPCA
01 Pubblicazione su rivista::01a Articolo in rivista
Solving ℓ0-penalized problems with simple constraints via the Frank–Wolfe reduced dimension method / Liuzzi, G.; Rinaldi, F.. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 9:1(2015), pp. 57-74. [10.1007/s11590-014-0757-3]
File allegati a questo prodotto
File Dimensione Formato  
Liuzzi_Solving_2015.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 285.39 kB
Formato Adobe PDF
285.39 kB Adobe PDF   Contatta l'autore

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: https://hdl.handle.net/11573/1434021
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact