3
$\begingroup$

I have seen the claim that the l0-norm ($\|X\|_0$ = support(X)) is a pseudo-norm because it does not satisfy all properties of a norm. I thought it to be triangle inequality, but am not able to show it by example. Can anyone give an example to show that the l0-norm does not satisfy the triangle inequality?

Thanks.

$\endgroup$
  • $\begingroup$ It does not violate triangle inequality. It's not positive homogeneous. $\endgroup$ – S.B. Jun 21 '13 at 4:03
  • $\begingroup$ This can't be the support of $X$. It must be its measure for some measure. The counting measure if $X$ is a finite-dimensional vector. The measure at use if $X$ is some measurable function. $\endgroup$ – Julien Jun 21 '13 at 15:03
8
$\begingroup$

is a semi-norm because it does not satisfy all properties of a norm.

This is a misuse of the term seminorm, which is defined as a norm, except that it's okay for a nonzero element to have seminorm $0$.

The cardinality of support satisfies the triangle inequality, since the support of the sum of two vectors is contained in the union of their supports.

But the property $\|\lambda x\|=|\lambda|\|x\|$ clearly fails for $l_0$: instead we have $\|\lambda x\|_0=\|x\|_0$ for all $\lambda\ne 0$.

$\endgroup$
  • $\begingroup$ Thanks, perhaps a better term is pseudo-norm? My memory was just clouded by glancing at semi-norm in some wiki articles without exactly reading through it. $\endgroup$ – Atul Deshpande Jun 21 '13 at 16:11
  • $\begingroup$ @AtulDeshpande Pseudo-norm is better, although it's also sometimes used as a synonym of "seminorm". Then there's quasinorm but it weakens the triangle inequality instead. I don't think there is a standard term for the concept obtained from norm by changing the homogeneity requirement. $\endgroup$ – ˈjuː.zɚ79365 Jun 21 '13 at 23:55

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.