# L1 norm minimization over a matrix for a linear system

Let $$\mathbf{A} \in \mathbb{R}^{m \times n}$$, where $$m< 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 $$$$\hat{\mathbf{x}} = \underset{\mathbf{x}}{ \text{argmin} } \; \; \left\Vert \mathbf{Ax} - \mathbf{b} \right\Vert _{1}, \label{equ_1}$$$$ where $$\hat{\mathbf{x}} \in \mathbb{R}^{n}$$ can be written as $$$$\hat{\mathbf{x}}=\left[\begin{array}{c} \mathbf{v}_{1}\\ \vdots\\ \mathbf{v}_{q} \end{array}\right]$$$$ 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., $$$$\mathbf{V}=\left[\begin{array}{ccc} | & & |\\ \mathbf{v}_{1} & \ldots & \mathbf{v}_{q}\\ | & & | \end{array}\right],$$$$ 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.

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.

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

• Many thanks for this Brian. I'm interested in solutions to (1) under the constraint that the rows of $\mathbf{X}$ are sparse. In other words, the locations of the first $n$ zeros in the vector $z$ (Line 7) will repeat every $q$ times. Thus, if $n=3$ and $q=4$, then $z$ may be $[1.2, 0, 0, -3.2, 0, 0, -0.3, 0, 0, 5.8, 0, 0]$. Any help is greatly appreciated! – primazonda Apr 4 at 8:16
• This additional aspect of the problem isn't at all clear to me from your comment- I'd suggest that you edit the question to explain this in more detail. There are certainly ways to regularize for sparsity of rows of $X$, but that's different from forcing the nonzeros to appear in the same columns in each row. – Brian Borchers Apr 4 at 14:37
• Sure Brian. I've edited the question, hopefully it is more clear now. Thank you! – primazonda Apr 4 at 17:27
• Group Lasso is a technique that would promote the kind of sparsity you desire, but it's not an absolute constraint. It's quite straight forward to add that to the LP formulation of the 1-norm minimization problem. – Brian Borchers Apr 4 at 19:49