# Best Metric to Compare Sparsity of Vectors

I solved the Basis Pursuit Denoising Problem looking for a sparse solution (I am in compressive sensing):
$$x^* = \text{arg min}_x \left\{\frac{1}{2} \lVert Ax-y\rVert_2^2 + \lambda \lVert x\rVert_1\right\}$$ for $$100$$ different $$\lambda$$ with ADMM.

Now I have $$100$$ different $$x^*$$ and want to find "the best one" out of them. Moreover, I solved several optimization problems for CS under noise and noisefree cases (e.g. also Lasso, etc.)

What is the best measure to determine sparsity? Found the paper Comparing Measures of Sparsity by Niall Hurley and Scott Rickard, saying it's the Gini index. Do you agree? In my opinion sparsity in this case is not all, isn't it? It's also about solving the equation as good as possible, e.g. having a small norm on:
$$\lVert A x^* -y \rVert_1$$

What do you recommend?

I am sorry I cannot comment your answer due to my low reputation. Gini and your suggested sparsity ratio ($l_1(x)/l_2(x)$) both give me the same value for $\lambda$. But

1. The problem I still see is that I cannot take into account how well the vector is solving the equation $Ax-y$. I would like to combine the residuum $l_1(A\hat{x}-y)$ and the sparsity $l_1(\hat{x})/l_2(\hat{x})$ into a new metric value. Do you know something from the literature?
2. Gini only works with positive values, but my measurement vector has lots of negative values. In my eyes, this is a heavy disadvantage because many sparse vectors can have negative values.
• A very acute question. I did some editing, but I believe your question is an open one. Why $\ell_1$ on the residuals? – Laurent Duval May 13 '17 at 19:03

[EDIT below] Norms like $\ell_p$, $p \ge 1$, or quasi-norms ($0<p< 1$) are all $1$-homogeneous: $\ell_p(\lambda x) = \lambda\ell_p( x)$. Which is not the case for the $\ell_0$ count measure, which is scale invariant.

I have been thinking a lot about Hurley's paper in the past years. A sparsity index should be scale invariant. From an more error perspective, Gini is excellent, but some $\ell_p( x)/\ell_q( x)$ norm ratios are almost as good. From an optimization perspective, Gini remains difficult as a penalty, while some $\ell_p( x)/\ell_q( x)$ ratios of norms are, slowly, becoming tractable. An example, and useful references, are given in A. Repetti et al., 2015, IEEE Signal Processing Letters, Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed ℓ1/ℓ2 Regularization.

So I would use both to try to measure sparsity alone.

[EDIT] Having the same $\lambda$ with both Gini and $\ell_1( x)/\ell_2( x)$ is by itself an interesting result. Sparsity of the recovered signal is one thing. The statistics of the residuals is another thing. I do not know of any standard metric combining both of them. Indeed, they don't have the same physical units: any loss quasi-norm

$$\ell_p(A\hat{x}−y)$$

will be $1$-homogeneous with respect to $y$, while the ratio $$\ell_1( \hat{x})/\ell_2( \hat{x})$$ has "no unit".

So for a linear combination, one needs a coupling weight $\omega$:

$$\ell_p(A\hat{x}−y) + \omega\ell_1( \hat{x})/\ell_2( \hat{x})$$

and like in the regression model, how do you chose $\omega$.

I believe that a 2D metric should be better, but then you lose the possibility to have a natural order to compare two outcomes. In a similar context, I am also struggling to find a nice quantitative comparison of scaled-, delayed- and warped-signals.