Skip to main content
fixed some formatting; changed wording to make it sound less useless
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

ForA longish comment follows below.

Sometimes we are more interested in measuring "distance", often one does not need the various notions imposed above"directed distances" or "dissimilarity" functions. The mostA notable example that springs to mind is that of asuch functions is the Bregman divergence.

$\newcommand{\rr}{\mathbb{R}}$

   Definition Let $\varphi : S \subseteq \rr^n \to \rr$ be a strictly convex function over a convex set $S$. The Bregman divergence $D_\varphi : S \times S \mapsto \rr_+$ is defined by: $$D_\varphi(x,y) := \varphi(x)-\varphi(y) - \langle\nabla \varphi(x), x-y\rangle.$$ From strict convexity of $\varphi$ it follows that:

  1. $D_\varphi(x,y) \ge 0$ with equality iff $x=y$.
  2. $D_\varphi(x,y)$ is a strictly convex function of $x$

Notice that $D_\varphi$ is almost always asymmetric, but it is still a very useful "distance-like" function that is heavily used in optimization, information-theory, statistics. Specific examples include:

  1. $\varphi(x)=x^Tx$ yields the squared Euclidean distance
  2. $\varphi(x)=\sum_i x_i\log x_i$ yields the famous Kullback-Leibler Divergence
  3. $\varphi(x)=-\sum_i \log x_i$ yields the so-called Burg-divergence

In optimization, it turns out that the convergence analysis of a certain convex optimization algorithm (Bregman's method) becomes simpler when judging convergence using $D_\varphi$, instead of Euclidean distance.

In statistics, there is a very nice bijection between (modulo minor technicalities) between Bregman divergences and the exponential family (e.g., Gaussians correspond to the squared Euclidean divergence, etc.)

My point about mentioning this example is that some of "evident" requirements on a distance that are laid out in the question, are not necessarily the only "right thing", both mathematically as well as philosophically.

For measuring "distance", often one does not need the various notions imposed above. The most notable example that springs to mind is that of a Bregman divergence

$\newcommand{\rr}{\mathbb{R}}$

 Definition Let $\varphi : S \subseteq \rr^n \to \rr$ be a strictly convex function over a convex set $S$. The Bregman divergence $D_\varphi : S \times S \mapsto \rr_+$ is defined by: $$D_\varphi(x,y) := \varphi(x)-\varphi(y) - \langle\nabla \varphi(x), x-y\rangle.$$ From strict convexity of $\varphi$ it follows that:

  1. $D_\varphi(x,y) \ge 0$ with equality iff $x=y$.
  2. $D_\varphi(x,y)$ is a strictly convex function of $x$

Notice that $D_\varphi$ is almost always asymmetric, but it is still a very useful "distance-like" function that is heavily used in optimization, information-theory, statistics. Specific examples include:

  1. $\varphi(x)=x^Tx$ yields the squared Euclidean distance
  2. $\varphi(x)=\sum_i x_i\log x_i$ yields the famous Kullback-Leibler Divergence
  3. $\varphi(x)=-\sum_i \log x_i$ yields the so-called Burg-divergence

In optimization, it turns out that the convergence analysis of a certain convex optimization algorithm (Bregman's method) becomes simpler when judging convergence using $D_\varphi$, instead of Euclidean distance.

In statistics, there is a very nice bijection between (modulo minor technicalities) between Bregman divergences and the exponential family (e.g., Gaussians correspond to the squared Euclidean divergence, etc.)

My point about mentioning this example is that some of "evident" requirements on a distance that are laid out in the question, are not necessarily the only "right thing", both mathematically as well as philosophically.

A longish comment follows below.

Sometimes we are more interested in measuring "directed distances" or "dissimilarity" functions. A notable example of such functions is the Bregman divergence.

$\newcommand{\rr}{\mathbb{R}}$  Definition Let $\varphi : S \subseteq \rr^n \to \rr$ be a strictly convex function over a convex set $S$. The Bregman divergence $D_\varphi : S \times S \mapsto \rr_+$ is defined by: $$D_\varphi(x,y) := \varphi(x)-\varphi(y) - \langle\nabla \varphi(x), x-y\rangle.$$ From strict convexity of $\varphi$ it follows that:

  1. $D_\varphi(x,y) \ge 0$ with equality iff $x=y$.
  2. $D_\varphi(x,y)$ is a strictly convex function of $x$

Notice that $D_\varphi$ is almost always asymmetric, but it is still a very useful "distance-like" function that is heavily used in optimization, information-theory, statistics. Specific examples include:

  1. $\varphi(x)=x^Tx$ yields the squared Euclidean distance
  2. $\varphi(x)=\sum_i x_i\log x_i$ yields the famous Kullback-Leibler Divergence
  3. $\varphi(x)=-\sum_i \log x_i$ yields the so-called Burg-divergence

In optimization, it turns out that the convergence analysis of a certain convex optimization algorithm (Bregman's method) becomes simpler when judging convergence using $D_\varphi$, instead of Euclidean distance.

In statistics, there is a very nice bijection between (modulo minor technicalities) between Bregman divergences and the exponential family (e.g., Gaussians correspond to the squared Euclidean divergence, etc.)

My point about mentioning this example is that some of "evident" requirements on a distance that are laid out in the question, are not necessarily the only "right thing", both mathematically as well as philosophically.

Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

For measuring "distance", often one does not need the various notions imposed above. The most notable example that springs to mind is that of a Bregman divergence

$\newcommand{\rr}{\mathbb{R}}$

Definition Let $\varphi : S \subseteq \rr^n \to \rr$ be a strictly convex function over a convex set $S$. The Bregman divergence $D_\varphi : S \times S \mapsto \rr_+$ is defined by: $$D_\varphi(x,y) := \varphi(x)-\varphi(y) - \langle\nabla \varphi(x), x-y\rangle.$$ From strict convexity of $\varphi$ it follows that:

  1. $D_\varphi(x,y) \ge 0$ with equality iff $x=y$.
  2. $D_\varphi(x,y)$ is a strictly convex function of $x$

Notice that $D_\varphi$ is almost always asymmetric, but it is still a very useful "distance-like" function that is heavily used in optimization, information-theory, statistics. Specific examples include:

  1. $\varphi(x)=x^Tx$ yields the squared Euclidean distance
  2. $\varphi(x)=\sum_i x_i\log x_i$ yields the famous Kullback-Leibler Divergence
  3. $\varphi(x)=-\sum_i \log x_i$ yields the so-called Burg-divergence

In optimization, it turns out that the convergence analysis of a certain convex optimization algorithm (Bregman's method) becomes simpler when judging convergence using $D_\varphi$, instead of Euclidean distance.

In statistics, there is a very nice bijection between (modulo minor technicalities) between Bregman divergences and the exponential family (e.g., Gaussians correspond to the squared Euclidean divergence, etc.)

My point about mentioning this example is that some of "evident" requirements on a distance that are laid out in the question, are not necessarily the only "right thing", both mathematically as well as philosophically.