# Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport
## 4 Sinkhorn-Knopp with Successive Overrelaxation
### Acceleration of the Local Convergence Rate  
In order to justify the acceleration of convergence that is observed in practice, we now study the local convergence rate of the overrelaxed algorithm, which follows from the classical convergence analysis of the linear SOR method. Our result involves the second largest eigenvalue of the matrix:  
\[M_{1}=\text{diag}(1\odot\mu_{1})\,\gamma^{*}\,\,\text{diag}(1\odot\mu_{2})^{t }\gamma^{*} \tag{31}\]where \(\gamma^{*}\) is the solution to the regularized OT problem (the largest eigenvalue is one, associated with the eigenvector \(\mathbf{1}\)). We denote the second largest eigenvalue by \(1-\eta\); it satisfies \(\eta>0\)[36]. Proposition 2: _The SK algorithm converges locally at a linear rate \(1-\eta\). For the optimal choice of extrapolation parameter \(\theta^{*}=2/\left(1+\sqrt{\eta}\right)\), algorithm SK-SOR converges locally linearly at a rate \(\left(1-\sqrt{\eta}\right)/\left(1+\sqrt{\eta}\right)\). The local convergence of SK-SOR is guaranteed for \(\theta\in\left]0,2\right[\), and the linear rate is given in Figure 6 as a function of \(1-\eta\) and \(\theta\)._  
Proof: In this proof, we focus on the dual problem, and we recall the relationship \(\gamma^{\ell}=e^{\alpha^{\ell}/\varepsilon}\gamma^{0}e^{\beta^{\ell}/\varepsilon}\) between the iterates of the overrelaxed projection algorithm \(\gamma^{\ell}\) and the iterates \((\alpha^{\ell},\beta^{\ell})\) of the SOR algorithm on the dual problem (21), initialized with \((\alpha^{0},\beta^{0})=(0,0)\). The dual problem (6) is invariant by translations of the form \((\alpha,\beta)\mapsto(\alpha-k,\beta+k)\), \(k\in\mathbb{R}\), but is strictly convex up to this invariance. In order to deal with this invariance, consider the subspace \(S\) of pairs of dual variables \((\alpha,\beta)\) that satisfy \(\sum\alpha=\sum\beta\); let \(\pi_{S}\) be the orthogonal projection on \(S\) of kernel \((\mathbf{1},-\mathbf{1})\), and let \((\alpha^{*},\beta^{*})\in S\) be the unique dual maximizer in \(S\). Since one SK-SOR iteration is a smooth map, the local convergence properties of the SK-SOR algorithm are characterized by the local convergence of its linearization, which here corresponds to the SOR method applied to the maximization of the quadratic Taylor expansion of the dual objective \(E\) at \((\alpha^{*},\beta^{*})\). This defines an affine map \(M_{\theta}:(\alpha^{\ell},\beta^{\ell})\mapsto(\alpha^{\ell+1},\beta^{\ell+1})\) whose spectral properties are well known [22; 37] (see also [38] (Chapter 4) for the specific case of convex minimization and [39] for the non-strictly convex case). For the case \(\theta=1\), this is the matrix \(M_{1}\) defined in Equation (31). The operator norm of \(\pi_{S}\circ M_{1}\) is smaller than \(1-\eta\), so the operator \(\left(\pi_{S}\circ M_{1}\right)^{\ell}=\pi_{S}\circ M_{1}^{\ell}\) converges at the linear rate \(1-\eta\) towards zero (observe that by construction, \(\pi_{S}\) and \(M_{1}\) are co-diagonalizable and thus commute): for any \((\alpha,\beta)\in\mathbb{R}^{n_{1}}\times\mathbb{R}^{n_{2}}\), it holds \(\|\pi_{S}\circ M_{1}^{\ell}(\alpha-\alpha^{*},\beta-\beta^{*})\|_{2}\leq\|\pi_ {S}(\alpha-\alpha^{*},\beta-\beta^{*})\|_{2}(1-\eta)^{\ell}\). More generally, the convergence of \(\pi_{S}\circ M_{\theta}^{\ell}\) is guaranteed for \(\theta\in]0,2\right[\), with the linear rate:  
\[f(\theta,\eta)= \begin{cases}\theta-1&\text{if }\theta>\theta^{*}\\ \frac{1}{2}\theta^{2}(1-\eta)-(\theta-1)+\frac{1}{2}\sqrt{(1-\eta)\theta^{2}( \theta^{2}(1-\eta)-4(\theta-1))}&\text{otherwise.}\end{cases}  \tag{32}\]  
This function is minimized with \(\theta^{*}\coloneqq 2/(1+\sqrt{\eta})\), which satisfies \(f(\theta^{*},\eta)=(1-\sqrt{\eta})/(1+\sqrt{\eta})\). The function \(f\) is plotted in Figure 6.  
Figure 6: Local linear rate of convergence of the SK-SOR algorithm as a function of \(1-\eta\), the local convergence rate of the SK algorithm, and \(\theta\) the overrelaxation parameter. (Plain curve) The original rate is recovered for \(\theta=1\).