English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a non-negative $n \times m$ real matrix $A$, the {\em matrix scaling}problem is to determine if it is possible to scale the rows and columns so thateach row and each column sums to a specified target value for it. This problemarises in many algorithmic applications, perhaps most notably as apreconditioning step in solving a linear system of equations. One of the mostnatural and by now classical approach to matrix scaling is the Sinkhorn-Knoppalgorithm (also known as the RAS method) where one alternately scales eitherall rows or all columns to meet the target values. In addition to beingextremely simple and natural, another appeal of this procedure is that iteasily lends itself to parallelization. A central question is to understand therate of convergence of the Sinkhorn-Knopp algorithm.  In this paper, we present an elementary convergence analysis for theSinkhorn-Knopp algorithm that improves upon the previous best bound. In anutshell, our approach is to show a simple bound on the number of iterationsneeded so that the KL-divergence between the current row-sums and the targetrow-sums drops below a specified threshold $\delta$, and then connect theKL-divergence with $\ell_1$ and $\ell_2$ distances. For $\ell_1$, we can usePinsker's inequality. For $\ell_2$, we develop a strengthening of Pinsker'sinequality, called (KL vs $\ell_1/\ell_2$) in the paper, which lower bounds theKL-divergence by a combination of $\ell_1$ and $\ell_2$ distance. Thisinequality may be of independent interest.  The idea of studying Sinkhorn-Knopp convergence via KL-divergence is not newand has indeed been previously explored. Our contribution is an elementary,self-contained presentation of this approach and an interesting new inequalitythat yields a significantly stronger convergence guarantee for the extensivelystudied $\ell_2$-error.

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling