Active-set Methods for Submodular Minimization Problems

K. S. Sesh Kumar 1, 2 Francis Bach 1, 2
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider submodular optimization problems such as submodular function minimization (SFM) and quadratic problems regularized by the Lovász extension; for cut functions, this corresponds respectively to graph cuts and total variation (TV) denoising. Given a submodular function with an SFM oracle, we propose a new active-set algorithm for total variation denoising, which is more flexible than existing ones; the algorithm may be seen as a local descent algorithm over ordered partitions with explicit convergence guarantees. For functions that decompose into the sum of two functions F1 and F2 with efficient SFM oracles, we propose a new active-set algorithm for total variation denoising (and hence for SFM by thresholding the solution at zero). This algorithm also optimizes over ordered partitions and improves over existing ones based on TV or SFM oracles for F1 and F2.
Type de document :
Pré-publication, Document de travail
2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01161759
Contributeur : Ks Seshkumar <>
Soumis le : vendredi 18 novembre 2016 - 12:05:37
Dernière modification le : jeudi 11 janvier 2018 - 06:23:26
Document(s) archivé(s) le : mercredi 15 mars 2017 - 04:25:51

Fichiers

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

Identifiants

  • HAL Id : hal-01161759, version 3
  • ARXIV : 1506.02852

Collections

Citation

K. S. Sesh Kumar, Francis Bach. Active-set Methods for Submodular Minimization Problems. 2016. 〈hal-01161759v3〉

Partager

Métriques

Consultations de la notice

309

Téléchargements de fichiers

322