# Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport
## 4 Sinkhorn-Knopp with Successive Overrelaxation
### Proposed Algorithm  
We first give a general convergence result that later serves as a basis to design an explicit algorithm. **Theorem 1**. : _Let \(\Theta_{1}\) and \(\Theta_{2}\) be two continuous functions of \(\gamma\) such that:_  
\[\forall\gamma\in\mathbb{R}_{+*}^{n_{1}n_{2}},\quad F(P_{\mathcal{C}_{k}}^{ \Theta_{k}(\gamma)}(\gamma))\leq F(\gamma), \tag{26}\]  
_where the inequality is strict whenever \(\gamma\
otin\mathcal{C}_{k}\). Consider the sequence defined by \(\gamma^{0}=e^{-\varepsilon/\varepsilon}\) and:_  
\[\gamma^{\ell+1} =P_{\mathcal{C}_{1}}^{\Theta_{1}(\gamma^{\ell})}(\gamma^{\ell})\] \[\gamma^{\ell+1} =P_{\mathcal{C}_{2}}^{\Theta_{2}(\tilde{\gamma}^{\ell+1})}( \tilde{\gamma}^{\ell+1}).\]  
_Then, the sequence \((\gamma^{\ell})\) converges to \(\gamma^{*}\)._  
**Lemma 2**. : _Let us take \(\gamma^{0}\) in \(\mathbb{R}_{+*}^{n_{1}n_{2}}\), and denote:_  
\[S=\Bigl{\{}\operatorname{diag}(u)\gamma^{0}\operatorname{diag}(v),\quad(u,v) \in\mathbb{R}_{+*}^{n_{1}+n_{2}}\Bigr{\}}\]  
_the set of matrices that are diagonally similar to \(\gamma^{0}\). Then, the set \(S\cap\mathcal{C}_{1}\cap\mathcal{C}_{2}\) contains exactly one element \(\gamma^{*}=P_{\mathcal{C}_{1}\cap\mathcal{C}_{2}}(\gamma^{0})\)._  
Figure 5: Value of \(\varphi_{\omega}(x)\). The function is positive above the red line, negative below. For any relaxation parameter \(\omega\) smaller than two, there exists a neighborhood of one on which \(\varphi_{\omega}(\cdot)\) is positive. Proof. : We refer to [2] for a proof of this lemma. Proof of the Theorem. : First of all, notice that the operators \(P^{\theta}_{\mathcal{C}_{k}}\) apply a scaling to lines or columns of matrices. All \((\gamma^{\ell})\) are thus diagonally similar to \(\gamma^{0}\):  
\[\forall\ell\geq 0,\quad\gamma^{\ell}\in S\]  
By construction of the functions \(\Theta_{k}\), the sequence of values of the Lyapunov function \((F(\gamma^{\ell}))\) is non-increasing. Hence, \((\gamma^{\ell})\) is precompact. If \(\zeta\) is a cluster point of \((\gamma^{\ell})\), let us define:  
\[\xi =P^{\Theta_{1}(\zeta)}_{\mathcal{C}_{1}}(\xi)\] \[\zeta^{\prime} =P^{\Theta_{2}(\zeta)}_{\mathcal{C}_{2}}(\xi).\]  
Then, by the continuity of the applications, \(F(\zeta)=F(\bar{\zeta})=F(\zeta^{\prime})\). From the hypothesis made on \(\Theta_{1}\) and \(\Theta_{2}\), it can be deduced that \(\zeta\) is in \(\mathcal{C}_{1}\) and is thus a fixed point of \(P_{\mathcal{C}_{1}}\), while \(\bar{\zeta}\) is in \(\mathcal{C}_{2}\). Therefore, \(\zeta^{\prime}=\bar{\zeta}=\zeta\) is in the intersection \(\mathcal{C}_{1}\cap\mathcal{C}_{2}\). By Lemma 2, \(\zeta=\gamma^{*}\), and the whole sequence \((\gamma^{\ell})\) converges to the solution. We can construct explicitly functions \(\Theta_{k}\) as needed in Theorem 1 using the following lemma. **Lemma 3**. : _Let \(1\leq\omega<\theta\). Then, for any \(\gamma\in\mathbb{R}_{+\ast}^{n_{1}n_{2}}\), one has:_  
\[F(P^{\omega}_{\mathcal{C}_{k}}(\gamma))\leq F(P^{\theta}_{\mathcal{C}_{k}}( \gamma)). \tag{27}\]  
_Moreover, equality occurs if and only if \(\gamma\in\mathcal{C}_{k}\)._  
Proof. : Thanks to Lemma 1, one knows that:  
\[F(P^{\omega}_{\mathcal{C}_{k}}(\gamma))-F(P^{\theta}_{\mathcal{C}_{k}}(\gamma ))=\langle\mu_{k},(\varphi_{\theta}-\varphi_{\omega})((A_{k}\gamma)\oslash\mu_{ k})\rangle.\]  
The function that maps \(t\in[1,\infty)\) to \(\varphi_{t}(x)\) is non-increasing since \(\partial_{t}\varphi_{t}(x)=(x^{1-t}-1)\log x\). Moreover, for \(x\
eq 1\), it is strictly decreasing. Thus, Inequality (27) is valid, with equality iff \(A_{k}\gamma=\mu_{k}\). We now argue that a good choice for the functions \(\Theta_{k}\) may be constructed as follows. Pick a target parameter \(\theta_{0}\in[1;2)\), which will act as an upper bound for the overrelaxation parameter \(\omega\), and a small security distance \(\delta>0\).