4
$\begingroup$

It is common in the compressed sensing literature to refer to the number of nonzero entries of a vector as its $\ell_0$ "norm." The scare quotes are there because strictly speaking, the $\ell_0$ "norm" is not a norm, but the terminology is not unreasonable since $$\lim_{p\to 0^+} \sum_{i=1}^n |v_i|^p$$ is indeed the number of nonzero numbers among the $v_i$. My question is, who first used this terminology? Wikipedia, as of this writing, claims it was Donoho, but no citation is given.

If no specific person can be credited with coining the terminology, is there at least some good evidence that it became popular only with the advent of the field of compressed sensing? I have had trouble doing searches because (as Wikipedia explains) "$\ell_0$ norm" has two different meanings.

ADDENDUM: Someone pointed out to me a 2001 paper by David Donoho, Uncertainty principles and ideal atomic decomposition, which calls the number of nonzero entries the "$\ell_0$ quasinorm." This is the earliest reference that I am aware of. Can anyone beat it?

$\endgroup$
1
  • $\begingroup$ David Donoho is alive. Would it be worth writing to him and share your knowledge so that Wikipedia can be corrected...statistics.stanford.edu/people/david-donoho $\endgroup$
    – ACR
    Commented Sep 18, 2023 at 19:42

1 Answer 1

4
$\begingroup$

Following the suggestion in AChem's comment, I wrote to David Donoho, and he suggested that I check the literature on interpolation of normed Abelian groups. Sure enough, the terminology can (essentially) be found in Section 6 of Jaak Peetre and Gunnar Sparr, Interpolation of normed Abelian groups, Annali di Matematica Pura ed Applicata 92 (1972), 217–262.

In this Section we assume that all groups in question consist of measurable functions $f$ defined on a domain $D$ of the $d$-dimensional real Cartesian space $\mathbb{R}^d$, with values in $\mathbb{R}$ or $\mathbb{C}$. … define $L_0 = L_0(D)$ as the space corresponding to the norm $$|| f ||_{L_0} = \mathrm{meas.} (\mathrm{supp.} f).$$ (Here $\mathrm{supp.} f$ denotes the support of $f$, i.e. a measurable set $E\subset D$ such that $f=0$ a.e. in $D-E$ and $f\ne 0$ a.e. in $D$; it is unique up to a nullset).

If we take $D$ to be a finite discrete set, then we recover the notion of the $\ell_0$ norm as being the number of nonzero entries. Peetre and Sparr may not be the earliest reference, but it does at least show that the concept was around long before compressed sensing was a "thing," even if compressed sensing led to an explosion in the attention devoted to the concept.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.