L1 norm minimization over a matrix for a linear system

Question

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.

Answer 1

1. 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.

2. 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$.