Fast decomposable submodular function minimization using constrained total variation
File(s)
Accepted version
Author(s)
Karri, Senanayak Sesh Kumar
Bach, Francis
Pock, Thomas
Type
Conference Paper
Abstract
We consider the problem of minimizing the sum of submodular set functions as-suming minimization oracles of each summand function. Most existing approachesreformulate the problem as the convex minimization of the sum of the correspond-ing Lovász extensions and the squared Euclidean norm, leading to algorithmsrequiring total variation oracles of the summand functions; without further assump-tions, these more complex oracles require many calls to the simpler minimizationoracles often available in practice. In this paper, we consider a modified convexproblem requiring a constrained version of the total variation oracles that can besolved with significantly fewer calls to the simple minimization oracles. We supportour claims by showing results on graph cuts for 2D and 3D graphs.
Date Issued
2019-12-08
Date Acceptance
2019-09-04
Citation
NIPS Proceedings, 2019
Publisher
Neural Information Processing Systems Foundation, Inc.
Journal / Book Title
NIPS Proceedings
Copyright Statement
© 2019 Neural Information Processing Systems Foundation, Inc.
Source
Neural Information Processing Systems, 2019
Publication Status
Published
Start Date
2019-12-08
Finish Date
2019-12-14
Coverage Spatial
Vancouver, Canada