Network Flow Algorithms for Structured Sparsity

Julien Mairal 1, 2 Rodolphe Jenatton 1, 2 Guillaume Obozinski 1, 2 Francis Bach 1, 2
1 WILLOW - Models of visual object recognition and scene understanding
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Résumé : Nous considérons une classe de problèmes d'apprentissage régularisés par une norme induisant de la parcimonie structurée, définie comme une somme de normes $\ell_\infty$ sur des groupes de variables. Alors que de nombreux efforts ont étés mis pour développer des algorithmes d'optimisation rapides lorsque les groupes sont disjoints ou structurés hiérarchiquement, nous nous intéressons au cas général de groupes avec recouvrement. Nous montrons que le problème d'optimisation correspondant est lié à l'optimisation de flots sur un réseau. Plus précisément, l'opérateur proximal associé à la norme que nous considérons est dual à la minimisation d'un coût quadratique de flot sur un graphe particulier. Nous proposons une procédure efficace qui calcule cette solution en un temps polynomial. Notre algorithme peut traiter de larges problèmes, comportant des millions de variables, et ouvre de nouveaux champs d'applications pour les modèles parcimonieux structurés. Nous présentons diverses expériences sur des données d'images et de vidéos, qui démontrent l'utilité et l'efficacité de notre approche pour résoudre de nombreux problèmes.
Type de document :
Rapport
[Research Report] RR-7372, INRIA. 2010, pp.23
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00512556
Contributeur : Julien Mairal <>
Soumis le : lundi 30 août 2010 - 18:34:48
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : jeudi 1 décembre 2016 - 11:33:39

Fichiers

RR-7372.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00512556, version 1
  • ARXIV : 1008.5209

Citation

Julien Mairal, Rodolphe Jenatton, Guillaume Obozinski, Francis Bach. Network Flow Algorithms for Structured Sparsity. [Research Report] RR-7372, INRIA. 2010, pp.23. 〈inria-00512556〉

Partager

Métriques

Consultations de la notice

1257

Téléchargements de fichiers

320