# BP: Basis Pursuit In ADMM: Algorithms using Alternating Direction Method of Multipliers

## Description

For an underdetermined system, Basis Pursuit aims to find a sparse solution that solves

which is a relaxed version of strict non-zero support finding problem. The implementation is borrowed from Stephen Boyd's MATLAB code.

## Usage

 1 2 admm.bp(A, b, xinit = NA, 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 xinit a length-n vector for initial value 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.

## Examples

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ## generate sample data n = 30; m = 10; A = matrix(rnorm(n*m), nrow=m); x = matrix(rep(0,n)) x[c(3,6,21),] = rnorm(3) b = A%*%x ## run example output = admm.bp(A, b) ## report convergence plot niter = length(output$history$s_norm) par(mfrow=c(1,3)) plot(1:niter, output$history$objval, "b", main="cost function") plot(1:niter, output$history$r_norm, "b", main="primal residual") plot(1:niter, output$history$s_norm, "b", main="dual residual") 

ADMM documentation built on Sept. 29, 2018, 1:04 a.m.