# What is an exact measure of sparsity?

I am currently working on compressed sensing and sparse representation of signals, specificly images.

I am frequently asked "what is sparsity definition?". I answer "if most elements of a signal are zero or close to zero, in some domain like Fourier or Wavelet, then this signal is sparse in that basis." but there is always a problem in this definition, "what does most elements mean? Is it 90 percent? 80 percenct? 92.86 percent?!" Here is where my question arises, is there any exact, i.e. numerical, definition for sparsity?

• I think you'll find that sparse is a term like bandwidth. They don't have a single definition that is applicable in all contexts. The answer is an unsatisfying "it depends." Aug 21, 2017 at 12:15
• @JasonR I think so, but is there any reference mentioning this? Aug 21, 2017 at 12:31
• It also depends on you're reconstruction schemes. Aug 21, 2017 at 13:35
• @Jason R Your conjunction with bandwidth is quite inspiring. Both have an amplitude-less notion over some support. Bandwidth seems to me to enforce some idea of "sufficient" connexity over sparsity Sep 3, 2017 at 15:17

"Is there any exact, i.e. numerical, definition for sparsity?" And by numerical, I understand both computable, and practically "usable". My take is that: not yet, as least, there is no consensus, yet there are some worthy contenders. The first option "count only non zero terms" is precise, but inefficient (sensitive to numerical approximation and noise, and very complex to optimize). The second option "most elements of a signal are zero or close to zero" is rather imprecise, either on "most" and "close to".

So "an exact measure of sparsity" remains elusive, without more formal aspects. One recent attempt to define sparsity performed in Hurley and Rickard, 2009 Comparing Measures of Sparsity, IEEE Transactions on Information Theory.

Their idea is to provide a set of axioms that a good sparsity measure ought to fulfill; for instance, a signal $$x$$ multiplied by a non zero constant, $$\alpha x$$, should have the same sparsity. In other terms, a sparsity measure should be $$0$$-homogeneous. Funnily, the $$\ell_1$$ proxy in compressive sensing, or in lasso regression is $$1$$-homogeneous. This is indeed the case for every norm or quasi-norm $$\ell_p$$, even if they tend to the (non-robust) count measure $$\ell_0$$ as $$p\to 0$$.

So they detail their six axioms, performed computations, borrowed from wealth analysis:

• Robin Hood (take from the rich, give to the poor reduces sparsity),
• Scaling (constant multiplication preserves sparsity),
• Rising Tide (adding the same non zero account reduces sparsity),
• Cloning (duplicating data preserves sparsity),
• Bill Gates (One man getting richer increases sparsity),
• Babies (adding zero values increases sparsity)

and probe known measures against them, revealing that the Gini index and some norm or quasi-norm ratios could be good candidates (for the latter, some details are provided in Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed $$\ell_1/\ell_2$$ Regularization, 2005, IEEE Signal Processing Letters). I sense that this initial work ought to be further developed (stay tune at SPOQ, Smoothed $$p$$ over $$q$$ $$\ell_p/\ell_q$$ quasi-norms/norms ratios). Because for a signal $$x$$, $$0< p\le q$$, the norm ratio inequality yields:

$$1\le \frac{\ell_p(x)}{\ell_q(x)}\le \ell_0(x)^{1/p-1/q}$$

and tends to $$1$$ (left-hand side, LHS) when $$x$$ is sparse, and to the right-hand side (RHS) when not. This work is published in 2020 as SPOQ: smooth ℓp-Over-ℓq Regularization for Sparse Signal Recovery applied to Mass Spectrometry (arxiv preprint, SPOQ published paper, IEEE Transactions on Signal Processing, 2020 and Matlab toolbox).

However, a sound measure of sparsity does not tell you whether the transformed data is sufficiently sparse, or not, for your purpose.

Finally, another concept used in compressive sensing is that of the compressibility of signals, where the re-ordered (descending order) coefficient magnitudes $$c_{(k)}$$ follow a power law $$C_\alpha .(k)^{-\alpha}$$, and the bigger the $$\alpha$$, the sharper the decay.