Solving Sparse Linear Inverse Problems: Analysis of Reweighted l1 and l2 Methods

Abstract : A variety of practical methods have recently been introduced for finding maximally sparse representations from overcomplete dictionaries, a central computational task in compressed sensing and source localization applications as well as numerous others. Many of the underlying algorithms rely on iterative reweighting schemes that produce more focal estimates as optimization progresses. Two such variants are iterative reweighted l1 and l2 minimization; however, some properties related to convergence and sparse estimation, as well as possible generalizations, are still not clearly understood or fully exploited. In this paper, we make the distinction between separable and nonseparable iterative reweighting algorithms. The vast majority of existing methods are separable, meaning the weighting of a given coefficient at each iteration is only a function of that individual coefficient from the previous iteration (as opposed to dependency on all coefficients). We examine two such separable reweighting schemes: an l2 method from Chartand and Yin (2008) and an l1 approach from Cand`es et al. (2008), elaborating on convergence results and explicit connections between them. We then explore an interesting non-separable variant that can be implemented via either l2 or l1 reweighting and show several desirable properties relevant to sparse recovery. For the former, we show a direct connection with Chartrand and Yin's approach. For the latter, we demonstrate two desirable properties: (i) each iteration can only improve the sparsity and (ii), for any dictionary and sparsity profile, there will always exist cases where non-separable `1 reweighting improves over standard `1 minimization.
Type de document :
Communication dans un congrès
Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00369406
Contributeur : Ist Rennes <>
Soumis le : jeudi 19 mars 2009 - 16:18:39
Dernière modification le : samedi 25 novembre 2017 - 14:06:40
Document(s) archivé(s) le : mardi 8 juin 2010 - 23:39:45

Fichier

21.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00369406, version 1

Collections

Citation

David Wipf, Srikantan Nagarajan. Solving Sparse Linear Inverse Problems: Analysis of Reweighted l1 and l2 Methods. Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009. 〈inria-00369406〉

Partager

Métriques

Consultations de la notice

214

Téléchargements de fichiers

266