8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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." $\endgroup$ – Jason R Aug 21 '17 at 12:15
  • $\begingroup$ @JasonR I think so, but is there any reference mentioning this? $\endgroup$ – M.Jalali Aug 21 '17 at 12:31
  • $\begingroup$ It also depends on you're reconstruction schemes. $\endgroup$ – MimSaad Aug 21 '17 at 13:35
  • 1
    $\begingroup$ @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 $\endgroup$ – Laurent Duval Sep 3 '17 at 15:17
10
$\begingroup$

You are very true. One attempt is 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, it should be $0$-homogeneous. Funnily, the $\ell_1$ proxy in compressive sensing is $1$-homogeneous. This is indeed the case for every norm/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 ratios could be good candidates. I sense that this initial work ought to be further developed.

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

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.

$\endgroup$

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.