L1 norm minimization over a matrix for a linear system Let $\mathbf{A} \in \mathbb{R}^{m \times n}$, where $m<<n$ and $\mathbf{b} \in \mathbb{R}^{m}$. The rank of $\mathbf{A}$ is $m$ and both $\mathbf{A}$ and $\mathbf{b}$ are known. Consider the optimization problem where 
\begin{equation}
\hat{\mathbf{x}} = \underset{\mathbf{x}}{ \text{argmin} } \; \; \left\Vert \mathbf{Ax} - \mathbf{b} \right\Vert _{1},
\label{equ_1}
\end{equation}
where $\hat{\mathbf{x}} \in \mathbb{R}^{n}$ can be written as 
\begin{equation}
\hat{\mathbf{x}}=\left[\begin{array}{c}
\mathbf{v}_{1}\\
\vdots\\
\mathbf{v}_{q}
\end{array}\right]
\end{equation}
where $\mathbf{v}_{i} \in \mathbb{R}^{p}$ for $i=1, \ldots, q$, and thus $pq=n$. We wish to obtain solutions to the optimization problem such that rows of $\mathbf{v}_{i}$ have zeros at the same indices. However, we do not known a priori which indices to set to zero. Another way to think about this is that if we define a matrix $\mathbf{V} \in \mathbb{R}^{p \times q}$, where we assemble rows of $\mathbf{v}_{i}$, i.e.,
\begin{equation}
\mathbf{V}=\left[\begin{array}{ccc}
| &  & |\\
\mathbf{v}_{1} & \ldots & \mathbf{v}_{q}\\
| &  & |
\end{array}\right],
\end{equation}
then if entry $\mathbf{V}(i,j)$ is zero, all entries in the $i$-th row will be zero. Conversely, if $\mathbf{V}(i,j)$ is non-zero, all the entries in the $i$-th row will be non-zero.
 A: *

*By $\| W \|_{{l}_{1}}$, do you mean (incorrect, but a common misuse of notation)


$\| W \|_{{l}_{1}}= \sum_{i=1}^{m} \sum_{j=1}^{q} | W_{i,j} |$?
This can be reformulated as 
$\min \| Gz - d \|_{1}$
where
$G=\left[
\begin{array}{c}
A \\
A \\
\vdots \\
A
\end{array}
\right]$
$z=\mbox{vec}(X)$
$d=\mbox{vec}(B)$
and then you can use a wide variety of algorithms for solving the one-norm minimization problem- IRLS is perhaps the quickest to implement.


*Do you mean the operator 1-norm


$\| W \|_{{l}_{1}}= \max_{\| x \|_{1}=1} \| Wx \|_{1}
=\max_{j} \sum_{i=1}^{m} | W_{i,j} |
$?  
In that case, you can formulate the norm minimization as the LP
$\min_{s,t,U,V,X} s $
subject to 
$s \geq t_{j}$ for $i=1, 2, \ldots, q$.
$t_{j} \geq \sum_{i=1}^{m} U_{i,j}$ for $j=1, 2, \ldots, q$.
$U_{i,j} \geq V_{i,j}$  for $i=1, 2, \ldots, m$, $j=1, 2, \ldots, q$.
$U_{i,j} \geq -V_{i,j}$   for $i=1, 2, \ldots, m$, $j=1, 2, \ldots, q$.
$AX-B=V$.   
Here, $V$ is the matrix whose 1-norm we're minimizing.  $U$ is constrained so that all of its elements are bigger than the elements of $| V |$.  $t_{j}$ is constrained to be larger than the 1-norm of column $j$ of $V$.  s is constrained to be larger than the maximum of the $t_{j}$.  Since $s$ is being minimized it will actually be equal to the 1-norm of $V$.  
