3
$\begingroup$

Using $ {l}_{1} $-norm regularization for the purpose of achieving sparsity of the solution has been successfully applied a lot. But many times, I found the paper using mixed-norm instead of $l_1$-norm.

Considering the mixed norm $ {L}_{p,q}$ norm defined as:

$$ {\left\| a \right\|}_{p,q} = \left( \sum_{i} \left( \sum_{j} {\left| {a}_{i,j} \right|}^{p} \right)^{ \frac{q}{p} } \right)^{ \frac{1}{q} } $$

How is mixed-norm better than $l1$-norm for sparse representation? Most of what I have seen is $l_{1,2}$.

Reference, for example,

$\endgroup$
1
$\begingroup$

The mixed norm allows you to impose some simple structure in the solution matrix. Using your example with $p=q=1$ then this means the solution could have arbitrary elements set to non-zero coefficients. This would not impose any structure in the solution. In this case the $L_{11} $ norm just sums the absolute value of all the matrix elements - similar to the Frobenius norm.

As an example, consider that $L_{11}$ norm of the following matrices are the same:

$\begin{bmatrix} 0&2 \\ 0 & 0\end{bmatrix}, \quad \begin{bmatrix} 0&0 \\ 2 & 0\end{bmatrix}, \quad \begin{bmatrix} 2&0 \\ 0 & 0\end{bmatrix}, \quad \begin{bmatrix} 0&0 \\ 0 & 2\end{bmatrix}$.

So there is no preference as to which element is set to non-zero

Instead, if $p=2$ and $q=1$, then the objective function is minimizing the $l_2$ norm of the columns and then the $l_1$ norm over the that. This means you're looking for an $a$ matrix with a sparse number of column vectors and where each column vector has a small $l_2$ norm. Of course this assumes you are using the $l_1$ norm as a proxy for sparsity.

Consider the $L_{2,1}$ and $L_{1,2}$ norms of following matrices:

$\begin{bmatrix} 2&0 \\ 2 & 0\end{bmatrix}, \quad L_{2,1} = \sqrt{8} \approx 2.8, \quad L_{1,2} = 4 $

and

$\begin{bmatrix} 2 & 0\\ 0 & 2 \end{bmatrix}, \quad L_{2,1}= 4, \quad L_{1,2} = \sqrt{8} $

So minimizing the $L_{2,1}$ norm tends to prefer the structure of the first matrix over the second one, while minimizing the $L_{1,2}$ norm tends to prefer the structure second matrix over the first.

Thus the mixed norm allows you impose a soft constraint on the structure of the sparse solution that you're looking for. It's relatively easy to see that be you could also set it up to look for a sparse set of row vectors, each with a small $l_2$ norm. Deciding which to use is really dependent on how you set up your equations.

$\endgroup$
  • $\begingroup$ May you explain why “with $p = q = 1$ , this means the solution could have arbitrary elements set to non-zero coefficients”? May be I miss some points but not $L_{1}$ forces the coefficient to be zero as many as possible? $\endgroup$ – Jan Sep 26 '18 at 17:20
  • $\begingroup$ $L_1$ is normally used as a substitute for $L_0$, in order to make the problem convex - so I'm assuming you are looking for a sparse solution - as per the title of your question. Using $L_{11}$ the matrix $[ 0, 2, 0 ,0]$ and $[0, 0, 0, 2]$ have the same have the same norm. $\endgroup$ – David Sep 26 '18 at 22:58
  • 1
    $\begingroup$ I updated my answer to try to be more explicit. It is difficult to typeset matrices in the comments. $\endgroup$ – David Sep 27 '18 at 12:46
  • $\begingroup$ Thanks so much for updating the answer with matrices. One thing is may you check the paragraph before the last paragraph pls? $L2,1$ are written twice and I wonder may be one of them should be $L1,2$ norm? $\endgroup$ – Jan Sep 27 '18 at 13:09
  • $\begingroup$ Yes, you are correct. I made the correction. If the post does answer your question then I'd appreciate the upvote. $\endgroup$ – David Sep 27 '18 at 13:44

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.