Optimization Online


Duality-Based Algorithms for Total-Variation-Regularized Image Restoration

Mingqiang Zhu(mingqiang.zhu***at***gmail.com)
Stephen J. Wright(swright***at***cs.wisc.edu)
Tony F. Chan(TFCHAN***at***nsf.gov)

Abstract: Image restoration models based on total variation (TV) have become popular since their introduction by Rudin, Osher, and Fatemi (ROF) in 1992. The dual formulation of this model has a quadratic objective with separable constraints, making projections onto the feasible set easy to compute. This paper proposes application of gradient projection (GP) algorithms to the dual formulation. We test variants of GP with different step length selection and line search strategies, including techniques based on the Barzilai-Borwein method. Global convergence can in some cases be proved by appealing to existing theory. We also propose a sequential quadratic programming (SQP) approach that takes account of the curvature of the boundary of the dual feasible set. Computational experiments show that the proposed approaches perform well in a wide range of applications and that some are significantly faster than previously proposed methods, particularly when only modest accuracy in the solution is required.

Keywords: Image Denoising, Constrained Optimization, Gradient Projection

Category 1: Applications -- Science and Engineering (Basic Sciences Applications )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Computational and Applied Mathematics Report 08-33, UCLA, October 2008 (Revised).

Download: [PDF]

Entry Submitted: 10/14/2008
Entry Accepted: 10/14/2008
Entry Last Modified: 10/14/2008

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 Programming Society