Skip to Main content Skip to Navigation

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 - ENS Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider a class of learning problems that involve a structured sparsity-inducing norm defined as the sum of $\ell_\infty$-norms over groups of variables. Whereas a lot of effort has been put in developing fast optimization methods when the groups are disjoint or embedded in a specific hierarchical structure, we address here the case of general overlapping groups. To this end, we show that the corresponding optimization problem is related to network flow optimization. More precisely, the proximal problem associated with the norm we consider is dual to a quadratic min-cost flow problem. We propose an efficient procedure which computes its solution exactly in polynomial time. Our algorithm scales up to millions of variables, and opens up a whole new range of applications for structured sparse models. We present several experiments on image and video data, demonstrating the applicability and scalability of our approach for various problems.
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Julien Mairal Connect in order to contact the contributor
Submitted on : Monday, August 30, 2010 - 6:34:48 PM
Last modification on : Thursday, March 17, 2022 - 10:08:39 AM
Long-term archiving on: : Thursday, December 1, 2016 - 11:33:39 AM


Files produced by the author(s)


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



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



Record views


Files downloads