An Adaptive Total Variation Algorithm for Computing the Balanced Cut of a Graph

arXiv1302.2717MaRDI QIDQ6239554FDOQ6239554

Thomas Laurent, Xavier Bresson, David Uminsky, James H. von Brecht

Publication date: 12 February 2013

Abstract: We propose an adaptive version of the total variation algorithm proposed in [3] for computing the balanced cut of a graph. The algorithm from [3] used a sequence of inner total variation minimizations to guarantee descent of the balanced cut energy as well as convergence of the algorithm. In practice the total variation minimization step is never solved exactly. Instead, an accuracy parameter is specified and the total variation minimization terminates once this level of accuracy is reached. The choice of this parameter can vastly impact both the computational time of the overall algorithm as well as the accuracy of the result. Moreover, since the total variation minimization step is not solved exactly, the algorithm is not guarantied to be monotonic. In the present work we introduce a new adaptive stopping condition for the total variation minimization that guarantees monotonicity. This results in an algorithm that is actually monotonic in practice and is also significantly faster than previous, non-adaptive algorithms.

This page was built for publication: An Adaptive Total Variation Algorithm for Computing the Balanced Cut of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239554)