  We propose an adaptive refinement algorithm to solve total variation
regularized measure optimization problems. The method iteratively constructs
dyadic partitions of the unit cube based on i) the resolution of discretized
dual problems and ii) on the detection of cells containing points that violate
the dual constraints. The detection is based on upper-bounds on the dual
certificate, in the spirit of branch-and-bound methods. The interest of this
approach is that it avoids the use of heuristic approaches to find the
maximizers of dual certificates. We prove the convergence of this approach
under mild hypotheses and a linear convergence rate under additional
non-degeneracy assumptions. These results are confirmed by simple numerical
experiments.
