The rate of convergence of Sinkhorn balancing (Q802704): Difference between revisions

Let x be an \(n\times n\) stochastic matrix with no zero columns. Define a function f into the \(n\times n\) stochastic matrices defined by \(f(x)_{ij}=z_{ij}(\sum_{k}z_{ik})^{-1}\) where each \(z_{ij}=x_{ij}(\sum_{k}x_{kj})^{-1}\), \(i,j=1,...,n\). The reviewer and \textit{P. Knopp} [Pac. J. Math. 21, 343-348 (1967; Zbl 0152.014)] have shown that if \(x\neq 0\) is an \(n\times n\) nonnegative matrix with total support, i.e. every \(x_{ij}>0\) lies on a positive diagonal, and if \(x^ 0_{ij}=x_{ij}(\sum_{k}x_{ik})^{-1}\), \(i,j=1,...,n\), then the iteration \(x^{t+1}=f(x^ t),\) \(t=0,1,2,...\), converges to a doubly stochastic limit D. The author shows that there is a nonnegative number \(\beta <1\) which depends only upon the limit D such that for every \(\epsilon >0\) there is a norm \(\|.\|\) for which \(\| x^{t+1}-D\| \leq (\beta +\epsilon)\| x^ t-D\|\) holds for every sufficiently large value of t. For \(\epsilon\), \(0<\epsilon <\gamma -\beta\) where \(\beta \leq \gamma <1\), this becomes \(\| x^{t+1}-D\| \leq \gamma \| x^ t-D\|\) for sufficiently large t. Thus \(x^ t\to D\) geometrically. If \(x^ 0\) only has support, i.e. at least one positive diagonal, the convergence may not be geometric. Consider \(\left( \begin{matrix} 1\\ \alpha_ 0\end{matrix} \quad \begin{matrix} 0\\ 1-\alpha_ 0\end{matrix} \right),\) where \(0<\alpha_ 0<1\). Then \(x^ t=\left( \begin{matrix} 1\\ \alpha_ 0/(1+2t\alpha_ 0)\end{matrix} \quad \begin{matrix} 0\\ (1-j\alpha_ 0+2t\alpha_ 0)/(1+2t\alpha_ 0)\end{matrix} \right)\) which converges to \(\left( \begin{matrix} 1\\ 0\end{matrix} \begin{matrix} 0\\ 1\end{matrix} \right)\) at a rate proportional to 1/t.