Let $\mathbf{x}$ be a vector in $\mathbb{R}^n$. We define the $\ell_0$ pseudo-norm by:$$\|\mathbf{x}\|_0=\#\left\{i : \mathbf{x}_i\neq0\right\}$$ Why $\|\cdot\|_0$ is not properly a norm?

  • 2
    $\begingroup$ Does $\Vert\alpha x\Vert=|\alpha|\Vert x\Vert$ hold? $\endgroup$ – David Mitra May 16 '13 at 11:25
  • $\begingroup$ O.K., thanks! Thus, we call it "pseudo-norm" because it is not mathematically a norm, but it acts as a norm. Is it correct? $\endgroup$ – no_name May 16 '13 at 11:29
  • 1
    $\begingroup$ pseudonorm has a definition as norm has. this doesn't seem to be a pseudonorm. $\endgroup$ – user59671 May 16 '13 at 11:30
  • $\begingroup$ mmm, considering ccrma.stanford.edu/~jos/gradient/Vector_Space_Concepts.html $\ell_0$ is neither a norm nor a pseudo-norm... $\endgroup$ – no_name May 16 '13 at 11:38

$\| \cdot \|_0$ is not properly a norm because:

  1. $\|\alpha x\| = \|x\|$ and hence $\|\alpha x \| = \vert \alpha \vert \|x\|$ if and only if $\vert \alpha \vert = 1$.

but observe that the other properties of a norm do hold:

  1. If $\|x\| = 0$, then $\# \{ i : x_i \neq 0\} = 0$ which means that $x_i = 0$ for all $i$ which means $x = 0$. We immediately have $x = 0$ imply $\|x\| = 0$.
  2. We get the triangle inequality from observing that $x_i + y_i \neq 0$ means $x_i, y_i \neq 0$ and hence $\|x + y\| = \# \{i : x_i + y_i \neq 0\} \leq \# \{i : x_i \neq 0\} + \# \{i : y_i \neq 0\} = \|x\| + \|y\|$.

Now, not being properly a norm doesn't make it a pseudonorm. There are different types of "not being properly a norm". A pseudonorm is a norm that satisfies all the norm properties except being positive-definite, that is, $\|x\| = 0$ implies $x = 0$. But that holds in this case. Moreover, a pseudonorm requires the absolute scalability property, which is the key part that fails here.

So it's not properly a norm and it's not a pseudonorm.

  • $\begingroup$ What do you mean "it is not a pseudo-norm"? I read in two published paper that it's called pseudo-norm! $\endgroup$ – Gigili Apr 26 '15 at 12:18
  • $\begingroup$ The definition for pseudo-norm I've seen is "it satisfies all the norm properties except being positive-definite". In the example, scalability fails, so it's not a pseudo-norm under that definition. $\endgroup$ – Robert Cardona Apr 26 '15 at 16:52
  • $\begingroup$ Thank you for your explanation $\endgroup$ – Gigili Apr 27 '15 at 6:39
  • 1
    $\begingroup$ A lot of papers refer to it as a "pseudo-norm" or "quasi-norm" but they do not mean this in the standard mathematical sense, they just mean it is not a norm, and are being loose with terminology. The pseudonorm definition in Robert's answer is quite standard. The definition of quasinorm seems to be a bit less standard. $\endgroup$ – Stephen May 11 '15 at 23:57
  • $\begingroup$ Is there a proper (= mathematically precise) name to describe this function then? $\endgroup$ – Viktor Glombik Oct 17 at 13:43

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.