Let X be some set and $X^r$ be the space of $r$-tuples of elements of $X$. The discrete metric on $X$ is $d(x,y) = 1$ if $x \neq y$ and $d(x,y) = 0$ if $x=y$. Now, suppose I combine discrete metrics on all of the $r$ dimensions of my tuple, using $L^1$, i.e. $d(\vec{x}, \vec{y}) = \sum_{i=1}^{d} d(x_i,y_i)$, i.e. the distance between two tuples is the number of coordinates on which they differ. This is a metric on $X^r$.

My question: Is there a commonly-used name or term for this metric? I'm sure there must be and it's just on the tip of my tongue.

Note: If $d$ had been the $L^1$ norm (i.e. $d(x,y) = \left|x-y\right|$) then the tuple metric would have been the Taxicab Metric, a.k.a. the Manhattan Distance.

  • $\begingroup$ the $1$-product metric en.wikipedia.org/wiki/Product_metric ? If you meant $\sum_i d(x_i , y_i)$. $\endgroup$ – Calvin Khor Feb 12 '18 at 14:40
  • $\begingroup$ @CalvinKhor: I did, but the 1-product metric is relative to any basic metric. So "the 1-product of discrete metrics"? $\endgroup$ – einpoklum Feb 12 '18 at 15:21
  • $\begingroup$ Perhaps you are thinking of the "taxicab metric"? I don't think that phrase is used much outside of the contex of the Euclidean plane, but I see no reason that one could not talk about the "taxicab product" of two metric spaces (although in that context there's nothing special about discrete metrics). $\endgroup$ – Lee Mosher Feb 12 '18 at 15:29
  • $\begingroup$ Sure. The wikipedia page defines it for a product of metric spaces $(X_i,d_i)$ for which $d_i$ is already chosen beforehand, so no ambiguity should arise $\endgroup$ – Calvin Khor Feb 12 '18 at 15:30
  • $\begingroup$ @CalvinKhor: I was hoping for more of a "non-compound term", like what LeeMosher suggests. But thanks. $\endgroup$ – einpoklum Feb 12 '18 at 15:34

This is called the $\ell_0$ distance (or $L_0$ distance), e.g., second page of these notes or this blog post.

The idea is that "the $\ell_0$ norm" of a vector is the size of its support, i.e., the number of nonzero coordinates it has. Accordingly, $\ell_0$ metric is the number of coordinates in which two points differ.

There is a terminological conflict because "$L_0$ norm" is often understood as the limit of "$L^p$ norms" as $p\to 0$, which isn't the same. So one needs to clarify what the term means.

  • $\begingroup$ For finite dimension, why are these not the same? $\endgroup$ – einpoklum Feb 12 '18 at 19:22
  • $\begingroup$ Maybe because people want consistent definition for finite and infinite case, and so they make modifications that affect the finite case as well... like weight $2^{-n}$ for $n$th variable. $\endgroup$ – user357151 Feb 12 '18 at 19: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.