Comparing Measures of Sparsity

By Niall P. Hurley, Scott T. Rickard. 2008

855 citations recorded by the source corpus.

Sparsity of representations of signals has been shown to be a key concept of fundamental importance in fields such as blind source separation, compression, sampling and signal analysis. The aim of this paper is to compare several commonly-used sparsity measures based on intuitive attributes. Intuitively, a sparse representation is one in which a small number of coefficients contain a large proportion of the energy. In this paper, six properties are discussed: (Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates, and Babies), each of which a sparsity measure should have. The main contributions of this paper are the proofs and the associated summary table which classify commonly-used sparsity measures based on whether or not they satisfy these six propositions. Only two of these measures satisfy all six: the pq-mean with p les 1, q > 1 and the Gini index.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

In Signal Processing

Citations in the corpus

A Discrete Hard EM Approach for Weakly Supervised Question Answering (2019, methodology): “P ( z | x ; θ ) < (cid:15) }| | Z | (Hurley and Rickard, 2009) and show that the model with our method gives higher sparsity than the model with MML (59 vs. 36 with (cid:15) = 10 − 3 , 54 vs. 17 with (cid:15) = 10 − 4 on DROP).”
Question Answering through Transfer Learning from Large Fine-grained Supervision Data (2017, methodology): “Following Hurley and Rickard (2009), the sparsity of an attention map is defined by”
Learning Explainable Models Using Attribution Priors (2019, background): “Prior work on sparse linear regression has shown that the Gini coefﬁcient G of the weights, deﬁned as 0.5 minus the area under the CDF of sorted values, avoids such problems and corresponds more directly to a sparse model [12, 42].”
3D Human Pose Estimation from Monocular Images with Deep Convolutional Neural Network (2014, methodology): “[33] showed that the negative lp norm can be used for measuring the sparsity of a vector.”
Optimizing the Channel Selection and Classification Accuracy in EEG-Based BCI (2011, background): “the same as a large value, the presence of noise in the data may render the l0 norm completely ineffective in inducing sparsity [27].”
Disentangling Disentanglement in Variational Autoencoders (2018, methodology): “10 10 MM D ( q ( z ) , p ( z )) extrinsic metric (Hurley and Rickard, 2008).”
Bias Mitigation Post-processing for Individual and Group Fairness (2018, background): “Uniﬁed metrics for both group and individual fairness have recently been proposed [11] based on inequality indices [12].”
DeepHoyer: Learning Sparser Neural Network with Differentiable Scale-Invariant Sparsity Measures (2019, methodology): “Plenty of sparsity measurements have been used in the field of compressed sensing [16].”
Improving performance of deep learning models with axiomatic attribution priors and expected gradients (2020, background): “Previous work on sparse linear regression has shown that the Gini coefficient G of the weights, proportional to 0.5 minus the area under the cumulative distribution function of sorted values, avoids such problems and corresponds more directly to a sparse model 40,41 .”
Blind deconvolution using a normalized sparsity measure (2011, methodology): “In [9], different sparsity measures are compared using 6 heuristic criteria and the `1/`2 function satisfies all them.”
Progress measures for grokking via mechanistic interpretability (2023, methodology): “Beyond these, we will also measure (1) the Gini coefficient (Hurley & Rickard, 2009) of the norms of the Fourier components of W E and W L , which measures the sparsity of W E and W L in the Fourier basis, and (2) the ℓ 2 -norm of the weights during training, since weight decay should push these…”