PCD-CG: Parallel coordinate descent merged with conjugate gradients
PCD-CG [1] is a method for large-scale unconstrained optimization. At each iteration we substitute parallel coordinate descent (PCD) direction into Polak-Ribiere conjugate gradient formula in place of preconditioned gradient. Here we provide Matlab code for Basis Pursuit (LASSO) problem
min 1/2 ||Ax-b||^2 + mu*||x||_1
We use exact line search of " quadratic + piece-wise linear" function (mex implementation by Eran Treister and Irad Yavneh [2] ) . The method demonstrates best known performance on ill-conditioned problems [1,2].
MATLAB CODE: version 01.07.2014
References:
1. M. Zibulevsky and M. Elad, L1-L2 Optimization in Signal and Image Processing, IEEE Signal Processing Magazine, Vol. 27 No. 3, Pages 78-88, May 2010.
2. Eran Treister and Irad Yavneh, A Multilevel Iterated-Shrinkage Approach to l1 Penalized Least-Squares Minimization. IEEE Trans. on Signal Processing, 60, 12, 6319-6329, 2012. (pdf)
Haifa, July 2014