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

Question

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,

• Sparse Nonnegative Matrix Factorization for Clustering eq.12
• Compressive Sensing of Jointly Sparse Signals as a Method for Dimensionality reduction of Mass Spectrometry Data eq.7
• L1/2 Sparsity Constrained Nonnegative Matrix Factorization for Hyperspectral Unmixing

Answer 1

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.