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.

翻译：我们认为亚模块函数最小化(SFM) 和亚模块函数Lov'asz扩展的二次最小化问题。 这些优化问题密切相关; 例如, 最小化问题和完全变异解调问题, 其切割函数为子模块, 其Lov' asz扩展由相关总变异给出。 当二次损失通过剪切函数的完全变异而正规化, 从而成为完全变异解的问题, 我们用本文中的相同术语来形容“ 常规” 子模块功能。 我们提出一种新的主动设置算法, 用于完全变异, 与一个解决相应 SFM 问题的甲骨架的安装问题密切相关。 这可以被看作是由明确的趋同保证来给定分区的本地白种算法。 当二次调整时, 我们还会考虑一个子模块函数可以解析成两个子模块的组合。 我们建议对一个总和 F1 和 F2 的算法进行完全变换换, 并且将SFMLA 的演算法进行新的变法。