Problems regularized by the total variation on a general weighted graph produce piecewise constant solutions with a small number of constant connected components. We propose a working-set strategy which exploits this structure by recursively splitting the connected components of a candidate solution using graph cuts. This method exhibits a significant speed-up over state-of-the-art algorithms when regularizing ill-posed, ill-conditioned, large-scale inverse problems, notably involving functions with a separable non-smooth part.

This presentation is part of Minisymposium “MS4 - Graph Techniques for Image Processing (2 parts)”
organized by: Yifei Lou (University of Texas at Dallas) , Jing Qin (Montana State University) .

Authors:

Loic Landrieu (Institut géographique national)

Keywords: