  We consider the submodular function minimization (SFM) and the quadratic
minimization problemsregularized by the Lov'asz extension of the submodular
function. These optimization problemsare intimately related; for
example,min-cut problems and total variation denoising problems, wherethe cut
function is submodular and its Lov'asz extension is given by the associated
total variation.When a quadratic loss is regularized by the total variation of
a cut function, it thus becomes atotal variation denoising problem and we use
the same terminology in this paper for "general" submodularfunctions. We
propose a new active-set algorithm for total variation denoising with
theassumption of an oracle that solves the corresponding SFM problem. This can
be seen as localdescent algorithm over ordered partitions with explicit
convergence guarantees. It is more flexiblethan the existing algorithms with
the ability for warm-restarts using the solution of a closely relatedproblem.
Further, we also consider the case when a submodular function can be decomposed
intothe sum of two submodular functions F1 and F2 and assume SFM oracles for
these two functions.We propose a new active-set algorithm for total variation
denoising (and hence SFM by thresholdingthe solution at zero). This algorithm
also performs local descent over ordered partitions and itsability to warm
start considerably improves the performance of the algorithm. In the
experiments,we compare the performance of the proposed algorithms with
state-of-the-art algorithms, showingthat it reduces the calls to SFM oracles.
