5
$\begingroup$

Suppose we would like to compute the Euclidean projection of an arbitrary matrix $A$ onto the Birkhoff polytope, the set of doubly-stochastic matrices.

  1. Under some conditions on $A$, Sinkhorn's algorithm returns two diagonal matrices $D_1,D_2$ such that $D_1 A D_2$ is a doubly-stochastic matrix (which is unique). How does this matrix compare to the Euclidean projection, and if not, does this solution correspond to the projection under any particular metric?
  2. Are there known methods for solving this efficiently besides just formulating the problem as a quadratic program and applying a generic QP algorithm?
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

It is known that symmetric Sinkhorn algorithm in fact minimizes KL divergence [2,3]. In 1, authors present a method to minimize the Euclidean distance. This is called BBS (Bregmanian Bi-Stochastication). It is reported that BBS algorithm using the Euclidian distance has noticeably better potential of producing good clustering results than the SK algorithm, while Sinkhorn performs better in terms of doubly stochasticity.

(1) Learning a Bi-Stochastic Data Similarity Matrix, Fei Lang, Ping Li, Arnd Christian Konig

(2) J. N. Darroch and D. Ratcliff. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5):1470–1480, 1972.

(3) G. W. Soules. The rate of convergence of Sinkhorn balancing. Linear Algebra and its Applications, 150:3 – 40, 1991.

Regarding the projection of an arbitrary (arguably non-positive matrix): First, it is quite hard to project a matrix with negative entries. I would first project it onto the orthogonal matrices and then from there round it to the Birkhoff polytope. It is not a great procedure though, but a reasonable approach is given in :

(4) Approximating Orthogonal Matrices by Permutation Matrices, Alexander Barvinok, 2005

$\endgroup$
4
  • $\begingroup$ The original post seeks to find a bi-stochastication of an arbitrary matrix, but this paper seems to rely on the input being a similarity matrix. Are you aware of a more general algorithm? $\endgroup$
    – RMurphy
    May 7, 2020 at 17:21
  • $\begingroup$ Updated my reply, but unfortunately I am not aware of "the way" to do it. $\endgroup$
    – Tolga Birdal
    May 7, 2020 at 20:28
  • $\begingroup$ for what it's worth, I've done some toy experiments with method [1] inputting matrices with negative elements, etc. So far, the method does seem to converge quite reliably, but as of right now I don't know whether it scales well. I will take a look at the second paper you mentioned. Thanks! $\endgroup$
    – RMurphy
    May 7, 2020 at 20:52
  • $\begingroup$ I'm surprised. Please keep us posted on your findings. $\endgroup$
    – Tolga Birdal
    May 8, 2020 at 18:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .