9
$\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$
  • 3
    $\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
11
$\begingroup$

"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. 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. 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.