5
$\begingroup$

Question

The usual projection in $\mathbb{R}^n$ on a subspace can be defined as the point that minimizes the squared distance to the subspace. I'll call the Pythagorean theorem the easy fact that, given a point $x$, its projection $Px$ and another point $y$ in the subspace, $$ |x-y|^2 = |x - Px|^2 + |Px-y|^2 $$

An amazing fact to me is that, in a easy result (due to, I believe, Csiszar), the Kullback-Leibler divergence also obeys this Pythagorean theorem. The question is, is this an example of a more general phenomenon? Are there other interesting 'distance' functions that obey the Pythagorean theorem? Note that the KL divergence does not obey the triangle inequality. Besides the convergence of the alternating projection algorithm (see below), does this lead to any other interesting mathematics?

Background

I came to this question studying the "RAS" algorithm in economics. This algorithm takes a matrix and gives a matrix with prescribed row and column sums by alternatingly scaling the rows and columns to have the prescribed sums. Csiszar [1] showed that this algorithm is exactly the alternating projection algorithm in disguise, except replacing the $L^2$ projection with the KL distance (Csiszar calls these I-projections). The proof of convergence is almost identical to the usual one, making use of Pinsker's inequality. This beautiful fact led me to the question above.

[1] Csiszár, Imre. "I-divergence geometry of probability distributions and minimization problems." The Annals of Probability (1975): 146-158. https://www.jstor.org/stable/2959270?seq=1

$\endgroup$
2
  • $\begingroup$ The so-called "Bregman divergences", which include both $\ell_2$ distance and KL divergence among others, obey the Pythagorean relation. For a nice summary, see Banerjee et al, "Clustering with Bregman Divergences", JMLR 2005, in particular p.1741. $\endgroup$
    – Artemy
    Jan 3 '20 at 22:54
  • $\begingroup$ Thank you. Can you post this as an answer? $\endgroup$ Jan 4 '20 at 1:45
5
$\begingroup$

The so-called "Bregman divergences", which include both $\ell_2$ distance and KL divergence among others, obey the Pythagorean relation. For a nice summary, see Banerjee et al, "Clustering with Bregman Divergences", JMLR 2005, in particular p.1741.

$\endgroup$

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.