Source-linked AI summary
Comparing Measures of Sparsity
Niall P. Hurley, Scott T. Rickard
TL;DR
Sparsity measures are numerous, and the paper asks which best captures intuitive behavior in applications where energy is concentrated among few coefficients. It formalizes six criteria, compares fifteen measures through proofs and empirical visualizations, and finds that only the Gini Index satisfies all six.
Problem
The paper addresses how to compare numerous sparsity measures when a sparse representation concentrates much of its energy in few coefficients.
Method
The paper formalizes six desirable sparsity criteria and compares fifteen popular measures using proofs, counterexamples, and graphical analyses on parameterized distributions.
Results
Only the Gini Index satisfies all six criteria; the Gini Index and Hoyer measure outperform the other measures in the graphical examples.
Takeaways & Limitations
Selecting a sparsity measure should account for which combinations of the six attributes it emphasizes; the paper encourages use and further study of the Gini Index.
Abstract
from arXiv · showhide
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 commonlyused 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 and the corresponding proofs. Only one of these measures satisfies all six: The Gini Index. measures based on whether or not they satisfy these six propositions and the corresponding proofs. Only one of these measures satisfies all six: The Gini Index.
I. INTRODUCTION
Sparsity is widely used across signal processing, machine learning, imaging, and related applications. This paper compares fifteen popular sparsity measures using six desirable characteristics.
- Sparsity supports applications including matrix factorization, signal recovery, compressed sensing, dictionary learning, sampling, and source separation.
- A sparse representation concentrates a large proportion of its energy in a small number of coefficients.
- The paper addresses the question of which sparsity measure is best by proposing six desirable characteristics and comparing fifteen measures.
- The study formalizes six scenarios as mathematical criteria, proves relationships among criteria, and compares the measures using proofs and graphical analyses.
- Only the Gini Index satisfies all six criteria, motivating its further use and study.
II. THE SIX CRITERIA
The paper defines sparsity through six behavioral criteria for coefficient distributions, using wealth-distribution analogies and a convention that larger S means greater sparsity.
- The six criteria are Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates, and Babies.
- Robin Hood: Robin Hood decreases sparsity by transferring amount from a larger coefficient to a smaller one without reversing their order.
- Scaling and Rising Tide: Scaling leaves sparsity unchanged under multiplication by a positive constant, while Rising Tide decreases sparsity when a constant is added to every coefficient.
- Cloning: Cloning requires sparsity to remain invariant when identical copies of a coefficient vector are concatenated.
- Bill Gates and Babies: Bill Gates increases sparsity as one coefficient becomes infinitely wealthy, whereas Babies increase sparsity when zero-valued coefficients are added to a population with nonzero total wealth.
- Measure definition: The measure maps complex coefficient vectors to real numbers, is permutation-invariant, uses coefficient magnitudes, and is defined to increase with sparsity.
A. Two Proofs
The proofs show that some sparsity criteria overlap: satisfying Robin Hood and Scaling implies Bill Gates, while adding Cloning also implies Babies.
- Theorem 2.1 states that satisfying D1 Robin Hood and D2 Scaling necessarily implies P1 Bill Gates.
- Theorem 2.1: The proof of Theorem 2.1 begins with an ascending-sorted vector and applies inverse Robin Hood operations that transfer mass toward the largest coefficient.
- Theorem 2.2 states that satisfying D1, D2, and D4 Cloning necessarily implies P2 Babies.
- Theorem 2.2: Theorem 2.2 clones the vector N + 1 times and redistributes one copy through inverse Robin Hood operations before applying Scaling and Cloning.
III. THE MEASURES OF SPARSITY
The paper reviews commonly used sparsity measures, including count-based, norm-like, entropy, kurtosis, and range-based measures, and notes their differing behavior and constraints.
- The section surveys popular sparsity measures and adjusts some definitions so greater sparsity produces a more positive measure.
- The ℓ0 measure counts non-zero coefficients but treats infinitesimally small and large non-zero values identically.
- The ℓ0 measure is difficult to optimize because its derivative provides no information, while noise makes it inappropriate without modification.
- The ℓ1 measure approximates ℓ0 while weighting large coefficients more than small coefficients and remaining easy to calculate.
- Alternative measures include ℓp variants, tanh, log, kurtosis, range-based uθ, and Shannon- or Gaussian-entropy diversity measures.
- The Hoyer measure is an exception among normalized measures because normalization can preserve more constraints rather than generally trading one constraint for another.
- Component-magnitude plots show that several measures approximate ℓ0 while providing gradients, but Shannon entropy measures prefer small non-zero components rather than zero components.
A. The Gini Index
The Gini Index is presented as a sparsity measure that weights coefficient contributions, has a graphical interpretation, and meets convergence expectations for sampled distributions.
- A sparsity measure should weight coefficients so changes in smaller coefficients remain visible rather than being overwhelmed by large coefficients.
- The Gini Index is defined after sorting coefficients from smallest to largest and is presented as a measure of their distribution.
- In the graphical interpretation, the Gini Index equals twice the area between the sorted coefficient-value curve and the 45° equality line.
- The 45° line represents the least sparse distribution, in which all coefficients have equal values.
- The Gini Index is expected to converge as more coefficients are drawn from a distribution, and the paper states that it meets this expectation.
- The paper connects the Gini Index’s origins in wealth inequality to sparsity as unequal energy distribution among signal coefficients.
IV. COMPARISON OF SPARSITY MEASURES
The paper compares fifteen sparsity measures against six criteria using proofs and counterexamples. The Gini Index is the only measure reported to satisfy all six criteria.
- The comparison evaluates fifteen sparsity measures against six criteria, using proofs and counterexamples summarized in tables and appendices.
- Six measures fail the Robin Hood example [0, 1, 3, 5] versus [0, 2, 3, 4], while seven satisfy the corresponding criterion.
- The paper describes Type A proofs as inequality-based and Type B proofs as derivative-based.
- Most measures satisfy Rising Tide, indicating that relative coefficient size is important when evaluating sparsity.
- Most measures do not satisfy Cloning, while the remaining criteria are satisfied by varying numbers of measures.
- κ4 and the Hoyer measure satisfy most of the criteria, whereas the Gini Index alone satisfies all six.
A. Numerical Sparse Analysis
The experiments vary distribution parameters or vector size to test how fifteen sparsity measures respond to controlled changes in coefficient distributions. The Gini Index and Hoyer measure are highlighted as convergent or strong-performing measures, while κ4 shows a late sharp increase near maximal sparsity.
- Experimental setup: Fifteen measures are evaluated on parameterized distributions whose sparsity can be controlled by changing a distribution parameter.The experiments use equal coefficients as the least sparse case and one nonzero coefficient as the most sparse case.
- Poisson experiment: For Poisson coefficients with λ = 5, sparsity is measured as vector length increases, with κ4, Hoyer, and Gini identified as convergent measures.The normalized plot compares sparsity against vector length.
- Bernoulli experiment: For Bernoulli coefficients, sparsity should increase as the zero probability p rises, and this occurs in some form for every measure except HS′.The coefficients are 0 with probability p and 1 otherwise, with measures scaled from 0 to 1.
- Bernoulli experiment: κ4 does not rise steadily with p but increases dramatically as the Bernoulli set approaches its sparsest state.The paper notes limited indication of increasing sparsity before this late rise.
- Poisson experiment: The Poisson figure contrasts distributions with λ = 5, 10, 15, and 30, expecting narrower peaks at smaller λ to have higher sparsity.The expectation is based on peak width in the probability density functions.
V. CONCLUSIONS
The paper defines six intuitive sparsity attributes, formalizes them as criteria, and compares commonly used measures using proofs and a summary table. The Gini Index is the only measure satisfying all six, while Hoyer is close behind and both satisfy all criteria when coefficient count is fixed.
- Main conclusion: The Gini Index is the only commonly used sparsity measure satisfying all six criteria.The comparison covers fifteen measures, with proofs provided in Appendices A and B.
- Main conclusion: The Hoyer measure fails only D4, invariance under cloning, and therefore comes close to satisfying all six criteria.The paper describes D4 as arguable for certain applications.
- Main conclusion: For applications with a fixed number of coefficients, both the Gini Index and Hoyer measure satisfy all criteria.
- Implications: The paper presents six intuitive attributes and compares sparsity measures to motivate selecting a measure appropriate to an application.Each measure emphasizes a different combination of attributes.
- Graphical evaluation: Graphical examples with controlled distribution sparsity show the Gini Index and Hoyer measure outperforming the other measures.The examples quantify sparsity while the distribution's sparsity is controlled.
A. Counter-Examples
The paper uses simple counter-examples to demonstrate when sparsity measures fail the stated criteria. An example involving the negative ℓ1 measure and D1 illustrates this approach, while Table IV summarizes compliance and proof references.
- Counter-example method: Counter-examples are presented as the most parsimonious method for showing non-compliance with sparsity criteria.The paper illustrates the method using the negative ℓ1 measure and D1.
- Counter-example method: For the example, S([0, 2, 3, 4]) = −9.
- Summary table: Table IV indicates whether each measure complies with each criterion and identifies proofs or marks cases as obvious.
- D1 Robin Hood: The ℓ0 measure fails D1 because a Robin Hood operation has no effect on the measured sparsity.D1 requires transferring energy from a larger coefficient to a smaller one to decrease sparsity.
B. Proofs
The proofs establish criterion compliance by substituting measure formulas into formal definitions or differentiating modified measures with respect to their parameters. Inequalities are verified under the criteria's stated constraints.
- Proof strategy: The proofs commonly substitute sparsity-measure formulas into the mathematical definitions of the six criteria.
- Proof strategy: Differentiating a modified sparsity measure with respect to its modifying parameter can establish a criterion.
- D3 proof: Showing ∂S(α + c⃗)/∂α < 0 for α > 0 proves D3 because any increase in α lowers the measure.
- Inequality verification: The inequality for the Robin Hood-style transformation is proved for ci > cj and 0 < α < ci−cj.The upper bound on α is one of the constraints required by the transformation.
2) −ℓp and D3:
The paper proves how commonly used sparsity measures behave under the six criteria, including Rising Tide, Robin Hood, and parameterized conditions. The results show substantial variation: some measures satisfy individual criteria, while the Gini Index satisfies all six.
- Criterion results: Theorems show that −ℓp fails D3, whereas several other measures, including κ4, Hoyer, and the Gini Index, satisfy specified criteria.The cited proofs establish both failures and satisfactions under their stated conditions.
- Support-based criteria: uθ fails D3 because adding a constant shifts both relevant supports without changing their widths, while cloning leaves those supports unchanged and satisfies D4.These conclusions follow directly from the support-based proofs.
- Robin Hood criterion: The Robin Hood operation transfers α from a larger coefficient ci to a smaller coefficient cj, with ci > cj and 0 < α < ci−cj.The proofs track how this reordering affects the sorted coefficients and the sparsity measure.
- Robin Hood criterion: The Gini Index satisfies the Robin Hood inequality S(c1, . . ., ci−α, . . ., cj+α, . . .) < S(c).The proof uses the reordered coefficient correspondence and positivity of the resulting terms.