Least Absolute Deviations

Description

Least Absolute Deviations (LAD) is an alternative to traditional Least Sqaures by using cost function

\textrm{min}_x ~ \|Ax-b\|_1

to use \ell_1 norm instead of square loss for robust estimation of coefficient.

Usage

admm.lad(
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


## generate data
m = 1000
n = 100
A = matrix(rnorm(m*n),nrow=m)
x = 10*matrix(rnorm(n))
b = A%*%x

## add impulsive noise to 10% of positions
idx = sample(1:m, round(m/10))
b[idx] = b[idx] + 100*rnorm(length(idx))

## run the code
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")