Optimization Online


On iteratively reweighted Algorithms for Non-smooth Non-convex Optimization in Computer Vision

Peter Ochs(ochs***at***cs.uni-freiburg.de)
Alexey Dosovitskiy(dosovits***at***cs.uni-freiburg.de)
Thomas Brox(brox***at***cs.uni-freiburg.de)
Thomas Pock(pock***at***icg.tugraz.at)

Abstract: Natural image statistics indicate that we should use non-convex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge of optimization. Recently, iteratively reweighed $\ell_1$ minimization (IRL1) has been proposed as a way to tackle a class of non-convex functions by solving a sequence of convex $\ell_2$-$\ell_1$ problems. We extend the problem class to the sum of a convex function and a (non-convex) non-decreasing function applied to another convex function. The proposed algorithm sequentially optimizes suitably constructed convex majorizers. Convergence to a critical point is proved when the Kurdyka-Lojasiewicz property and additional mild restrictions hold for the objective function. The efficiency of the algorithm and the practical importance of the algorithm is demonstrated in computer vision tasks such as image denoising and optical flow. Most applications seek smooth results with sharp discontinuities. This is achieved by combining non-convexity with higher order regularization.

Keywords: Iteratively reweighted algorithm, majorization-minimization, IRL1, IRLS, non-smooth non-convex optimization, Kurdyka-Lojasiewicz inequality, non-convex total generalized variation

Category 1: Nonlinear Optimization

Citation: Accepted to SIAM Journal on Imaging Sciences, 2014.

Download: [PDF]

Entry Submitted: 01/10/2015
Entry Accepted: 01/10/2015
Entry Last Modified: 01/10/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society