Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization

被引:146
作者
Elad, Michael [1 ]
Matalon, Boaz
Zibulevsky, Michael
机构
[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel
[2] Technion Israel Inst Technol, Dept Elect Engn, IL-32000 Haifa, Israel
关键词
least squares; regularization; inverse problems; denoising; shrinkage; basis pursuit; sparsity; coordinate-descent; proximal-point; SCALE MIXTURES; IMAGE; ALGORITHM; TRANSFORM;
D O I
10.1016/j.acha.2007.02.002
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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 [M. Elad, Why simple shrinkage is still relevant for redundant representations? IEEE Trans. Inform. Theory 52 (12) (2006) 5559-5569], 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 [I. Daubechies, M. Defrise, C. De-Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. LVII (2004) 1413-1457; M.A. Figueiredo, R.D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process. 12 (8) (2003) 906-916; M.A. Figueiredo, R.D. Nowak, A bound optimization approach to wavelet-based image deconvolution, in: IEEE International Conference on Image Processing, 2005], which considered the deblurring problem in a Bayesian methodology, also obtained element-wise optimization algorithms. We show that the last three methods are essentially equivalent, and the unified method is termed separable surrogate functionals (SSF). We also provide a convergence analysis for SSE 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 demonstrated. (c) 2007 Elsevier Inc. All rights reserved.
引用
收藏
页码:346 / 367
页数:22
相关论文
共 36 条
[1]  
ANDREWS DF, 1974, J ROY STAT SOC B MET, V36, P99
[2]  
[Anonymous], 2001, Noise Reduction by Wavelet Thresholding, volume 161 of Lecture Notes in Statistics
[3]   Penalty/barrier multiplier methods for convex programming problems [J].
BenTal, A ;
Zibulevsky, M .
SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (02) :347-366
[4]   Bayesian wavelet-based image deconvolution: A GEM algorithm exploiting a class of heavy-tailed priors [J].
Bioucas-Dias, JM .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2006, 15 (04) :937-951
[5]   Spatially adaptive wavelet thresholding with context modeling for image denoising [J].
Chang, SG ;
Yu, B ;
Vetterli, M .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2000, 9 (09) :1522-1531
[6]  
Chen S. S., 2001, SIAM REV, V43, P59
[7]   Signal recovery by proximal forward-backward splitting [J].
Combettes, PL ;
Wajs, VR .
MULTISCALE MODELING & SIMULATION, 2005, 4 (04) :1168-1200
[8]   An iterative thresholding algorithm for linear inverse problems with a sparsity constraint [J].
Daubechies, I ;
Defrise, M ;
De Mol, C .
COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2004, 57 (11) :1413-1457
[9]   MAXIMUM LIKELIHOOD FROM INCOMPLETE DATA VIA EM ALGORITHM [J].
DEMPSTER, AP ;
LAIRD, NM ;
RUBIN, DB .
JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-METHODOLOGICAL, 1977, 39 (01) :1-38
[10]   The contourlet transform: An efficient directional multiresolution image representation [J].
Do, MN ;
Vetterli, M .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2005, 14 (12) :2091-2106