# L1-norm approximation

The $$\ell_1$$-norm approximation problem is given by

(1)$\begin{array}{ll} \mbox{minimize} & \| Pu - q \|_1 \end{array}$

with variable $$u \in \mathbf{R}^n$$ and problem data $$P \in \mathbf{R}^{m \times n}$$ and $$q \in \mathbf{R}^m$$. The problem is equivalent to an LP

(2)$\begin{split}\begin{array}{ll} \mbox{minimize} & \mathbf{1}^Tv \\ \mbox{subject to} & \begin{bmatrix} P & -I\\ -P & - I \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} \preceq \begin{bmatrix} q \\ -q \end{bmatrix} \end{array}\end{split}$

with $$m + n$$ variables and $$2m$$ constraints. Yet another equivalent formulation is the problem

(3)$\begin{split}\begin{array}{ll} \mbox{minimize} & e^Ts + e^Tt \\ \mbox{subject to} & Pu - q = s - t \\ & s, t \geq 0 \end{array}\end{split}$

with variables $$u \in \mathbf{R}^n$$, $$s \in \mathbf{R}^m$$, and $$t \in \mathbf{R}^m$$.

### Documentation

A custom solver for the $$\ell_1$$-norm approximation problem is available as a Python module l1.py (or l1_mosek6.py or l1_mosek7.py for earlier versions of CVXOPT that use either MOSEK 6 or 7). The module implements the following four functions:

l1(P, q)

Solves the problem (2) using a custom KKT solver.

Returns the solution $$u$$.

l1blas(P, q)

Solves the problem (2) using a custom KKT solver. This function implements the same custom KKT solver as l1(), but it uses BLAS routines instead of overloaded arithmetic.

Returns the solution $$u$$.

l1mosek(P, q)

Solves the problem (2) using MOSEK. This function is only available if MOSEK is installed.

Returns the solution $$u$$.

l1mosek2(P, q)

Solves the problem (3) using MOSEK. This function is only available if MOSEK is installed.

Returns the solution $$u$$.

### Example

from l1 import l1
from cvxopt import normal

m, n = 500, 100
P, q = normal(m,n), normal(m,1)
u = l1(P,q)