PCD-CG

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