ADMM_lasso

This code applies ADMM for the lasso problem, (1/2)*||Ax-b||_l2^2+\lambda*||x||_l1. based on Sherman-Morrison-Woodbury matrix inversion.

This code applies ADMM for the lasso problem,

-------------------------------------------------

(1/2)*||Ax-b||_l2^2+\lambda*||x||_l1

-------------------------------------------------

as follows:

x_{k+1}=(A'*A+rho*I)^-1*(A'*b+\rho(z_{k}-u_{k});

z_{k+1}=S_{\lambda/\rho}*(x_{k+1}+u_{k});

u_{k+1}=u_{k}+x_{k+1}-z_{k+1}.

The code is based on Section 6.4 of Boyd, S., Parikh, N., & Chu, E. (2011). "Distributed optimization and statistical learning via the alternating direction method of multipliers". Now Publishers Inc.

where the term psi_inv=(A'*A+rho*I)^-1 is calculated not directly, but by the Sherman-Morrison-Woodbury

(SMW) matrix inversion formula, to avoid the memory-intensive multiplication A'*A:

(A'*A+rho*I)^-1=(I*A'*A*I+rho*I)^-1

=1/rho*(I - A'*(A*A'+rho*I)^-1 * A)

=1\rho*I - 1/rho^2*(1/rho*A*A'+I)^-1 * A.

The above formula is adopted from an equation in Page 6 of Afonso, M. V., Bioucas-Dias, J. M., & Figueiredo, M. A. (2010). "Fast image recovery using variable splitting and constrained optimization. IEEE transactions on image processing, 19(9), 2345-2356. suggested by Boyd et al. in the aforementioned reference.