Bregman Distance Function

A Bregman Distance Function is a distance function that is not symmetric nor satisfies the triangle inequality .

• AKA: Bregman Divergence.
• Example(s):
  • Kullback–Leibler divergence.
  • Itakura–Saito distance,
  • Frobenius Norm.
• Counter-Example(s):
  • Euclidean Distance.
• See: Itakura–Saito distance, Triangle Inequality, Distance function, Frobenius Norm.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://wikipedia.org/wiki/Bregman_divergence
  • QUOTE: In mathematics, a Bregman divergence or Bregman distance is similar to a metric, but does not satisfy the triangle inequality nor symmetry. There are three ways in which Bregman divergences are important. Firstly, they generalize squared Euclidean distance to a class of distances that all share similar properties. Secondly, they bear a strong connection to exponential families of distributions; as has been shown by (Banerjee et al. 2005), there is a bijection between regular exponential families and regular Bregman divergences. Finally, Bregman divergences appear in a natural way as regret functions in problems involving optimization over convex.

(...)

Let [math]\displaystyle{ F: \Omega \to \mathbb{R} }[/math] be a continuously-differentiable real-valued and strictly convex function defined on a closed convex set [math]\displaystyle{ \Omega }[/math].

The Bregman distance associated with F for points [math]\displaystyle{ p, q \in \Omega }[/math] is the difference between the value of F at point p and the value of the first-order Taylor expansion of F around point q evaluated at point p:

[math]\displaystyle{ D_F(p, q) = F(p)-F(q)-\langle \nabla F(q), p-q\rangle. }[/math]

2012

• (Li et al., 2012) ⇒ Liangda Li, Guy Lebanon, and Haesun Park. (2012). “Fast Bregman Divergence NMF Using Taylor Expansion and Coordinate Descent.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339582

---