L1 Minimization with Non-negativity constraints. Is there any fast approach to solving l1 minimization problem with non-negativity contraints? The problem is to minimize $|x_1|+|x_2|+...+|x_n|_{l_1}$ subject to $Ax = b$ and $Ax \geq 0$.
 A: You can convert problems like this into linear programs by introducing variables $t_i, i = 1,\ldots,n$ that satisfy
\begin{equation}
-t_i \leq x_i \leq t_i
\end{equation}
for $i = 1,\ldots, n$.
(Note that this is equivalent to requiring $t_i \geq | x_i| \, \forall \, i$.)
Just minimize $t_1 + \cdots + t_n$ subject to these constraints, and to whatever other constraints you have on $x$.  Efficient methods are available to solve linear programs.
This trick (which is standard) is described in chapter 6 ("Approximation and fitting") of Vandenberghe's 236b notes.  See slide 6-3.
A: Indeed, this can be solved as a quadratic program by any QP solver (I do this routinely).
The problem is (if I understood correctly):
$min||Ax-b||^2_2+c||x||_1$ such that $x>=0$
In your case $c=1$ but in general this is a regularization parameter (for more information read about LASSO or L1-regularized least squares).
Start with the fact that $min||Ax-b||^2_2$ such that $x>=0$ is clearly a QP since:
$||Ax-b||^2_2=x^TA^TAx-2(b^TA)^Tx+b^Tb$
Now the additional constraint won't change much, and the problem is still a QP:
$||Ax-b||^2_2+c||x||_1=x^TA^TAx-2(b^TA)^Tx+b^Tb+c\underline{1}^Tx$
I hope I got all those nasty transpose right :)
