Optimization Online


Coordinate and Subspace Optimization Methods for Linear Least Squares with Non-Quadratic Regularization

Michael Elad (elad***at***cs.technion.ac.il)
Boaz Matalon (mboaz17***at***techunix.technion.ac.il)
Michael Zibulevsky (mzib***at***ee.technion.ac.il)

Abstract: This work addresses the problem of regularized linear least squares (RLS) with non-quadratic separable regularization. Despite being frequently deployed in many applications, the RLS problem is often hard to solve using standard iterative methods. In a recent work [10], a new iterative method called Parallel Coordinate Descent (PCD) was devised. We provide herein a convergence analysis of the PCD algorithm, and also introduce a form of the regularization function, which permits analytical solution to the coordinate optimization. Several other recent works [6, 12, 13], which considered the deblurring problem in a Bayesian methodology, also obtained element-wise optimization algorithms. We show that these three methods are essentially equivalent, and the unified method is termed Separable Surrogate Functionals (SSF). We also provide a convergence analysis for SSF. To further accelerate PCD and SSF, we merge them into a recently developed sequential subspace optimization technique (SESOP), with almost no additional complexity. A thorough numerical comparison of the denoising application is presented, using the Basis Pursuit Denoising (BPDN) objective function, which leads all of the above algorithms to an iterated shrinkage format. Both with synthetic data and with real images, the advantage of the combined PCD-SESOP method is clearly demonstrated.

Keywords: Least Squares, Regularization, Inverse problems, Denoising, Shrinkage, Basis Pursuit,

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Applications -- Science and Engineering (Statistics )

Citation: Technion, April 28, 2006

Download: [PDF]

Entry Submitted: 05/04/2006
Entry Accepted: 05/04/2006
Entry Last Modified: 05/08/2006

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