where \(\varepsilon >0\)  is a positive small tolerance.
This can be achieved within \(K = {\mathcal {O}}(|| C ||_{\infty }^2\log n\, \varepsilon ^{-2})\)  Sinkhorn iterations if we set \(\lambda = 4 \,\varepsilon ^{-1}\log n\)  [1]}.
See also [2]} for a less sharp bound on the number of iterations.
The bounds presented in [1]}, [2]} suggest that the number of iterations depends weakly on \(n\) .
The main computational bottleneck of Sinkhorn's algorithm is however
the two vector-matrix multiplications against kernels \(Q\)  and
\(Q^{\top }\)  needed in each iteration with complexity \({\mathcal {O}}(n^2)\)  if implemented naively.
Overall, Sinkhorn's algorithm can compute an \(\varepsilon \) -approximate solution of
the unregularized OT problem in \({\mathcal {O}}(K n^2) = {\mathcal {O}}(n^2\log n)\)  operations. We also refer to Section 4.3 in [5]} for a
few strategies that may improve this complexity. In particular, the
authors in [6]} exploited possible separability of
cost metrics (closely related to assumption A1 in Section
REF  of the present work) to reduce the quadratic
complexity to
\({\mathcal {O}}(n^{1 + 1/d} \, \log n)\) ; see also Remark 4.17 in
[5]}.
It is to be noted that although this improved cost is no longer quadratic (except when \(d=1\) ), the resulting algorithm will still be a polynomial time
algorithm whose complexity includes a term \(n^{\gamma }\)  with
\(\gamma = 1+1/d>1\) .
Our goal here is to exploit other possible structures in the kernels
and further reduce the cost to a log-linear cost, thereby delivering
an algorithm that runs faster than any polynomial time algorithm.
