Sequential convex programming for computing information-theoretic minimal partitions: Nonconvex nonsmooth optimization

Kee Y, Lee Y, Souiai M, Cremers D, Kim J (2017)

Publication Type: Journal article

Publication year: 2017

Journal

Siam Journal on Imaging Sciences Society for Industrial and Applied Mathematics

Book Volume: 10

Pages Range: 1845-1877

Journal Issue: 4

DOI: 10.1137/16M1078653

Abstract

We consider an unsupervised image segmentation problem—from figure-ground separation to multiregion partitioning—that consists of maximal distribution separation (in terms of mutual information) with spatial regularity (total variation regularization), which is what we call information- theoretic minimal partitioning. Adopting the bounded variation framework, we provide an in-depth analysis of the problem which establishes theoretical foundations and investigates the structure of the associated energy from a variational perspective. In doing so, we show that the objective exhibits a form of difference of convex functionals, which leads us to a class of large-scale nonconvex optimization problems where convex optimization techniques can be successfully applied. In this regard, we propose sequential convex programming based on the philosophy of stochastic optimization and the Chambolle–Pock primal-dual algorithm. The key idea behind it is to construct a stochastic family of convex approximations of the original nonconvex function and sequentially minimize the associated subproblems. Indeed, its stochastic nature makes it possible to often escape from bad local minima toward near-optimal solutions, where such optimality can be justified in terms of the recent findings in statistical physics regarding a striking characteristic of the high-dimensional landscapes. We experimentally demonstrate such a favorable ability of the proposed algorithm as well as show the capacity of our approach in numerous experiments. The preliminary conference paper can be found in [Y. Kee, M. Souiai, D. Cremers, and J. Kim, Proceedings of the IEEE Conference on Computer Vision and Pattern, Recognition, 2014].

Involved external institutions

Korea Advanced Institute of Science and Technology (KAIST) KR Korea, Republic of (KR) Technische Universität München (TUM) DE Germany (DE)

How to cite

APA:

Kee, Y., Lee, Y., Souiai, M., Cremers, D., & Kim, J. (2017). Sequential convex programming for computing information-theoretic minimal partitions: Nonconvex nonsmooth optimization. Siam Journal on Imaging Sciences, 10(4), 1845-1877. https://dx.doi.org/10.1137/16M1078653

MLA:

Kee, Youngwook, et al. "Sequential convex programming for computing information-theoretic minimal partitions: Nonconvex nonsmooth optimization." Siam Journal on Imaging Sciences 10.4 (2017): 1845-1877.

BibTeX: Download