Selective l1 minimization for sparse recovery

van Luong Le (1) , Fabien Lauer (2) , Gérard Bloch (1)

1 CRAN - Centre de Recherche en Automatique de Nancy
2 ABC - Machine Learning and Computational Biology

Motivated by recent approaches to switched linear system identification based on sparse optimization, the paper deals with the recovery of sparse solutions of underdetermined systems of linear equations. More precisely, we focus on the associated convex relaxation where the $\ell_{1}$-norm of the vector of variables is minimized and propose a new iteratively reweighted scheme in order to improve the conditions under which this relaxation provides the sparsest solution. We prove the convergence of the new scheme and derive sufficient conditions for the convergence towards the sparsest solution. Experiments show that the new scheme significantly improves upon the previous approaches for compressive sensing. Then, these results are applied to switched system identification.

Mots clés: Sparsity; Convex relaxation; Hybrid Systems; Switched systems; system identification; compressed sensing; basis pursuit

Domaines: Automatique; Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]; Automatique / Robotique; Optimisation et contrôle [math.OC]

van Luong Le, Fabien Lauer, Gérard Bloch. Selective l1 minimization for sparse recovery. IEEE Transactions on Automatic Control, 2014, 59 (11), pp.3008-3013. ⟨10.1109/TAC.2014.2351694⟩. ⟨hal-00904836⟩