I would like to solve a linear system $Ax = b$ under the $L_1$ norm constraint $\min(|Ax-b|)$.
All that I can find about $L_1$ minimization is a way to minimize $|x|_1$ subject to $Ax=b$.
I wanted to use linear programming in matlab to solve this problem. This lead me to solving a new system with linprog in matlab:
$$My = k$$
So I did some transformations, knowing that Linprog can solve the following problem:
$$\min f(x) \ \ \textrm{s.t.} \ \ Ax \leq b$$
I want to minimize this problem:
$$\min ||My – k||_1$$
for $y$
To convert this to the linprog form, I introduced a new vector I want to minimize, $z$:
$$\min \sum z$$
s.t.
$$My – k \leq z$$
$$-My + k \leq z$$
However, the constraints include both the variable $y$ and the constants $k$. We can formulate this in the required form by creating a bigger system:
$Ax \leq b$, where the matrix $A$ is:
$$\begin{pmatrix}
M & -I \\
-M & I
\end{pmatrix}
$$
the vector $x$ is equal to $y$ and $z$ stacked:
$$\begin{pmatrix}
y \\
z
\end{pmatrix}
$$
and the constraints are $k$ and $-k$ stacked:
$$\begin{pmatrix}
k \\
-k
\end{pmatrix}
$$
The problem is that this doesn't work. (Matlab can't find a good solution). I would like to know if there is another way to solve this problem? If you have heard about a matlab code that already does it?
Thanks a lot
Best Answer
If you have min $\|Ax-b\|_1$ where $A$ is $n\times m$ for $n>m$ and $b$ is $n\times 1$ (so the sum of the absolute values of all the components of the result vector $y=Ax-b$ where y is $n\times 1$) then you can solve this as an LP with linprog with a command like this:
which is just a translation into Matlab of the usual trick described on Wikipedia.
Here is a polynomial fitting example that compares least absolute deviations to linear least squares.
This is what the output looks like