A generalised differential sparsity measure for reconstructing compressively sampled signals

Recent advances in signal compression, sampling and analysis have accentuated the importance of sparse representations of signals. A plethora of measures have been presented in the literature for estimating signal sparsity. In this paper, based on the concept that sparsity is encoded in the differences among the signal coefficients, we propose a novel parametric Generalised Differential Sparsity (GDS) measure and we rigorously prove that satisfies a set of objective criteria. Moreover, we prove that GDS interpolates between l0 norm and Gini Index (GI), both of which prove to be specific instances of GDS, demonstrating the generalisation power of our framework. In showcasing the potential of GDS, we incorporate it in Simultaneous Perturbation Stochastic Approximation (SPSA) method and experimentally investigate its efficacy in recovering compressively sampled sparse signals. In the SPSA context, we prove that GDS, in comparison to GI, loosens the bounds of the assumed sparsity of the original signals and reduces the minimum number of compressive samples, required to guarantee an almost perfect recovery of heavily compressed signals. Finally, through a comparison with various sparse recovery methodologies, we show the superiority of SPSA+GDS in recovering both synthetic and real data.