Optimization Online


Second-order Cone Programming Methods for Total Variation-based Image Restoration

Donald Goldfarb (goldfarb***at***columbia.edu)
Wotao Yin (wy2002***at***columbia.edu)

Abstract: In this paper we present optimization algorithms for image restoration based on the total variation (TV) minimization framework of L. Rudin, S. Osher and E. Fatemi (ROF). Our approach formulates TV minimization as a second-order cone program which is then solved by interior-point algorithms that are efficient both in practice (using nested dissection and domain decomposition) and in theory (i.e., they obtain solutions in polynomial time). In addition to the original ROF minimization model, we show how to apply our approach to other TV models including ones that are not solvable by PDE based methods. Numerical results on a varied set of images are presented to illustrate the effectiveness of our approach.

Keywords: image denoising, total variation, secon-order cone programming, interior-point methods, nested dissection, domain decomposition

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

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: CORC Report TR-2004-05, Department of Industrial Engineering and Operations Research, Columbia University

Download: [PDF]

Entry Submitted: 08/08/2004
Entry Accepted: 08/08/2004
Entry Last Modified: 08/08/2004

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