0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$
  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$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – primazonda Apr 4 at 8:16
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Apr 4 at 14:37
  • $\begingroup$ Sure Brian. I've edited the question, hopefully it is more clear now. Thank you! $\endgroup$ – primazonda Apr 4 at 17:27
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Apr 4 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.