7

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?

no_name
  • 445
  • 1
  • 5
  • 10
  • 2
    Does $\Vert\alpha x\Vert=|\alpha|\Vert x\Vert$ hold? – David Mitra May 16 '13 at 11:25
  • 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? – no_name May 16 '13 at 11:29
  • 1
    pseudonorm has a definition as norm has. this doesn't seem to be a pseudonorm. –  May 16 '13 at 11:30
  • mmm, considering https://ccrma.stanford.edu/~jos/gradient/Vector_Space_Concepts.html $\ell_0$ is neither a norm nor a pseudo-norm... – no_name May 16 '13 at 11:38

1 Answers1

11

$\| \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.

Robert Cardona
  • 9,271
  • What do you mean "it is not a pseudo-norm"? I read in two published paper that it's called pseudo-norm! – Gigili Apr 26 '15 at 12:18
  • 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. – Robert Cardona Apr 26 '15 at 16:52
  • Thank you for your explanation – Gigili Apr 27 '15 at 06:39
  • 2
    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. – Stephen May 11 '15 at 23:57
  • Is there a proper (= mathematically precise) name to describe this function then? – ViktorStein Oct 17 '19 at 13:43