# admm.lasso: Least Absolute Shrinkage and Selection Operator In ADMM: Algorithms using Alternating Direction Method of Multipliers

## Description

LASSO, or L1-regularized regression, is an optimization problem to solve

\textrm{min}_x ~ \frac{1}{2}\|Ax-b\|_2^2 + λ \|x\|_1

for sparsifying the coefficient vector x. The implementation is borrowed from Stephen Boyd's MATLAB code.

## Usage

  1 2 3 4 5 6 7 8 9 10 admm.lasso( A, b, lambda = 1, rho = 1, alpha = 1, abstol = 1e-04, reltol = 0.01, maxiter = 1000 ) 

## Arguments

 A an (m\times n) regressor matrix b a length-m response vector lambda a regularization parameter rho an augmented Lagrangian parameter alpha an overrelaxation parameter in [1,2] abstol absolute tolerance stopping criterion reltol relative tolerance stopping criterion maxiter maximum number of iterations

## Value

a named list containing

x

a length-n solution vector

history

dataframe recording iteration numerics. See the section for more details.

## Iteration History

When you run the algorithm, output returns not only the solution, but also the iteration history recording following fields over iterates,

objval

object (cost) function value

r_norm

norm of primal residual

s_norm

norm of dual residual

eps_pri

feasibility tolerance for primal feasibility condition

eps_dual

feasibility tolerance for dual feasibility condition

In accordance with the paper, iteration stops when both r_norm and s_norm values become smaller than eps_pri and eps_dual, respectively.

## References

\insertRef

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ## generate sample data m = 50 n = 100 p = 0.1 # percentange of non-zero elements x0 = matrix(Matrix::rsparsematrix(n,1,p)) A = matrix(rnorm(m*n),nrow=m) for (i in 1:ncol(A)){ A[,i] = A[,i]/sqrt(sum(A[,i]*A[,i])) } b = A%*%x0 + sqrt(0.001)*matrix(rnorm(m)) ## set regularization lambda value lambda = 0.1*base::norm(t(A)%*%b, "F") ## run example output = admm.lasso(A, b, lambda) niter = length(output$history$s_norm) history = output$history ## report convergence plot opar <- par(no.readonly=TRUE) par(mfrow=c(1,3)) plot(1:niter, history$objval, "b", main="cost function") plot(1:niter, history$r_norm, "b", main="primal residual") plot(1:niter, history$s_norm, "b", main="dual residual") par(opar)