How Is Mixed Norm (${L}_{1, 2 }$) Better than ${L}_{1}$ Norm for Sparse Representation?

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,

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.

• 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?
– Jan
Commented Sep 26, 2018 at 17:20
• $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. Commented Sep 26, 2018 at 22:58
• I updated my answer to try to be more explicit. It is difficult to typeset matrices in the comments. Commented Sep 27, 2018 at 12:46
• 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?
– Jan
Commented Sep 27, 2018 at 13:09
• Yes, you are correct. I made the correction. If the post does answer your question then I'd appreciate the upvote. Commented Sep 27, 2018 at 13:44