# On isometries and Tingley’s problem for the spaces
$T\left[\theta,\mathcal{S}_{\alpha}\right],1\leqslant\alpha<\omega_{1}$

Natalia Maślany  Jagiellonian University, Doctoral School of Exact and Natural
Sciences, Faculty of Mathematics and Computer Science, Institute of
Mathematics, Łojasiewicza 6, 30-348 Kraków, Poland and Institute of
Mathematics, Czech Academy of Sciences, Žitná 25, 115 67 Prague 1, Czech
Republic<EMAIL_ADDRESS>
###### Abstract.

We extend the existing results on surjective isometries of unit spheres in the
Tsirelson space $T\left[\frac{1}{2},\mathcal{S}_{1}\right]$ to the class
$T[\theta,\mathcal{S}_{\alpha}]$ for any integer $\theta^{-1}\geqslant 2$ and
$1\leqslant\alpha<\omega_{1}$, where $\mathcal{S}_{\alpha}$ denotes the
Schreier family of order $\alpha$. This positively answers Tingley’s problem
for these spaces, which asks whether every surjective isometry between unit
spheres can be extended to a surjective linear isometry of the entire space.

Furthermore, we improve the result stating that every linear isometry on
$T[\theta,\mathcal{S}_{1}]$ ($\theta\in\left(0,\frac{1}{2}\right]$) is
determined by a permutation of the first $\lceil\theta^{-1}\rceil$ elements of
the canonical unit basis, followed by a possible sign change of the
corresponding coordinates and a sign change of the remaining coordinates.
Specifically, we prove that only the first $\lfloor\theta^{-1}\rfloor$
elements can be permuted. This finding enables us to establish a sufficient
condition for being a linear isometry in these spaces.

###### Key words and phrases:

combinatorial spaces, combinatorial Tsirelson spaces, higher-order Schreier
families, isometry group, regular families, Schreier families, Tingley’s
problem

###### 2020 Mathematics Subject Classification:

46B04, 46B25, 46B45

The author was supported by GAČR grant GF20-22230L; RVO 67985840 and received
an incentive scholarship from the funds of the program Excellence Initiative -
Research University at the Jagiellonian University in Kraków.

##  1\. Introduction and the main result

In 1987, Tingley [23] proposed a question that has since become known as
Tingley’s problem:

_Let $X$ and $Y$ be normed spaces with unit spheres $\mathbb{S}_{X}$ and
$\mathbb{S}_{Y}$, respectively. Suppose that
$U\colon\mathbb{S}_{X}\rightarrow\mathbb{S}_{Y}$ is a surjective isometry. Is
there a linear isometry $\tilde{U}\colon X\rightarrow Y$ such that
$\tilde{U}|_{\mathbb{S}_{X}}=U$?_

Many authors have shown that Tingley’s problem has a positive solution for
surjective isometries of unit spheres in classical Banach spaces
$\ell_{p}(\Gamma)$, $L_{p}(\mu)$ $(1\leqslant p\leqslant\infty)$, and
$C(\Omega)$ (see, _e.g._ , [9, 10, 7, 11, 8, 12, 14, 16, 17, 20, 21, 15, 25]).
However, the general case remains open. Notable results in the search for a
solution to Tingley’s problem in specific spaces have been comprehensively
documented in surveys by A. M. Peralta [19], G. G. Ding [13], X. Yang, and X.
Zhao [26]. Recently, a positive solution to this isometric expansion problem
has been found for 2-dimensional Banach spaces (see [4]); nevertheless, the
answer remains unknown for higher dimensions. Positive solutions for certain
subspaces of function algebras, including closed function algebras on locally
compact Hausdorff spaces, have been presented in more recent studies (see
[6]).

The Tsirelson space $T$ (the dual of the space constructed by Tsirelson [24],
which was the first example of a space containing no isomorphic copies of
$c_{0}$ or $\ell_{p}$ for $1\leqslant p<\infty$) can be regarded as a special
case of the double-parameter family of Banach spaces
$T[\theta,\mathcal{S}_{\alpha}]$, where $\theta\in\left(0,\frac{1}{2}\right]$
and $1\leqslant\alpha<\omega_{1}$, with $\mathcal{S}_{\alpha}$ being the
Schreier family of order $\alpha$, where $\alpha$ is a countable ordinal.

In [18] we have characterized linear isometries of combinatorial Tsirelson
spaces. However, the methods employed assume linearity of the isometries
throughout the entire space. We improve the main theorem from this article by
proving the following first main result:

######  Theorem A.

Let $\theta\in\big{(}0,\frac{1}{2}\big{]}$. Then $U\colon
T\big{[}\theta,\mathcal{S}_{1}\big{]}\to
T\big{[}\theta,\mathcal{S}_{1}\big{]}$ is a linear isometry if and only if

$Ue_{i}=\left\\{\begin{array}[]{ll}\varepsilon_{i}e_{\pi(i)},&1\leqslant
i\leqslant\lfloor\theta^{-1}\rfloor\\\
\varepsilon_{i}e_{i},&i>\lfloor\theta^{-1}\rfloor\end{array}\right.\quad(i\in\mathbb{N})$

for some $\\{-1,1\\}$-valued sequence $(\varepsilon_{i})_{i=1}^{\infty}$ and a
permutation $\pi$ of $\big{\\{}1,2,\ldots,\lfloor\theta^{-1}\rfloor\big{\\}}.$

Then, following the approach of [22], where the author determine the
surjective isometries of the unit spheres of Tsirelson space
$T[\frac{1}{2},\mathcal{S}_{1}]$ and the modified Tsirelson space $T_{M}$ and
answer Tingley’s problem affirmatively in these spaces, we establish the
subsequent main Theorem.

######  Theorem B.

Let $\theta^{-1}\geqslant 2$ be an integer and let
$U\colon\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}\to\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$
be surjective isometry. If $\alpha=1$, then

$U\bigg{(}\sum_{i=1}^{\infty}a_{i}e_{i}\bigg{)}=\sum_{i=1}^{\theta^{-1}}\varepsilon_{i}a_{i}e_{\pi(i)}+\sum_{i=\theta^{-1}+1}^{\infty}\varepsilon_{i}a_{i}e_{i}$

and if $1<\alpha<\omega_{1}$, then

$U\bigg{(}\sum_{i=1}^{\infty}a_{i}e_{i}\bigg{)}=\sum_{i=1}^{\infty}\varepsilon_{i}a_{i}e_{i},$

for every
$\sum_{i=1}^{\infty}a_{i}e_{i}\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$,
where $(\varepsilon_{i})_{i=1}^{\infty}$ is a $\\{-1,1\\}$-valued sequence and
$\pi$ is a permutation of $\big{\\{}1,2,\ldots,\theta^{-1}\big{\\}}.$

This result together with Theorem A get an affirmative answer to the Tingley’s
problem in combinatorial Tsirelson spaces
$T\big{[}\theta,\mathcal{S}_{\alpha}\big{]}$ for an integer
$\theta^{-1}\geqslant 2$ and $1\leqslant\alpha<\omega_{1}$.

##  2\. Preliminaries

###  2.1. Combinatorial spaces

Let us denote by $(e_{i})_{i=1}^{\infty}$ the standard unit vector basis of
$c_{00}$ and by $[\mathbb{N}]^{<\omega}$ the family of finite subsets of
$\mathbb{N}.$ We adopt the following notation for sets
$F_{1},F_{2}\in[\mathbb{N}]^{<\omega}$: $F_{1}<F_{2}$ means that $\max
F_{1}<\min F_{2}$, and we say that $F_{1}$ and $F_{2}$ are consecutive in this
case. Additionally, we use the notation $F_{1}<n$ instead of $F_{1}<\\{n\\}$
for $n\in\mathbb{N}$.

######  Definition 1.

A family $\mathcal{F}\subset[\mathbb{N}]^{<\omega}$ is regular, whenever it is
simultaneously

  * $\bullet$

hereditary ($F\in\mathcal{F}$ and $G\subset F\implies G\in\mathcal{F}$);

  * $\bullet$

spreading ($\\{l_{1},l_{2},\dots,l_{n}\\}\in\mathcal{F}$ and $l_{i}\leqslant
k_{i}\implies\\{k_{1},k_{2},\dots,k_{n}\\}\in\mathcal{F}$);

  * $\bullet$

compact as a subset of the Cantor set $\\{0,1\\}^{\mathbb{N}}$ via the natural
identification of $F\in\mathcal{F}$ with

$\chi_{F}=\sum_{i\in F}e_{i}\in\\{0,1\\}^{\mathbb{N}}.$

The simplest examples of regular families include

$\mathcal{A}_{n}:=\big{\\{}F\in[\mathbb{N}]^{<\omega}\colon|F|\leqslant
n\big{\\}}\quad(n\in\mathbb{N})$

_i.e._ , for a given $n\in\mathbb{N}$, the family of subsets of $\mathbb{N}$
having at most $n$ elements. The family of Schreier sets, introduced by
Alspach and Argyros [1], is defined using these families in the following
manner.

######  Definition 2.

Given a countable ordinal $\alpha$, we define inductively the Schreier family
of order $\alpha$ as follows:

  * $\bullet$

$\mathcal{S}_{0}:=\mathcal{A}_{1};$

  * $\bullet$

if $\alpha$ is a successor ordinal, _i.e._ , $\alpha=\beta+1$ for some
$\beta<\omega_{1}$, then

$\mathcal{S}_{\alpha}:=\Bigg{\\{}\bigcup_{i=1}^{d}S^{i}_{\beta}\colon
d\leqslant
S^{1}_{\beta}<S^{2}_{\beta}<\cdots<S^{d}_{\beta},\,\,\big{\\{}S^{i}_{\beta}\big{\\}}_{i=1}^{d}\subset\mathcal{S}_{\beta}\text{
and }d\in\mathbb{N}\Bigg{\\}}\cup\big{\\{}\emptyset\big{\\}};$

  * $\bullet$

if $\alpha$ is a non-zero limit ordinal and
$\left(\alpha_{n}\right)_{n=1}^{\infty}$ is a fixed strictly increasing
sequence of successor ordinals converging to $\alpha$ with
$\mathcal{S}_{\beta_{n}}\subset\mathcal{S}_{\beta_{n+1}}$ for all
$n\in\mathbb{N}$, where $\alpha_{n}=\beta_{n}+1$ for all $n\in\mathbb{N}$, we
set

$\mathcal{S}_{\alpha}:=\big{\\{}S_{\alpha_{n}}\in[\mathbb{N}]^{<\omega}\colon
S_{\alpha_{n}}\in\mathcal{S}_{\alpha_{n}},\,\,n\leqslant\min
S_{\alpha_{n}}\text{ for some n}\big{\\}}\cup\big{\\{}\emptyset\big{\\}}.$

We emphasize that in the case where $\alpha$ is a limit ordinal, we require
the sequence $(\alpha_{n})_{n=1}^{\infty}$ cofinal in $\alpha$ to comprise
successor ordinals as needed in the proof of Theorem B. We can assume, and we
will, that $S_{\alpha_{n}}\subset S_{\alpha_{n+1}}$ for all $n\in\mathbb{N}$,
which will also be employed in the proof of Theorem B. Indeed, repeating the
proof of [5, Proposition 3.2.] in the case of Schreier families
$\big{\\{}S_{\xi}\big{\\}}_{\xi<\omega_{1}}$ which are multiplicative in the
sense of [5] we can also derive the desired result for Schreier families.
Elements belonging to $\mathcal{S}_{\alpha}$ are called
$\mathcal{S}_{\alpha}$_-sets_. The fact that these families are regular is
well-established; see [5][Proposition 3.2] or [3].

###  2.2. Combinatorial Tsirelson spaces

For a regular family $\mathcal{F}$ and $\theta\in\big{(}0,\frac{1}{2}\big{]}$,
we define the Banach space $T[\theta,\mathcal{F}]$ specializing it later to
space $T[\theta,\mathcal{S}_{\alpha}]$ for some countable ordinal $\alpha$.

For a vector $x=(a_{1},a_{2},\ldots,a_{n})\in c_{00}$ and a finite set
$E\subset\mathbb{N}$, we employ the symbol $Ex$ to represent the projection of
$x$ onto the space $[e_{i}\colon i\in E],$ given by

(2.1) $E\Bigg{(}\sum_{i=1}^{n}a_{i}e_{i}\Bigg{)}=\sum_{i\in E}a_{i}e_{i}.$

We denote by $\|\cdot\|_{0}$ the supremum norm on $c_{00}.$ Suppose that for
some $n\in\mathbb{N}$ the norm $\|\cdot\|_{n}$ has been defined. Let

$\|x\|_{n+1}=\max\big{\\{}\|x\|_{n},\|x\|_{T_{n}}\big{\\}}\quad(n\in\mathbb{N}),$

where

$\|x\|_{T_{n}}=\sup\bigg{\\{}\theta\sum_{i=1}^{d}\big{\|}E_{i}x\big{\|}_{n}\colon
E_{1}<\cdots<E_{d},\,d\in\mathbb{N},\,\\{E_{i}\\}_{i=1}^{d}\subset[\mathbb{N}]^{<\omega},\,\\{\min
E_{i}\\}_{i=1}^{d}\in\mathcal{F}\bigg{\\}}.$

We define the norm
$\|x\|_{\theta,\mathcal{F}}:=\sup_{n\in\mathbb{N}}\|x\|_{n}$ and denote by
$T[\theta,\mathcal{F}]$ the completion of $c_{00}$ with respect to it.

A proof by induction demonstrates that this norm is bounded above by the
$\ell_{1}$-norm and is given by the following implicit formula for $x\in
T[\theta,\mathcal{F}]$:

(2.2)
$\|x\|_{\theta,\mathcal{F}}=\max\big{\\{}\|x\|_{\infty},\|x\|_{T}\big{\\}},$

where

$\|x\|_{T}=\sup\bigg{\\{}\theta\sum_{i=1}^{d}\big{\|}E_{i}x\big{\|}_{\theta,\mathcal{F}}:E_{1}<\cdots<E_{d},\,d\in\mathbb{N},\,\\{E_{i}\\}_{i=1}^{d}\subset[\mathbb{N}]^{<\omega},\,\\{\min
E_{i}\\}_{i=1}^{d}\in\mathcal{F}\bigg{\\}}.$

It can be readily deduced from the definition that the unit vectors
$(e_{i})_{i=1}^{\infty}$ form an 1-unconditional basis of the space
$T[\theta,\mathcal{S}_{\alpha}]$ for a countable ordinal $\alpha$.

For $x_{1},x_{2}\in c_{00}$, we write $x_{1}<x_{2}$ whenever
$\operatorname{supp}\,x_{1}<\operatorname{supp}\,x_{2}$ and for
$n\in\mathbb{N}$ we streamline the notation of $\operatorname{supp}\,x_{1}<n$
to $x_{1}<n.$

We adopt the following convention in this paper: we say that the norm of an
element $x\in T[\theta,\mathcal{F}]$ is given by sets
$E_{1}<E_{2}<\cdots<E_{d}$ for some $d\in\mathbb{N}$ (with $\\{\min
E_{i}\\}_{i=1}^{d}\in\mathcal{F}$) precisely when

$\|x\|_{\theta,\mathcal{F}}=\theta\cdot\sum_{i=1}^{d}\big{\|}E_{i}x\big{\|}_{\theta,\mathcal{F}}.$

##  3\. Linear isometries on $T[\theta,\mathcal{S}_{1}]$ spaces for
$\theta\in\big{(}0,\frac{1}{2}\big{]}$

For further considerations, let us fix $\theta\in\big{(}0,\frac{1}{2}\big{]}$
and let $\lfloor\theta^{-1}\rfloor$ and $\lceil\theta^{-1}\rceil$ be the floor
and the ceiling of $\theta^{-1}$, respectively. Note that we do not yet
require $\theta^{-1}$ to be an integer. Fix a countable ordinal
$\alpha\geqslant 1$. Throughout this paper we use
$\mathbb{\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}}$to denote the unit
sphere of $T[\theta,\mathcal{S}_{\alpha}]$.

In [18, Theorem A] we have obtained the following description of linear
isometries on combinatorial Tsirelson spaces.

######  Theorem 3.

Let $\theta\in\big{(}0,\frac{1}{2}\big{]}$. If $U\colon
T\big{[}\theta,\mathcal{S}_{1}\big{]}\to
T\big{[}\theta,\mathcal{S}_{1}\big{]}$ is a linear isometry, then

$Ue_{i}=\left\\{\begin{array}[]{ll}\varepsilon_{i}e_{\pi(i)},&1\leqslant
i\leqslant\lceil\theta^{-1}\rceil\\\
\varepsilon_{i}e_{i},&i>\lceil\theta^{-1}\rceil\end{array}\right.\quad(i\in\mathbb{N})$

for some $\\{-1,1\\}$-valued sequence $(\varepsilon_{i})_{i=1}^{\infty}$ and a
permutation $\pi$ of $\big{\\{}1,2,\ldots,\lceil\theta^{-1}\rceil\big{\\}}.$

Armed with this result, we are now ready to prove Theorem A.

###### Proof.

Suppose that $U\colon T\big{[}\theta,\mathcal{S}_{1}\big{]}\to
T\big{[}\theta,\mathcal{S}_{1}\big{]}$ is a linear isometry.If $\theta^{-1}$
is an integer, there is nothing to prove, so assume that this is not the case.
Then $\lceil\theta^{-1}\rceil-1=\lfloor\theta^{-1}\rfloor$ and
$\lceil\theta^{-1}\rceil>\theta^{-1}$.

It is enough to show that for any $i\neq\lceil\theta^{-1}\rceil$ holds
$\pi(i)\neq\lceil\theta^{-1}\rceil$.

Let $i\in\\{1,2,\ldots,\lceil\theta^{-1}\rceil-1\\}$ and suppose for the
contrary that $\pi(i)=\lceil\theta^{-1}\rceil$, _i.e._ ,
$Ue_{i}=\varepsilon_{i}e_{\lceil\theta^{-1}\rceil}$. Then, by Theorem 3, for
any indices
$\lceil\theta^{-1}\rceil<j_{1}<j_{2}<\cdots<j_{\lceil\theta^{-1}\rceil-1}$ we
have

$\Bigg{\|}Ue_{i}-\sum_{k=1}^{\lceil\theta^{-1}\rceil-1}Ue_{j_{k}}\Bigg{\|}=\bigg{\|}\varepsilon_{i}e_{\lceil\theta^{-1}\rceil}-\sum_{k=1}^{\lceil\theta^{-1}\rceil-1}\varepsilon_{j_{k}}e_{j_{k}}\bigg{\|}=\theta\cdot\lceil\theta^{-1}\rceil>1.$

On the other hand, since $U$ is a linear isometry, we obtain

$\Bigg{\|}Ue_{i}-\sum_{k=1}^{\lceil\theta^{-1}\rceil-1}Ue_{j_{k}}\Bigg{\|}=\Bigg{\|}Ue_{i}-U\Bigg{(}\sum_{k=1}^{\lceil\theta^{-1}\rceil-1}e_{j_{k}}\Bigg{)}\Bigg{\|}=\Bigg{\|}e_{i}-\sum_{k=1}^{\lceil\theta^{-1}\rceil-1}e_{j_{k}}\Bigg{\|}=1.$

This contradiction finishes the proof that the isometry has the desired form.

To show that all such maps are indeed isometries, we refer the reader to [2,
Theorem 4.1] for technical details, because the same argument as for
$\theta^{-1}$ being an integer applies. ∎

##  4\. Isometries on $\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$ for an
integer $\theta^{-1}\geqslant 2$ and $1\leqslant\alpha<\omega_{1}$

To prove Theorem B we need a series of lemmas; the proofs emulate that of
[22].

######  Lemma 4.

Let $u,v\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$. Then for $\alpha=1$
we have [enumerate] $\min(\|u+y\|,\|u-y\|)\leqslant 1$ for all
$y\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$ if and only if $u\in\\{\pm
e_{1},\pm e_{2},\ldots,\pm e_{\lfloor\theta^{-1}\rfloor}\\}$; If
$v\geqslant\lfloor\theta^{-1}\rfloor+1$ and
$\min(\|v+y\|,\|v-y\|)\leqslant\theta\cdot(\lfloor\theta^{-1}\rfloor+1)$ for
all $y\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$, then $v$ has one of the
following forms: $|v_{\lfloor\theta^{-1}\rfloor+1}|=1$ with
$|v_{i}|\leqslant\theta$ for all $i\neq\lfloor\theta^{-1}\rfloor+1$;
$v=\varepsilon e_{m}+ae_{\lfloor\theta^{-1}\rfloor+1}$ for some
$m\geqslant\lfloor\theta^{-1}\rfloor+2$, some $\varepsilon\in\\{-1,1\\}$ and
some $|a|\leqslant\theta$, and for $\alpha>1$ holds

  * (3)

$\min(\|u+y\|,\|u-y\|)\leqslant 1$ for all
$y\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$ if and only if $u=\pm
e_{1}$;

  * (4)

If $v>1$ and
$\min(\|v+y\|,\|v-y\|)\leqslant\theta\cdot(\lfloor\theta^{-1}\rfloor+1)$ for
all $y\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$, then $v=\pm e_{m}$ for
some $m>1$.

###### Proof.

[enumerate] ($\Leftarrow$) Proof of this implication is inspired by a part of
the proof of [2, Theorem 4.1]. Let $x=y\pm e_{i}$ for
$i\leqslant\lfloor\theta^{-1}\rfloor$. Suppose that the norm of $x$ is given
by certain sets $d\leqslant E_{1}<E_{2}<\cdots<E_{d}$ for some
$d\in\mathbb{N}$ in the sense that

(4.1) $\|x\|=\theta\cdot\sum_{j=1}^{d}\big{\|}E_{j}x\big{\|}.$

It is enough to show that $\|x\|\leqslant\|y\|$. Suppose that $\min E_{1}<i.$
Then

$d\leqslant\min E_{1}<i\leqslant{\theta^{-1}},$

so

$\theta\cdot\sum_{i=j}^{d}\big{\|}E_{j}x\big{\|}\leqslant\theta\cdot
d\cdot\|x\|<\|x\|.$

Hence (4.1) cannot hold; a contradiction. Suppose that $\min E_{1}=i.$ Then
$d=i$, so from (4.1) we have $\|x\|=\|E_{j}x\|$ for any $1\leqslant j\leqslant
d$. Hence for $j\geqslant 2$ holds

$\|x\|=\|E_{j}x\|=\|E_{j}y\|\leqslant\|y\|.$

If $\min E_{1}>i$ then obviously $\|x\|=\|y\|$.

Suppose that $\|x\|=\|x\|_{\infty}>1$. Then $|y_{i}+1|>1$ and $|y_{i}-1|>1$; a
contradiction.

($\Rightarrow$) The proof is similar to the proof of [22][Lemma 2.1.1]. Take
any indices
$\operatorname{supp}u<j_{1}<j_{2}<\ldots<j_{\lfloor\theta^{-1}\rfloor}$
instead of $2<k<l$.

Again, the proof is analogous to [22][Lemma 2.1.2]. Take
$\varepsilon=\frac{\theta^{-1}-\lfloor\theta^{-1}\rfloor+1-\|v\|_{\infty}}{4}>0$
at the beginning of the proof and indices
$\max\\{m,i\\}<j_{1}<j_{2}<\ldots<j_{\lfloor\theta^{-1}\rfloor}$ at the end of
the proof (instead of indices $\max\\{m,i\\}<n<n+1$). The proof of $(3)$ and
$(4)$ is similar to the proofs of $(1)$ and $(2)$, respectively. Indeed, it is
enough to take indices $j_{1}<j_{2}<\ldots<j_{\lfloor\theta^{-1}\rfloor}$ with
additional assumption: $j_{1}>{\lfloor\theta^{-1}\rfloor}$. ∎

######  Lemma 5.

Let $x\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$. Then $\|x+e_{n}\|=2$ if
and only if $x(n)=1$.

###### Proof.

We omit the proof of implication ($\Leftarrow$) because it is trivial. Assume
that $\|x+e_{n}\|=2$. It is enough to show that norm of vector $x+e_{n}$ is
the supremum norm.

Take any sets $d\leqslant E_{1}<E_{2}<\cdots<E_{d}$. We may assume that $n\in
E_{i_{0}}$ for some $i_{0}\in\\{1,2,\ldots,d\\}$. Indeed, if this is not the
case, we will not get a norm of vector $x+e_{n}$ greater than $1$, because
$\|x\|=1$.

Since $E_{i}e_{n}=0$ for $i\neq i_{0}$ and $\|x\|=1$ we obtain

$\begin{split}\theta\sum_{i=1}^{d}\|E_{i}(x+e_{n})\|&\leqslant\theta\sum_{i=1}^{d}(\|E_{i}x\|+\|E_{i}e_{n}\|)\\\
&=\theta\sum_{i=1}^{d}\|E_{i}x\|+\theta\|E_{i_{0}}e_{n}\|\\\
&\leqslant\theta(\theta^{-1}+1)<2.\end{split}$

∎

The proof of the subsequent lemma is analogous to the proof of [22, Lemma
2.3], so we skip it.

######  Lemma 6.

If
$U\colon\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}\to\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$
is an isometry satisfying
$-U(\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]})\subset
U(\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]})$, then $-U(e_{i})=U(-e_{i})$
for $i\in\mathbb{N}$.

######  Lemma 7.

Let $\theta^{-1}\geqslant 2$ be an integer and let
$U\colon\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}\to\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$
be surjective isometry. If $\alpha=1$ then

$Ue_{i}=\left\\{\begin{array}[]{ll}\varepsilon_{i}e_{\pi(i)},&1\leqslant
i\leqslant\theta^{-1}\\\
\varepsilon_{i}e_{i},&i>\theta^{-1}\end{array}\right.\quad(i\in\mathbb{N}),$

and if $\alpha>1$ then $Ue_{i}=\varepsilon_{i}e_{i}$, where
$(\varepsilon_{i})_{i=1}^{\infty}$ is some $\\{-1,1\\}$-valued sequence and
$\pi$ is a permutation of $\big{\\{}1,2,\ldots,\theta^{-1}\big{\\}}.$

###### Proof.

_Case 1_. Let $\alpha=1$.

_Step 1_. Fix $1\leqslant i\leqslant\theta^{-1}$.

For any $y\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$ there exists
$x\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$ such that $U(x)=y$. Since $U$ is
isometry, so

$\|U(e_{i})-y\|=\|U(e_{i})-U(x)\|=\|e_{i}-x\|.$

By Lemma 6 we obtain

$\|U(e_{i})+y\|=\|-U(-e_{i})+U(x)\|=\|e_{i}+x\|.$

Hence by Lemma 4 (1)

$\min\\{\|U(e_{i})+y\|,\|U(e_{i})-y\|\\}=\min\\{\|e_{i}+x\|,\|e_{i}-x\|\\}\leqslant
1.$

Thus, again by Lemma 4 (1), for each $i$ there is index
$\pi(i)\in\big{\\{}1,2,\ldots,{\theta^{-1}}\big{\\}}$ so that $U(e_{i})=\pm
e_{\pi(i)}$. Note that

$\qquad\quad\,1=\|e_{i}\pm e_{j}\|=\big{\|}U(e_{i})\pm
U(e_{j})\big{\|}=\|e_{\pi(i)}\pm e_{\pi(j)}\|$

for any $j\neq i$ in $\big{\\{}1,2,\ldots,{\theta^{-1}}\big{\\}}.$ Therefore
$\pi(j)\neq\pi(i)$ for $j\neq i,$ so $\pi$ is the desired permutation.

_Step 2_. Let $i>\theta^{-1}$. We will show that there is
$\varepsilon_{i}\in\\{-1,1\\}$ such that

$U(e_{i})=\varepsilon_{i}e_{\sigma(i)},$

for some permutation $\sigma$ of the set
$\mathbb{N}\setminus\\{1,2,\ldots,\theta^{-1}\\}$.

Note that

$\qquad\quad\,1=\|e_{i}\pm e_{j}\|=\big{\|}U(e_{i})\pm
U(e_{j})\big{\|}=\|U(e_{i})\pm e_{\pi(j)}\|$

for any $j$ in $\big{\\{}1,2,\ldots,{\theta^{-1}}\big{\\}},$ so
$U(e_{i})>\theta^{-1}$. Following the arguments in the proof of Lemma 5 it
follows that for any $x\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$ holds

$\min\\{\|e_{i}-x\|,\|e_{i}+x\|\\}\leqslant\theta+1$

Since $U$ is surjective, so

$\min\\{\|U(e_{i})-y\|,\|U(e_{i})+y\|\\}\leqslant\theta+1$

for any $y\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$.

By the Lemma 4 (b) there are
$\sigma,\tilde{\sigma}\colon\mathbb{N}\setminus\\{1,2,\ldots,\theta^{-1}\\}\rightarrow\mathbb{N}\setminus\\{1,2,\ldots,\theta^{-1}\\}$
such that

(4.2)
$\big{|}\big{(}U(e_{i})\big{)}(\sigma(i))\big{|}=1\quad\text{and}\quad\big{|}\big{(}U^{-1}(e_{i})\big{)}(\tilde{\sigma}(i))\big{|}=1,$

for all $i>\theta^{-1}$. We claim that for all $k,i>\theta^{-1}$ with $k\neq
i$ we have

(4.3)
$\big{(}U(e_{k})\big{)}(\sigma(i))=0\quad\text{and}\quad\big{(}U^{-1}(e_{k})\big{)}(\tilde{\sigma}(i))=0.$

Indeed,

$1=\|e_{i}\pm e_{k}\|=\|U(e_{i})\pm
U(e_{k})\|\geqslant\big{|}1\pm\big{(}U(e_{k})\big{)}(\sigma(i))\big{|},$

for $k\neq i$ in $\mathbb{N}\setminus\\{1,2,\ldots,\theta^{-1}\\}$, and
similarly for $U^{-1}$, so the conclusion follows. In particular $\sigma$ and
$\tilde{\sigma}$ are injective.

We will show that there exists $l>\theta^{-1}$ such that
$\big{|}\big{(}U(e_{l})\big{)}(\theta^{-1}+1)\big{|}=1$.

If $\big{|}\big{(}U(e_{\theta^{-1}+1})\big{)}(\theta^{-1}+1)\big{|}=1$ then
the thesis is fulfilled, so suppose that this is not the case. Since
$\theta^{-1}$ is an integer, so by Lemma 4 (b) we have
$U(e_{\theta^{-1}+1})=ae_{\theta^{-1}+1}+\varepsilon e_{m}$ for some
$m>\theta^{-1}+1$, some $|a|\leqslant\theta$ and some
$\varepsilon\in\\{-1,1\\}$. Then

(4.4) $1>\|U(e_{\theta^{-1}+1})-\varepsilon
e_{m}\|=\|e_{\theta^{-1}+1}-\varepsilon\cdot U^{-1}(e_{m})\|.$

Moreover, by (4.2), we have
$|\big{(}U^{-1}(e_{m})\big{)}(\tilde{\sigma}(m))|=1$. If
$\tilde{\sigma}(m)>\theta^{-1}+1$ then

$\|e_{\theta^{-1}+1}-\varepsilon\cdot
U^{-1}(e_{m})\|\geqslant\|e_{\theta^{-1}+1}-\varepsilon\cdot
U^{-1}(e_{m})\|_{\infty}\geqslant 1,$

so we obtain a contradiction with (4.4).

This means that $\tilde{\sigma}(m)=\theta^{-1}+1$, _i.e._ ,
$\big{|}\big{(}U^{-1}(e_{m})\big{)}(\theta^{-1}+1)\big{|}=1$. Hence from (4.3)
we have $\big{(}U^{-1}(e_{\theta^{-1}+1})\big{)}(\theta^{-1}+1)=0$.

This together with Lemma 4 (b) yields
$U^{-1}(e_{\theta^{-1}+1})=\tilde{\varepsilon}e_{\tilde{\sigma}(\theta^{-1}+1)}$
for some $\tilde{\varepsilon}\in\\{-1,1\\}$.

So
$U(e_{\tilde{\sigma}(\theta^{-1}+1)})=\tilde{\varepsilon}e_{\theta^{-1}+1}$,
hence $\tilde{\sigma}(\theta^{-1}+1)$ is the $l$ we are looking for.

This together with (4.3) gives us $\big{(}U(e_{i})\big{)}(\theta^{-1}+1)=0$
for any $i\neq l$ with $i>\theta^{-1}$. By Lemma 4 (b) we obtain

(4.5) $U(e_{i})=\varepsilon_{i}e_{\sigma(i)}$

for all $i\neq l$ with $i>\theta^{-1}$ and some $\\{-1,1\\}$-valued sequence
$(\varepsilon_{i})_{\begin{subarray}{c}i=\theta^{-1}+1,\\\ i\neq
l\end{subarray}}^{\infty}$ Hence

$U^{-1}(e_{\sigma(i)})=\varepsilon_{i}e_{i}$

for such $i$ and $(\varepsilon_{i})_{\begin{subarray}{c}i=\theta^{-1}+1,\\\
i\neq l\end{subarray}}^{\infty}$ . This together with (4.2) means that
$\tilde{\sigma}=\sigma^{-1}$, so $\sigma$ is surjective. Since for every
$p\in\operatorname{supp}(U(e_{l}))\setminus\sigma(l)$ there exists $i\neq l$
with $\sigma(i)=p$, _i.e._ , $\big{|}\big{(}U(e_{i})\big{)}(p)\big{|}=1$, by
(4.3) we have $\big{(}U(e_{l})\big{)}(p)=0$. Hence
$U(e_{l})=\varepsilon_{l}e_{\sigma(l)}$ for some
$\varepsilon_{l}\in\\{-1,1\\}$. This together with (4.5) gives as conclusion.

_Step 3_. We will show that $\sigma$ from _Step 2_ is an identity.

Define

$x_{k}:=k^{-1}\cdot\theta^{-1}\cdot(e_{k},e_{k+1},\ldots,e_{2k-1})$

for $k>\theta^{-1}$. Then

$\|U(x_{k})+U(e_{i})\|=\|x_{k}+e_{i}\|=\|x_{k}-e_{i}\|=\|U(x_{k})-U(e_{i})\|$

for all $i\notin\operatorname{supp}x_{k}$. Hence, by the statement of _Step 2_
we have

$\|U(x_{k})+e_{\sigma(i)}\|=\|U(x_{k})-e_{\sigma(i)})\|$

for all $i\notin\operatorname{supp}x_{k}$. Since $\|U(x_{k})\|=1$ it must be
$\big{(}U(x_{k})\big{)}(\sigma(i))=0$ for all
$i\notin\operatorname{supp}x_{k}$, so

(4.6)
$\operatorname{supp}U(x_{k})\subseteq\\{\sigma(k),\sigma(k+1),\ldots,\sigma(2k-1)\\}.$

We claim that $\sigma(k)\geqslant k$ for any $k>\theta^{-1}$.

Suppose that $\sigma(k)<k$. Then by (4.6) there is
$i\in\operatorname{supp}x_{k}$ such that

$\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}\geqslant(k-1)^{-1}\cdot\theta^{-1}.$

Indeed, if not, then we obtain a contradiction, because

$\|U(x_{k})\|<\max\big{\\{}(k-1)^{-1}\cdot\theta^{-1},\,\theta\cdot(k-1)\cdot(k-1)^{-1}\cdot\theta^{-1}\big{\\}}=1.$

Since $\sigma(\theta^{-1}+1)\geqslant\theta^{-1}+1$, assume firstly that
$k\in\\{\theta^{-1}+2,\theta^{-1}+3,\ldots,2\theta^{-1}\\}$. Then

$\begin{split}1+(k-1)^{-1}\cdot\theta^{-1}&\leqslant\big{\|}U(x_{k})+\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}e_{\sigma(i)}\big{\|}\\\
&=\big{\|}x_{k}+\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}U^{-1}(e_{\sigma(i)})\big{\|}\\\
&\leqslant\|x_{k}+e_{i}\|=\max\big{\\{}k^{-1}\cdot\theta^{-1}+1,\theta\cdot\big{(}k^{-1}\cdot\theta^{-1}\cdot
k+1\big{)}\big{\\}}\\\ &=1+k^{-1}\cdot\theta^{-1},\end{split}$

which cannot hold. Hence for $\theta^{-1}<k\leqslant 2\theta^{-1}$ we have
$\sigma(k)\geqslant k$.

Assume that $k>2\theta^{-1}$. Since $x_{k}-e_{i}$ is a vector that has $k-1$
coordiantes equal to $k^{-1}\theta^{-1}$, one coordiante whose modulus is
equal to $1-k^{-1}\theta^{-1}$ and the other coordinates equal to zero, we
obtain

(4.7) $\begin{split}\big{\|}U(x_{k})-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}e_{\sigma(i)}\big{\|}&\geqslant\|x_{k}-e_{i}\|\\\
&=\max\big{\\{}1-k^{-1}\cdot\theta^{-1},\,\theta\big{(}k^{-1}\cdot\theta^{-1}(k-2)+1\big{)}\big{\\}}\\\
&=1-2k^{-1}+\theta>1=\|U(x_{k})\|.\end{split}$

This means that
$1-\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}>\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}$,
so $1-2\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}>0$.

For any finite set $E_{j}\subset\mathbb{N}$, where $j\in\mathbb{N}$ we have

$\begin{split}\big{\|}E_{j}\big{(}U(x_{k})-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}&e_{\sigma(i)}\big{)}\big{\|}\\\
&\leqslant\big{\|}E_{j}\big{(}U(x_{k})-2\big{(}U(x_{k})\big{)}(\sigma(i))e_{\sigma(i)}\big{)}\big{\|}\\\
&+\big{\|}E_{j}\big{(}2\big{(}U(x_{k})\big{)}(\sigma(i))e_{\sigma(i)}-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}e_{\sigma(i)}\big{)}\big{\|}\\\
&=\|E_{j}U(x_{k})\|\\\
&+\big{\|}E_{j}\big{(}2\big{(}U(x_{k})\big{)}(\sigma(i))e_{\sigma(i)}-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}e_{\sigma(i)}\big{)}\big{\|},\end{split}$

The above equality holds because the corresponding vectors have equal
coordinate moduli. Multiplying by $\theta$ both sides of the above inequality
and taking the supremum over all consecutive sets $d<E_{1}<E_{2}<\dots<E_{d}$
for some $d\in\mathbb{N}$, we obtain

$\begin{split}\big{\|}\big{(}U(x_{k})-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}&e_{\sigma(i)}\big{\|}\\\
&\leqslant\|U(x_{k})\|\\\
&+\theta\cdot\big{\|}E_{j_{0}}\big{(}2\big{(}U(x_{k})\big{)}(\sigma(i))e_{\sigma(i)}-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}e_{\sigma(i)}\big{)}\big{\|}\end{split}$

for some $j_{0}\in\\{1,2,\ldots,d\\}$. Hence

$\begin{split}\big{\|}U(x_{k})-\text{sgn
}\big{(}\big{(}U(x_{k})\big{)}(\sigma(i))\big{)}e_{\sigma(i)}\big{\|}&\leqslant\|U(x_{k})\|+\theta\big{(}1-2\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}\big{)}\\\
&=1+\theta-2\theta\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}\\\
&\leqslant 1+\theta-2\theta(k-1)^{-1}\cdot\theta^{-1}.\end{split}$

which contradicts (4.7).

Doing the same for $U^{-1}$ instead of $U$ we obtain
$\sigma^{-1}(\sigma(k))\geqslant\sigma(k)$, so $k\geqslant\sigma(k)$, hence
$\sigma(k)=k$ for all $k>\theta^{-1}$. This ends the proof for $\alpha=1$.

_Case 2_. Suppose that $\alpha=\beta+1$ for some $\beta<\omega_{1}$.

The proof that $U(e_{1})=\varepsilon_{1}e_{1}$, where
$\varepsilon_{1}\in\\{-1,1\\}$ and for any $i>1$ there is
$\varepsilon_{i}\in\\{-1,1\\}$ such that

$U(e_{i})=\varepsilon_{i}e_{\sigma(i)}$

for some permutation $\sigma$ of set $\\{2,3,\ldots\\}$ is similar to the
previous case and much simpler, so we omit it. We will show that $\sigma$ is
an identity.

Fix $k>1$ and suppose that $t:=\sigma(k)<k$.

Note that every $\mathcal{S}_{\alpha}$-set whose minimum is $k$ is the union
of at most $k$ many $\mathcal{S}_{\beta}$-sets, so the idea of the proof of
this case is to choose the indices $j_{1}<j_{2}<\cdots<j_{m},$ for some
$m\in\mathbb{N},$ so that they creates $k$ many consecutive
$\mathcal{S}_{\beta}$-sets. At the same time, we must ensure that the set

$\\{\sigma(j_{1}),\sigma(j_{2}),\ldots,\sigma(j_{m})\\}$

associated with these indices is not $\mathcal{S}_{\alpha}$-set. We proceed as
follows. Choose indices
$j_{1}=k,j_{1}^{1}>\max\big{\\{}k,\theta^{-1}\big{\\}}$. Then take the next
index $j_{2}^{1}>\max\big{\\{}j_{1}^{1},\sigma(j_{1}^{1})\big{\\}}$, in
sequence $j_{3}^{1}>\max\big{\\{}j_{2}^{1},\sigma(j_{2}^{1})\big{\\}}$ and so
on.

Following this procedure, we may choose
$S^{1}_{\beta}=\\{j_{1}^{1},j_{2}^{1},\ldots,j_{m_{1}}^{1}\\}$ which is a
maximal $\mathcal{S}_{\beta}$-set. At the same time, we get the indices

$\\{\sigma(j_{1}^{1}),\sigma(j_{2}^{1}),\ldots,\sigma(j_{m_{1}}^{1})\\}$

so that

$\begin{split}\sigma(j_{1}^{1})&<j_{2}^{1}\leqslant\max\\{\,j_{2}^{1},\sigma(j_{2}^{1})\,\\}<j_{3}^{1}\leqslant\cdots\\\
&\cdots\leqslant\max\\{\,j_{m_{1}-1}^{1},\sigma(j_{m_{1}-1}^{1})\,\\}<j_{m_{1}}^{1}.\end{split}$

We choose the remaining maximal $\mathcal{S}_{\beta}$-sets according to the
following procedure. If
$S^{n}_{\beta}=\\{j^{n}_{1},j^{n}_{2},\ldots,j_{m_{n}}^{n}\\}$ for some $n<t$,
then choose
$S^{n+1}_{\beta}=\\{j^{n+1}_{1},j^{n+1}_{2},\ldots,j_{m_{n+1}}^{n+1}\\}$,
where $j_{1}^{n+1}>\max\\{\,j_{m_{n}}^{n},\sigma(j_{m_{n}}^{n})\,\\}$ and
$j_{p}^{n+1}>\max\\{\,j_{p-1}^{n+1},\sigma(j_{p-1}^{n+1})\,\\}$ for
$p\leqslant m_{n+1}$.

We finally arrive at indices

$j_{1}^{1}<j_{2}^{1}<\cdots<j_{m_{t}}^{t},$

that form a union of $t$ maximal $\mathcal{S}_{\beta}$-sets, so we got the
conclusion because we may choose $\mathcal{S}_{\beta}$-sets

(4.8) $k\leqslant S^{0}_{\beta}<S^{1}_{\beta}<\dots<S^{t}_{\beta},$

where

  * $\bullet$

$S^{0}_{\beta}=\\{j_{1}\\},$

  * $\bullet$

$S^{1}_{\beta}=\\{j_{1}^{1},j_{2}^{1},\ldots,j_{m_{1}}^{1}\\},$

  * $\bullet$

$\vdots$

  * $\bullet$

$S^{t}_{\beta}=\\{j^{t}_{1},j^{t}_{2},\ldots,j_{m_{t}}^{t}\\}.$

By the above construction,

$\tilde{S}_{m}:=\big{\\{}\sigma(j_{1}),\sigma(j_{1}^{1}),\sigma(j_{2}^{1}),\ldots\sigma(j_{m_{t}}^{t})\big{\\}},$

where $m$ is the cardinality of set $\tilde{S}_{m}$, is not
$\mathcal{S}_{\alpha}$-set because the Schreier family (of order $\beta$) is
spreading (see Definition 1). Indeed, suppose
$\tilde{S}_{m}\in\mathcal{S}_{\alpha}$, then $\tilde{S}_{m}$ is the union of
at most t-many successive $\mathcal{S}_{\beta}$-sets. Take any index
$j>\max\\{j_{m_{t}}^{t},\sigma(j_{m_{t}}^{t})\\}$. Then
$j_{1}^{1}<j_{2}^{1}<\cdots<j_{m_{t}}^{t}<j$ is the union of at most t-many
successive $\mathcal{S}_{\beta}$-sets by the spreading property of
$S_{\beta}$. This contradicts the choice of
$j_{1}^{1}<j_{2}^{1}<\cdots<j_{m_{t}}^{t}$ as the union of t-many maximal
$S_{\beta}$-sets.

Then we define

$x_{k}:=\theta^{-1}\cdot m^{-1}\cdot\sum_{i=1}^{m}e_{j_{i}}.$

As in (4.6) we have

$\operatorname{supp}U(x_{k})\subseteq\tilde{S}_{m}.$

To complete the proof, it is enough to replace each $k$ with $m$ in _Step 3_
of _Case 1_. Note that

$\big{|}\big{(}U(x_{k})\big{)}(\sigma(i))\big{|}\geqslant(m-1)^{-1}\cdot\theta^{-1}$

holds for some $i\in\\{j_{1},j_{2},\ldots,j_{m}\\}$ as we ensured that
$m>\theta^{-1}+1$.

_Case 3_ : Suppose that $\alpha$ is a limit ordinal.

We proceed as in Case $2$ for $\alpha=\alpha_{t},$ where
$(\alpha_{i})_{i=1}^{\infty}$ is a fixed strictly increasing sequence of
successor ordinals converging to $\alpha$ with
$\mathcal{S}_{\beta_{i}}\subset\mathcal{S}_{\beta_{n}}$ for $i\leqslant n$,
where $\alpha_{n}:=\beta_{n}+1$ for each $n\in\mathbb{N}$, choosing suitable
sequence $(j_{i})_{i=1}^{m}$. Indeed, $\mathcal{S}_{\beta_{t}}$-sets
$k\leqslant S^{0}_{\beta_{t}}<S^{1}_{\beta_{t}}<\dots<S^{t}_{\beta_{t}}$,
where

  * $\bullet$

$S^{0}_{\beta_{t}}=\\{j_{1}\\},$

  * $\bullet$

$S^{1}_{\beta_{t}}=\\{j_{1}^{1},j_{2}^{1},\ldots,j_{m_{1}}^{1}\\},$

  * $\bullet$

$\vdots$

  * $\bullet$

$S^{t}_{\beta_{t}}=\\{j^{t}_{1},j^{t}_{2},\ldots,j_{m_{t}}^{t}\\}.$

give rise to an $\mathcal{S}_{\alpha}$-set (even an
$\mathcal{S}_{\alpha_{t}}$-set). Moreover, the set

$\tilde{S}_{m}:=\big{\\{}\sigma(j_{1}),\sigma(j_{1}^{1}),\sigma(j_{2}^{1}),\ldots\sigma(j_{m_{t}}^{t})\big{\\}}$

is not $\mathcal{S}_{\alpha_{t}}$-set by the spreading property of
$S_{\beta_{n}}$ (as explained in Case 2). Hence
$\tilde{S}_{m}\notin\mathcal{S}_{\alpha}$ as we ensured that
$\mathcal{S}_{\beta_{i}}\subset\mathcal{S}_{\beta_{n}}$ for $i\leqslant n$.
Indeed, suppose $\tilde{S}_{m}\in\mathcal{S}_{\alpha}$. Then
$\tilde{S}_{m}\in\mathcal{S}_{\alpha_{j}}$ for some $j\leqslant t$, i.e.
$\tilde{S}_{m}$ is the union of at most $j$-many successive
$\mathcal{S}_{\beta_{j}}$-sets, i.e. $\mathcal{S}_{\beta_{t}}$-sets by the
assumption on $(\beta_{i})_{i}$. This means that
$\tilde{S}_{m}\in\mathcal{S}_{{\alpha}_{t}}$; a contradiction. ∎

######  Lemma 8.

If
$y=\sum_{i=1}^{\infty}b_{i}e_{i}\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$,
then $x=\sum_{i=1,i\neq j}^{\infty}\theta b_{i}e_{i}\pm
e_{j}\in\mathbb{S}_{T[\theta,\mathcal{S}_{\alpha}]}$. Moreover the norm of
vector $z=y-\sum_{i=1,i\neq j}^{\infty}\theta b_{i}e_{i}-\text{sgn
}(b_{j})e_{j}$ is equal to $1+|b_{j}|$.

###### Proof.

Let us note that

$x=(\theta b_{1},\theta b_{2},\ldots,\theta b_{j-1},\pm 1,\theta
b_{j+1}\ldots).$

The supremum norm is obviously not greater than 1, because $\|y\|=1$. Take any
sets $d\leqslant E_{1}<E_{2}<\cdots<E_{d}$. We may assume that $j\in
E_{i_{0}}$ for some $i_{0}\in\\{1,2,\ldots,d\\}$. Indeed, if this is not the
case, we will not get a norm of vector $x$ greater than $1$, because
$\|y\|=1$.

Since

$\begin{split}\theta\sum_{i=1}^{d}\|E_{i}x\|&\leqslant\theta\sum_{i=1}^{d}(\|E_{i}(\theta
y)\|+\|E_{i}e_{j}\|)\\\
&=\theta\sum_{i=1}^{d}\theta\|E_{i}y\|+\theta\|E_{i_{0}}e_{j}\|\\\
&\leqslant\theta(\theta\cdot\theta^{-1}+1)=2\theta\leqslant 1,\end{split}$

so $\|x\|\leqslant 1$ as desired. The vector $z$ is of the form

$z=\big{(}(1-\theta)b_{1},\,(1-\theta)b_{2},\ldots,(1-\theta)b_{j-1},\,\pm(1+|b_{j}|),\,(1-\theta)b_{j+1},\ldots\big{)}.$

The supremum norm is $1+|b_{j}|$. As before, we show that the norm given by
some sets $d\leqslant E_{1}<E_{2}<\cdots<E_{d}$ is not larger. Indeed,

$\begin{split}\theta\sum_{i=1}^{d}\|E_{i}z\|&\leqslant\theta\sum_{i=1}^{d}\big{(}(1-\theta)\|E_{i}y\|+(1+|b_{j}|)\|E_{i}e_{j}\|\big{)}\\\
&\leqslant\theta\big{(}(1-\theta)\theta^{-1}+1+|b_{j}|\big{)}\\\
&=1+\theta|b_{j}|<1+|b_{j}|.\end{split}$

∎

We are now ready to prove Theorem B.

###### Proof.

Fix $\alpha=1$. Let $\theta^{-1}\geqslant 2$ be an integer. By Lemma 7
isometry $U$ is of the form

$Ue_{i}=\left\\{\begin{array}[]{ll}\hat{\varepsilon}_{i}e_{\pi(i)},&1\leqslant
i\leqslant\theta^{-1}\\\
\hat{\varepsilon}_{i}e_{i},&i>\theta^{-1}\end{array}\right.\quad(i\in\mathbb{N}),$

where $(\hat{\varepsilon}_{i})_{i=1}^{\infty}$ is some $\\{-1,1\\}$-valued
sequence and $\pi$ is a permutation of
$\big{\\{}1,2,\ldots,\theta^{-1}\big{\\}}.$

Define $\hat{\pi}(i)$ as $\pi(i)$ for $1\leqslant i\leqslant\theta^{-1}$ and
$\hat{\pi}(i)=i$ for $i>\theta^{-1}$. For $i\in\mathbb{N}$ let us set
$\varepsilon_{i}:=\big{(}U(e_{i})\big{)}\big{(}{\hat{\pi}(i)}\big{)}$.

Fix $x=\sum_{i=1}^{\infty}a_{i}e_{i}\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$
and take
$y=\sum_{i=1}^{\infty}b_{i}e_{i}\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$
such that $U(x)=y$. If $a_{i}$ is nonzero and $b_{i}=0$ then we use the
convention that $\text{sgn }(b_{i})=1$. Fix $j\in\mathbb{N}$ and take

$y_{j}=\sum_{i=1,i\neq\hat{\pi}(j)}^{\infty}\theta
b_{i}e_{i}-\varepsilon_{j}\text{sgn }(a_{j})e_{\hat{\pi}(j)}$

and

$z_{j}=\sum_{i=1,i\neq\hat{\pi}(j)}^{\infty}\theta b_{i}e_{i}-\text{sgn
}(b_{\hat{\pi}(j)})e_{\hat{\pi}(j)}.$

By Lemma 8 we have $\|y_{j}\|=1$ and $\|y-z_{j}\|=1+|b_{\hat{\pi}(j)}|$. Let
$x_{j}\in\mathbb{S}_{T[\theta,\mathcal{S}_{1}]}$ be such that
$U(x_{j})=y_{j}$. We obtain

$\|x_{j}-\text{sgn }(a_{j})e_{j}\|=\|U(x_{j})-\text{sgn
}(a_{j})U(e_{j})\|=\|y_{j}-\text{sgn
}(a_{j})\varepsilon_{j}e_{\hat{\pi}(j)}\|=2.$

So by Lemma 5 we have $x_{j}(j)=-\text{sgn }(a_{j})$. This yields

$1+|b_{\hat{\pi}(j)}|=\|y-z_{j}\|\geqslant\|y-y_{j}\|=\|U(x)-U(x_{j})\|=\|x-x_{j}\|\geqslant
1+|a_{j}|.$

Hence

(4.9) $|b_{\hat{\pi}(j)}|\geqslant|a_{j}|.$

Note that $\varepsilon_{i}=\big{(}U^{-1}(e_{\hat{\pi}(i)})\big{)}(i)$ and
$U^{-1}(e_{i})=\varepsilon_{\hat{\pi}^{-1}(i)}e_{\hat{\pi}^{-1}(i)}$.
Similarly, we define

$u_{j}=\sum_{i=1,i\neq\hat{\pi}^{-1}(j)}^{\infty}\theta
a_{i}e_{i}-\varepsilon_{\hat{\pi}^{-1}(j)}\text{sgn
}(b_{j})e_{\hat{\pi}^{-1}(j)}$

and

$v_{j}=\sum_{i=1,i\neq\hat{\pi}^{-1}(j)}^{\infty}\theta a_{i}e_{i}-\text{sgn
}(a_{\hat{\pi}^{-1}(j)})e_{\hat{\pi}^{-1}(j)}.$

Then

$\|U(u_{j})-\text{sgn }(b_{j})e_{j}\|=\|u_{j}-\text{sgn
}(b_{j})\varepsilon_{\hat{\pi}^{-1}(j)}e_{\hat{\pi}^{-1}(j)}\|=2.$

So $\big{(}U(u_{j})\big{)}(j)=-\text{sgn }(b_{j})$. Hence

$1+|a_{\hat{\pi}^{-1}(j)}|=\|x-v_{j}\|\geqslant\|x-u_{j}\|=\|U(x)-U(u_{j})\|=\|y-U(u_{j})\|\geqslant
1+|b_{j}|.$

This means that $|a_{\hat{\pi}^{-1}(j)}|\geqslant|b_{j}|$, which together with
(4.9) gives us $|a_{\hat{\pi}^{-1}(j)}|=|b_{j}|$. We moreover have
$\|x-v_{j}\|=\|x-u_{j}\|$, so $\varepsilon_{\hat{\pi}^{-1}(j)}\text{sgn
}(b_{j})=\text{sgn }(a_{\hat{\pi}^{-1}(j)})$ and finally
$b_{\hat{\pi}(j)}=\varepsilon_{j}a_{j}$ for $j\in\mathbb{N}$, hence the
conclusion follows.

Fix $1<\alpha<\omega_{1}$ and let $Ue_{i}=\hat{\varepsilon}_{i}e_{i}$, where
$(\hat{\varepsilon}_{i})_{i=1}^{\infty}$ is some $\\{-1,1\\}$-valued sequence.
The proof is exactly the same if we define $\hat{\pi}(i)$ as identity for any
$i\in\mathbb{N}$. ∎

## References

  * [1] Dale E. Alspach and Spiros Argyros.  Complexity of weakly null sequences.  Dissertationes Math. (Rozprawy Mat.), 321:44, 1992.
  * [2] L. Antunes and K. Beanland.  Surjective isometries on Banach sequence spaces: A survey.  Concrete Operators, 9(1):19–40, 2022.
  * [3] Spiros A. Argyros and Stevo Todorčević.  Ramsey Methods in Analysis.  Adv. Courses in Math. – CRM Barc. Basel: Birkhäuser, 2005.
  * [4] Taras Banakh.  Every 2-dimensional banach space has the Mazur–Ulam property.  Linear Algebra and its Applications, 632:268–280, 2022.
  * [5] Ryan M Causey.  Concerning the szlenk index.  Studia Mathematica, 236:201–244, 2017.
  * [6] María Cueto-Avellaneda, Daisuke Hirota, Takeshi Miura, and Antonio M Peralta.  Exploring new solutions to Tingley’s problem for function algebras.  Quaestiones Mathematicae, pages 1–32, 2022.
  * [7] Guang Gui Ding.  The representation theorem of onto isometric mappings between two unit spheres of $\ell^{1}(\Gamma)$-type spaces and the application to the isometric extension problem.  Acta Mathematica Sinica, 20(6):1089–1094, 2004.
  * [8] Guang-Gui Ding.  The isometric extension of the into mapping from a $L^{\infty}(\Gamma)$-type space to some Banach space.  Illinois Journal of Mathematics, 51(2):445–453, 2007.
  * [9] Guanggui Ding.  The 1-Lipschitz mapping between the unit spheres of two Hilbert spaces can be extended to a real linear isometry of the whole space.  Science in China Series A: Mathematics, 45:479–483, 2002.
  * [10] Guanggui Ding.  The isometric extension problem in the unit spheres of $\ell^{p}(\Gamma)$ $(p>1)$ type spaces.  Science in China Series A: Mathematics, 46:333–338, 2003.
  * [11] Guanggui Ding.  The representation theorem of onto isometric mappings between two unit spheres of $\ell^{\infty}$-type spaces and the application on isometric extension problem.  Science in China Series A: Mathematics, 47:722–729, 2004.
  * [12] GuangGui Ding.  The isometric extension of “into” mappings on unit spheres of AL-spaces.  Science in China Series A: Mathematics, 51(10):1904–1918, 2008\.
  * [13] GuangGui Ding.  On isometric extension problem between two unit spheres.  Science in China Series A: Mathematics, 52(10):2069–2083, 2009\.
  * [14] Xi Nian Fang and Jian Hua Wang.  Extension of isometries between the unit spheres of normed space E and $C(\Omega)$.  Acta Mathematica Sinica. English Series, 22(6):1819, 2006.
  * [15] Wang Jian.  On extension of isometries between unit spheres of $AL_{p}$\- spaces $(0<p<\infty)$.  Proceedings of the American Mathematical Society, 132(10):2899–2909, 2004.
  * [16] Rui Liu.  On extension of isometries between unit spheres of $L^{\infty}(\Gamma)$-type space and a banach space E.  Journal of mathematical analysis and applications, 333(2):959–970, 2007.
  * [17] Rui Liu and Lun Zhang.  On extension of isometries and approximate isometries between unit spheres.  Journal of mathematical analysis and applications, 352(2):749–761, 2009.
  * [18] Natalia Maślany.  Isometries of combinatorial Tsirelson spaces.  Proc. Amer. Math. Soc., 151:4475–4484, 2023.
  * [19] Antonio M Peralta.  A survey on tingley’s problem for operator algebras.  Acta Scientiarum Mathematicarum, 84:81–123, 2018.
  * [20] Dong-Ni Tan.  Nonexpansive mappings on the unit spheres of some banach spaces.  Bulletin of the Australian Mathematical Society, 80(1):139–146, 2009.
  * [21] Dong Ni Tan.  Extension of isometries on the unit sphere of $l^{p}$ spaces.  Acta Mathematica Sinica, English Series, 28:1197–1208, 2012.
  * [22] Dong-Ni Tan.  Isometries of the unit spheres of the Tsirelson space $T$ and the modified Tsirelson space $T_{M}$.  Houston J. Math, 2012.
  * [23] Daryl Tingley.  Isometries of the unit sphere.  Geometriae Dedicata, 22(3):371–378, 1987.
  * [24] B. Tsirelson.  It is impossible to embed $\ell_{p}$ or $c_{0}$ into an arbitrary Banach space (Russian).  Funkts. Anal. i Prilozhen English translation: Funct. Anal. Appl, 8:138–141, 1974.
  * [25] Xiuzhong Yang.  On extension of isometries between unit spheres of $L_{p}(\mu)$ and $L_{p}(\nu,H)$ $(1<p\neq 2)$, H is a Hilbert space).  Journal of mathematical analysis and applications, 323(2):985–992, 2006.
  * [26] Xiuzhong Yang and Xiaopeng Zhao.  On the extension problems of isometric and nonexpansive mappings.  In Mathematics Without Boundaries: Surveys in Pure Mathematics, pages 725–748. Springer, 2014.


# A note on overrelaxation in the
Sinkhorn algorithm

Tobias Lehmann Max-K. von Renesse∗ Universität Leipzig, Fakultät für
Mathematik und Informatik, Augustusplatz 10, 04109 Leipzig, Germany Alexander
Sambale∗ André Uschmajew Max Planck Institute for Mathematics in the Sciences,
04103 Leipzig, Germany

###### Abstract

We derive an a-priori parameter range for overrelaxation of the Sinkhorn
algorithm, which guarantees global convergence and a strictly faster
asymptotic local convergence. Guided by the spectral analysis of the
linearized problem we pursue a zero cost procedure to choose a near optimal
relaxation parameter.

##  1 Introduction and statement of result

The Sinkhorn algorithm is the benchmark approach to fast computation of the
entropic regularization of optimal transportation [3]. Ultimately, one is
faced with the following numerical problem: Given two probability vectors
$a\in\mathbb{R}_{+}^{m}$, $b\in\mathbb{R}^{n}_{+}$ and a matrix
$K\in\mathbb{R}^{m\times n}_{+}$, the goal is to find a pair of vectors
$(u,v)\in\mathbb{R}_{+}^{m}\times\mathbb{R}_{+}^{n}$ such that

$u{}\circ{}Kv=a\quad\mbox{and}\quad v{}\circ{}K^{\mathsf{T}}u=b,$ (1)

where $x{}\circ{}y$ denotes the component wise multiplication (Hadamard
product) of vectors of equal dimension. We assume $\min(m,n)\geq 2$.

In the standard Sinkhorn algorithm an approximating sequence
$(u_{\ell},v_{\ell})$ starting from an initial vector
$v_{0}\in\mathbb{R}_{+}^{n}$ is constructed via the update rule

$u_{\ell+1}=\frac{a}{Kv_{\ell}},\qquad
v_{\ell+1}=\frac{b}{K^{\mathsf{T}}u_{\ell+1}},$

where $\frac{x}{y}$ denotes the component wise division of vectors of equal
dimension. It is a classic result by Sinkhorn [12] that for any initial point
$v_{0}\in\mathbb{R}^{n}_{+}$ the algorithm converges to a solution
$(u^{*},v^{*})$ of (1). Moreover, the solution is unique modulo rescaling
$(tu^{*},t^{-1}v^{*})$, $t>0$. The rate of convergence, e.g. of suitably
normalized iterates $u_{\ell}/\|u_{\ell}\|$ and $v_{\ell}/\|v_{\ell}\|$, or
using other distance measures, is at least $O(\Lambda(K)^{2})$, where
$\Lambda(K)<1$ is the Birkhoff contraction ratio defined in (8) below [6]. See
also [11] for an overview.

In this note we discuss a modified version of the Sinkhorn algorithm employing
relaxation, which was recently proposed in [13] and [10]. It uses the update
rule

$u_{\ell+1}=u_{\ell}^{1-\omega}{}\circ{}\left(\frac{a}{Kv_{\ell}}\right)^{\omega},\qquad
v_{\ell+1}=v_{\ell}^{1-\omega}{}\circ{}\left(\frac{b}{K^{\mathsf{T}}u_{\ell+1}}\right)^{\omega},$
(2)

where $\omega>0$ is are suitably chosen relaxation parameter, and
exponentiation is understood component wise. In a log-domain formulation such
as (7) further below, the relation to the classic concept of relaxation in
(nonlinear) fixed point iterations will become immediately apparent. Note that
the iteration (2) still has the solution of (1) as its unique (modulo scaling)
fixed point. As illustrated in op. cit., choosing the parameter $\omega$
larger than one can significantly accelerate the convergence speed compared to
the standard Sinkhorn method, which sometimes can be slow. For optimal
transport, such an improvement could be in particular relevant in the regime
of small regularization, or when a high target precision is needed, such as in
applications in density functional theory [2].

While global convergence for $\omega\neq 1$ is not obvious anymore, local
convergence of the modified method is ensured for all $0<\omega<2$, and the
asymptotically optimal relaxation parameter can be determined from its
linearization at a fixed point $(u_{*},v_{*})$. In logarithmic coordinates,
the linearization of the standard Sinkhorn method has the iteration matrix

$M=\operatorname{diag}\left(\frac{1}{a}\right)P_{*}\operatorname{diag}\left(\frac{1}{b}\right)P_{*}^{\mathsf{T}},\qquad\text{where}\quad
P_{*}=\operatorname{diag}(u^{*})K\operatorname{diag}(v^{*}).$ (3)

The local convergence rate equals the second largest eigenvalue

$0\leq\vartheta^{2}<1$

of that matrix; see [8]. Note that $M$ has real and nonnegative eigenvalues
since it is similar to a positive semidefinite matrix, and its largest
eigenvalue equals one (the eigenvector having constant entries), which
accounts for the scaling indeterminacy in the problem formulation. For the
modified method with relaxation, the local rate is also related to
$\vartheta^{2}$, which has been worked out in [13] and is summarized in the
following theorem. For convenience, we provide a brief outline how this result
can be obtained at the end of section 2.

######  Theorem 1 (cf. [13]).

Assume $\vartheta^{2}>0$. For all choices of $0<\omega<2$ the modified
Sinkhorn algorithm (2) is locally convergent in some neighborhood of
$(u^{*},v^{*})$. Its asymptotic (R-linear) convergence rate is

$\rho_{\vartheta}(\omega)\coloneqq\begin{cases}\frac{1}{4}\left(\omega\vartheta+\sqrt{\omega^{2}\vartheta^{2}-4(\omega-1)}\right)^{2},\quad&\text{if
$0<\omega\leq\omega^{\text{opt}}$,}\\\ \omega-1,\quad&\text{if
$\omega^{\text{opt}}\leq\omega<2$},\end{cases}$ (4)

where

$\omega^{\text{opt}}=\frac{2}{1+\sqrt{1-\vartheta^{2}}}>1.$ (5)

It holds $\rho_{\vartheta}(\omega)<1$ for all $0<\omega<2$, and
$\omega^{\text{opt}}$ provides the minimal possible rate (independent of the
starting point) on that interval, namely

$\rho^{\text{\text{opt}}}=\omega^{\text{opt}}-1=\frac{1-\sqrt{1-\vartheta^{2}}}{1+\sqrt{1-\vartheta^{2}}}<\vartheta^{2}.$

By the above theorem, the optimal relaxation parameter $\omega^{\text{opt}}$
is always larger than one (if $\vartheta^{2}>0$). In fact, by the exact
formula (4) for the convergence rate, the range of $\omega$, for which the
modified method is asymptotically strictly faster than the standard Sinkhorn
method, is precisely the interval

$1<\omega<1+\vartheta^{2}.$ (6)

However, the value of $\vartheta^{2}$ depends on the solution and is therefore
not known in advance. To deal with this problem, an adaptive procedure for
choosing $\omega$ is proposed in [13].

As our contribution, the main goal in this note is to provide an a-priori
interval for the relaxation parameter $\omega$ for which the modified
iteration is both globally convergent and locally faster than the standard
Sinkhorn method. In Theorem 3 we first prove global convergence of the
modified method for parameters in the interval
$0<\omega<\frac{2}{1+\Lambda(K)}$. In Theorem 4 we provide an a-priori lower
bound $\vartheta^{2}>\delta_{K,a,b}>1$, which depends only on the data of the
problem, but requires a full rank assumption on $K$. Together with (6) this
yields the following result.

######  Theorem 2.

Assume $\operatorname{rank}(K)=\min(m,n)\geq 2$. For any
$1<\omega<1+\delta_{K,a,b}$ the asymptotic local convergence rate of the
modified Sinkhorn method (2) is faster than for the standard Sinkhorn method.
For $1<\omega<\min\left(\delta_{K,a,b},\frac{2}{1+\Lambda(K)}\right)$ the
modified method is both globally convergent and asymptotically faster than the
standard method.

We remark that our derived a-priori interval for $\omega$ is usually very
small, and hence our result is of rather theoretical interest. In the relevant
cases, when $\vartheta^{2}$ is close to one, significant acceleration is
achieved only when $\omega$ is close to $\omega^{{\text{opt}}}$ (which tends
to two for $\vartheta^{2}\to 1$). A possible heuristic to select a nearly
optimal relaxation is to approximate the second largest eigenvalue of $M$
based on the current iterate. After a similarity transform, this requires to
compute the spectral norm of a symmetric matrix. An even simpler approach, as
suggested in [13], is to directly estimate $\vartheta^{2}$, and hence
$\omega^{{\text{opt}}}$, by monitoring the convergence rate of the standard
Sinkhorn method in terms of a suitable residual. In the final section 4 we
include numerical illustrations, which indicate that in certain cases such
heuristics can be quite precise already in the initial phase of the algorithm,
resulting in the almost optimal convergence rate.

The convergence analysis of the Sinkhorn method is usually carried in a log-
domain formulation [11]. We choose the closely related framework of
compositional data space, e.g., in statistics, see [9], which we think could
be of independent interest in this context. In this space, which is introduced
in the next section, the Sinkhorn algorithm reads as a nonlinear fixed point
iteration for an essentially contractive iteration function, as is known from
the Birkhoff–Hopf theorem. The main results are then presented in Section 3.

##  2 Formulation in compositional data space

The problem (1) as well as the Sinkhorn algorithm and its modified variant
inherit a natural scaling indeterminacy of the variables $u$ and $v$. It can
be therefore formulated in a suitable equivalence space. Here we recast the
algorithm in the framework of what is called _compositional data space_ ; see,
e.g., [9, 1]. To this aim, let

$\mathcal{C}^{m}\coloneqq\mathbb{R}^{m}_{+}/\sim,$

where

$x\sim x^{\prime}\quad:\Longleftrightarrow\quad\exists t>0:\ x=tx^{\prime}.$

The resulting equivalence class of $x$ will be denoted by $\underline{x}$. One
specifies a vector addition and a scalar multiplication on $\mathcal{C}^{m}$
via

$\underline{x}+\underline{y}\coloneqq\underline{x{}\circ{}y},\qquad\gamma\cdot\underline{x}\coloneqq\underline{x^{\gamma}},\quad\gamma\in\mathbb{R},$

where again $x^{\gamma}$ has the components
$(x_{1}^{\gamma},\dots,x_{n}^{\gamma})$. As a result
$(\mathcal{C}^{m},+,\cdot)$ becomes a real vector space of dimension $m-1$. In
this space we consider the so called _Hilbert norm_

$\|\underline{x}\|_{H}\coloneqq\log\max_{i,j}\frac{x_{i}}{x_{j}},$

turning $(\mathcal{C}^{m},{}+{},{}\cdot{},\|\cdot\|_{H})$ into a finite
dimensional Banach space. Note that this norm on the equivalence classes
coincides with the well-known _Hilbert distance_ on the representatives:

$d_{H}(x,y)=\|\underline{x}-\underline{y}\|_{H}.$

Similarly we construct a Banach space
$\mathcal{C}^{n}=\mathbb{R}^{n}_{+}/\sim$.

The modified Sinkhorn algorithm (2) can be interpreted as an iteration in the
space $\mathcal{C}^{m}\times\mathcal{C}^{n}$ and reads

$\displaystyle\underline{u}_{\ell+1}$
$\displaystyle=(1-\omega)\cdot\underline{u}_{\ell}+\omega\cdot\underline{a}-\omega\cdot\mathcal{K}(\underline{v}_{\ell}),$
(7) $\displaystyle\underline{v}_{\ell+1}$
$\displaystyle=(1-\omega)\cdot\underline{v}_{\ell}+\omega\cdot\underline{b}-\omega\cdot\mathcal{K}_{\mathsf{T}}(\underline{u}_{\ell+1}),$

where $\mathcal{K}\colon\mathcal{C}^{n}\to\mathcal{C}^{m}$ and
$\mathcal{K}_{\mathsf{T}}\colon\mathcal{C}^{m}\to\mathcal{C}^{n}$ are now the
_nonlinear_ maps given by

$\mathcal{K}(\underline{v})=\underline{Kv},\qquad\mathcal{K}_{\mathsf{T}}(\underline{u})=\underline{K^{\mathsf{T}}u}.$

The convergence of the standard Sinkhorn algorithm ($\omega=1$) is based on a
famous result of Birkhoff and Hopf on the contractivity of $\mathcal{K}$ and
$\mathcal{K}_{\mathsf{T}}$. To state it, define the quantities

$\eta(K)\coloneqq\max\limits_{i,j,k,\ell}\frac{K_{ik}K_{j\ell}}{K_{jk}K_{i\ell}}\quad\mbox{
and }\quad\Lambda(K)\coloneqq\frac{\sqrt{\eta(K)}-1}{\sqrt{\eta(K)}+1}.$ (8)

Then the following holds; for a proof, see, e.g., [4, Theorems 3.5 & 6.2].

######  Theorem (Birkhoff–Hopf).

For any $K\in\mathbb{R}^{m\times n}_{+}$ and
$v,v^{\prime}\in\mathbb{R}^{n}_{+}$ let $\Lambda(K)$ be defined as above. Then

$\sup_{v,v^{\prime}\in\mathbb{R}^{m}_{+}}\frac{d_{H}(Kv,Kv^{\prime})}{d_{H}(v,v^{\prime})}=\Lambda(K).$

Note that $\Lambda(K)=\Lambda(K^{\mathsf{T}})<1$. As a result, both
$\mathcal{K}$ and $\mathcal{K}_{\mathsf{T}}$ are contractive maps in the
Hilbert norm with Lipschitz constant $\Lambda(K)$, which is also called the
_Birkhoff contraction ratio_ of $K$. Based on this, it is not difficult to
establish the global convergence of the standard Sinkhorn algorithm in the
space $\mathcal{C}^{m}\times\mathcal{C}^{n}$ at a rate $O(\Lambda(K)^{2})$.

It is important to emphasize that studying the convergence in
$\mathcal{C}^{m}\times\mathcal{C}^{n}$, that is, convergence of equivalence
classes, is indeed sufficient for understanding the method in
$\mathbb{R}^{m}_{+}\times\mathbb{R}^{n}_{+}$. Indeed, a pair
$(\underline{u}^{*},\underline{v}^{*})$ is a fixed point of (7) if and only if
for any choice of representatives $(u^{*},v^{*})$ there exist $\lambda,\mu$
such that $\lambda u{}\circ{}Kv=a$ and $\mu v{}\circ{}K^{\mathsf{T}}u=b$. From
$\mathbf{1}_{m}^{\mathsf{T}}a=\mathbf{1}_{n}^{\mathsf{T}}b$ (here $\mathbf{1}$
denotes a vector of all ones) it follows that $\lambda=\mu$, and hence, e.g.
$u^{+}\coloneqq\lambda^{-1/2}u^{*}$ and $v^{+}\coloneqq\lambda^{-1/2}v^{*}$
solve the initial problem (1), where $\lambda=u^{\mathsf{T}}Kv$. Moreover,
choosing representatives $(u_{\ell},v_{\ell})$ of the iterates
$(\underline{u}_{\ell},\underline{v}_{\ell})$ such that
$\mathbf{1}_{m}^{\mathsf{T}}u_{\ell}=\mathbf{1}_{n}^{\mathsf{T}}v_{\ell}=1$,
and setting $u_{\ell}^{+}\coloneqq\lambda_{\ell}^{-\frac{1}{2}}u_{\ell}$,
$v_{\ell}^{+}\coloneqq\lambda_{\ell}^{-\frac{1}{2}}v_{\ell}$ with
$\lambda_{\ell}=u_{\ell}^{\mathsf{T}}Kv_{\ell}$, yields a sequence which
converges exponentially fast to $(u^{*},v^{*})$.

We briefly outline how the local convergence analysis for (7) can be conducted
[13], leading to Theorem 1. By combining both steps of the iteration (7) into
a nonlinear fixed point iteration
$(\underline{u}_{\ell+1},\underline{v}_{\ell+1})=\mathcal{F}(\underline{u}_{\ell},\underline{v}_{\ell})$
in the space $\mathcal{C}^{m}\times\mathcal{C}^{n}$, one finds that its
derivative at the fixed point $(\underline{u}^{*},\underline{v}^{*})$ takes
the form

$M_{\omega}\coloneqq(I_{m+n}-\omega\cdot L)^{-1}[(1-\omega)\cdot
I_{m+n}+\omega\cdot U],$

where

$L=\begin{pmatrix}0&0\\\
-\mathcal{K}_{\mathsf{T}}^{\prime}(\underline{u}^{*})&0\end{pmatrix},\qquad
U=\begin{pmatrix}0&-\mathcal{K}^{\prime}(\underline{v}^{*})\\\
0&0\end{pmatrix}.$

Matrices of the form $M_{\omega}$ are well known as error iteration matrices
of block SOR methods for linear systems. The spectral radius of $M_{\omega}$
can be computed exactly from formula (4), if the spectral radius $\vartheta$
of $L+U$ is known; see [14, Sec. 6.2] or [7, Thm. 4.27]. The eigenvalues of
$L+U$, however, are square roots of the eigenvalues of the composition of
derivatives
$\mathcal{K}^{\prime}(\underline{v}^{*})\mathcal{K}_{\mathsf{T}}^{\prime}(\underline{u}^{*})$,
which is a linear map on $\mathcal{C}^{m}$. It remains to show that the
largest eigenvalue of that operator is precisely the second largest eigenvalue
of the matrix $M$ in (3). Indeed, by elementary calculations, $M$ is the
matrix representation of
$\mathcal{K}^{\prime}(\underline{v}^{*})\mathcal{K}_{\mathsf{T}}^{\prime}(\underline{u}^{*})$
under the isomorphism $u\mapsto\underline{\exp(u)}$ between the subspace
$\\{u\in\mathbb{R}^{m}\colon\mathbf{1}_{m}^{\mathsf{T}}u=0\\}\subseteq\mathbb{R}^{m}$
and $\mathcal{C}^{m}$.

##  3 Main results

We prove the global convergence of the modified method for a range of values
$\omega$ larger than one.

######  Theorem 3.

Let $\Lambda=\Lambda(K)$ be the Birkhoff contraction ratio of $K$. For
$0<\omega<\frac{2}{1+\Lambda}$, the modified Sinkhorn algorithm (7) converges,
for any starting point, to $(\underline{u}^{*},\underline{v}^{*})$
exponentially fast.

###### Proof.

Starting from (7), using the triangle inequality and the contractivity of
$\mathcal{K}$ and $\mathcal{K}_{\mathsf{T}}$ provided by the Birkhoff-Hopf
theorem, we obtain

$\displaystyle\|\underline{u}_{\ell+1}-\underline{u}^{*}\|_{H}$
$\displaystyle\leq\lvert
1-\omega\rvert\,\|\underline{u}_{\ell}-u_{*}\|_{H}+\omega\Lambda\,\|\underline{v}_{\ell}-\underline{v}^{*}\|_{H},$
$\displaystyle\|\underline{v}_{\ell+1}-\underline{v}^{*}\|_{H}$
$\displaystyle\leq\lvert
1-\omega\rvert\|\,\underline{v}_{\ell}-\underline{v}^{*}\|_{H}+\omega\Lambda\,\|\underline{u}_{\ell+1}-\underline{u}^{*}\|_{H}$
$\displaystyle\leq\left(\lvert
1-\omega\rvert+(\omega\Lambda)^{2}\right)\|\,\underline{v}_{\ell}-\underline{v}^{*}\|_{H}+\omega\Lambda\lvert
1-\omega\rvert\,\|\underline{u}_{\ell}-\underline{u}^{*}\|_{H}$

As a consequence, for $\Delta
u_{\ell}\coloneqq\|\underline{u}_{\ell+1}-\underline{u}^{*}\|_{H}$ and $\Delta
v_{\ell}\coloneqq\|\underline{v}_{\ell+1}-\underline{v}^{*}\|_{H}$ we obtain

${\Delta u_{\ell+1}\choose\Delta v_{\ell+1}}\leq T_{\omega}{\Delta
u_{\ell}\choose\Delta v_{\ell}},\qquad\text{ where}\quad
T_{\omega}=\begin{pmatrix}\lvert 1-\omega\rvert&\omega\Lambda\\\
\omega\Lambda\lvert 1-\omega\rvert&\lvert
1-\omega\rvert+(\omega\Lambda)^{2}\end{pmatrix},$

and the vector inequality is understood entry-wise. Since all involved
quantities are non-negative the inequality can be iterated, which gives

${\Delta u_{\ell+1}\choose\Delta v_{\ell+1}}\leq(T_{\omega})^{\ell+1}{\Delta
u_{0}\choose\Delta v_{0}}.$

Hence, to prove exponential convergence it suffices to show that the spectral
radius of $T_{\omega}$ is strictly less than one. Since the spectral radius
equals $\lvert
1-\omega\rvert+\frac{(\omega\Lambda)^{2}}{2}+\sqrt{\frac{(\omega\Lambda)^{4}}{4}+(\omega\Lambda)^{2}\lvert
1-\omega\rvert}$ this is the case iff $\omega<2/(1+\Lambda)$. ∎

Next we provide a lower bound for the second largest eigenvalue
$\vartheta^{2}$ of the matrix $M$ in (3), which by (6) then yields an interval
for $\omega$ such that the modified method has a strictly faster asymptotic
convergence rate than the standard Sinkhorn method.

######  Theorem 4.

Let $\operatorname{rank}(K)=\min(m,n)\geq 2$ and

$\delta_{1}=\frac{a_{\min}}{b_{\max}}\cdot\frac{1-b_{\max}}{\left(\frac{\|K\|_{\infty}}{\sigma_{\min}(K)}\right)^{2}-a_{\min}}>0,\qquad\delta_{2}=\frac{b_{\min}}{a_{\max}}\cdot\frac{1-a_{\max}}{\left(\frac{\|K^{\mathsf{T}}\|_{\infty}}{\sigma_{\min}(K)}\right)^{2}-b_{\min}}>0,$

where $\sigma_{\min}(K)$ is the smallest positive singular value of $K$,
$\|K\|_{\infty}=\max_{\|v\|_{\infty}=1}\|Kv\|_{\infty}$, and the subscripts
$\min$, $\max$ denote the smallest and largest entry of the corresponding
vector. Then it holds

$\vartheta^{2}\geq\delta_{K,a,b}\coloneqq\begin{cases}\delta_{1}&\quad\text{if
$m>n$,}\\\ \delta_{2}&\quad\text{if $m<n$,}\\\
\max(\delta_{1},\delta_{2})&\quad\text{if $m=n$.}\end{cases}$

Note that for a positive matrix $\|K\|_{\infty}>\sigma_{\min}(K)$. Moreover,
$a_{\min}\leq\frac{1}{m}\leq\frac{1}{n}\leq b_{\max}<1$ if $m\geq n$, and vice
versa if $m\leq n$. Hence $\delta_{K,a,b}$ is indeed smaller than one, which
is in line with the bound $\vartheta^{2}\leq\Lambda(K)^{2}$.

###### Proof.

We consider the case $m\geq n$. Instead of matrix $M$ we consider the positive
semidefinite matrix

$H=\operatorname{diag}\left(\frac{u^{*}}{a^{1/2}}\right)K\operatorname{diag}\left(\frac{v^{*}{}\circ{}v^{*}}{b}\right)K^{\mathsf{T}}\operatorname{diag}\left(\frac{u^{*}}{a^{1/2}}\right)\in\mathbb{R}^{m\times
m},$

which is obtained from $M$ by a similarity transformation (and using (1)).
Since the dominant eigenvector of $H$ (with eigenvalue one) is $a^{1/2}$, we
have

$\vartheta^{2}=\max\left\\{\frac{\langle w,Hw\rangle}{\langle
w,w\rangle}\colon\langle w,a^{1/2}\rangle=0\right\\}.$

By projecting on the orthogonal complement of $a^{1/2}$, and noting that
$\|a^{1/2}\|^{2}=1$, we first rewrite this as

$\vartheta^{2}=\max\frac{\langle w,Hw\rangle-\langle
w,a^{1/2}\rangle^{2}}{\langle w,w\rangle-\langle w,a^{1/2}\rangle^{2}},$

where the maximum is taken over all $w$ that are not collinear to $a^{1/2}$.
For such $w$ the nominator is always nonnegative and the denominator is
positive. Next we substitute

$w=a^{-1/2}{}\circ{}Kv^{*}{}\circ{}z$

with a new variable $z$. This yields

$\vartheta^{2}=\max\frac{\langle
K^{\mathsf{T}}z,\frac{v^{*}{}\circ{}v^{*}}{b}{}\circ{}K^{\mathsf{T}}z\rangle-\langle
K^{\mathsf{T}}z,v^{*}\rangle^{2}}{\left\langle
z,\frac{Kv^{*}{}\circ{}Kv^{*}}{a}{}\circ{}z\right\rangle-\langle
K^{\mathsf{T}}z,v^{*}\rangle^{2}},$

where the maximum is taken over all $z$ not collinear with $u^{*}$ (the
nominator is then nonnegative and the denominator is positive). To obtain a
lower bound, we now evaluate the expression at $z$ satisfying

$K^{\mathsf{T}}z=e_{j}$

where $e_{j}$ denotes the $j$-th unit vector. Note that such $z$ exists
($K^{\mathsf{T}}$ has full row rank) and is indeed not collinear to $u^{*}$,
since otherwise $K^{\mathsf{T}}u^{*}$ would be collinear with $e_{j}$, which
contradicts $K^{\mathsf{T}}u^{*}{}\circ{}v^{*}=b$. Therefore, using this $z$,
we get

$\vartheta^{2}\geq\frac{\left(\frac{1}{b_{\max}}-1\right)(v^{*})_{j}^{2}}{\left\langle
z,\frac{Kv^{*}{}\circ{}Kv^{*}}{a}{}\circ{}z\right\rangle-(v^{*})_{j}^{2}}.$

We can choose $j$ as the position of a largest entry of the vector $v^{*}$.
Then in the denominator

$\left\langle
z,\frac{Kv^{*}{}\circ{}Kv^{*}}{a}{}\circ{}z\right\rangle\leq\max_{i}\frac{(Kv^{*})_{i}^{2}}{a_{i}}\|z\|^{2}\leq\frac{\|K\|_{\infty}^{2}(v^{*})_{j}^{2}}{a_{\min}}\frac{1}{\sigma_{\min}(K)^{2}}.$

This leads to the asserted lower bound $\vartheta^{2}\geq\delta_{1}$.

When $m\leq n$, we can simply interchange the roles of $K$ and
$K^{\mathsf{T}}$, $a$ and $b$, as well as $u^{*}$ and $v^{*}$ in this proof to
obtain $\vartheta^{2}\geq\delta_{2}$. ∎

Taken together, Theorem 3 and Theorem 4 result in Theorem 2.

##  4 Numerical illustration

We illustrate the effect of relaxation by two numerical experiments related to
optimal transport. The first is motivated by an application to color transfer
between images [5]. The matrix $K=K_{\varepsilon}$ is generated as

$K_{ij}=\exp\left(-\frac{\|x_{i}-y_{j}\|^{2}}{\varepsilon}\right)$

where $x_{i},y_{j}\in\mathbb{R}^{3}$ are RGB values (scaled to $[0,1]$) of
$m=n=1000$ randomly sampled pixels in two different color images,
respectively. The vectors $a$ and $b$ are chosen as uniform distributions,
i.e. $a=\mathbf{1}_{m}/m$ and $b=\mathbf{1}_{n}/n$. We choose
$\varepsilon=0.01$. In this scenario the standard Sinkhorn method is
reasonably fast, but still can be accelerated using relaxation. A typical
outcome for different relaxation strategies is shown in Fig. 1 left, where we
plot the $\ell_{1}$-distance $\|P_{\ell}-P_{*}\|_{1}$ between the matrices
$P_{\ell}=\operatorname{diag}(u_{\ell})K\operatorname{diag}(v_{\ell})$ and a
numerical reference solution
$P_{*}=\operatorname{diag}(u^{*})K\operatorname{diag}(v^{*})$. Besides the
standard Sinkhorn method ($\omega=1$), we run the method with a fixed
relaxation $\omega=1.5$, and with the ‘optimal’ relaxation
$\omega^{\text{opt}}$, which is computed via formula (5) from the second
largest singular value $\vartheta$ of matrix
$\operatorname{diag}(1/a^{1/2})P_{*}\operatorname{diag}(1/b^{1/2})$ (then
$\vartheta^{2}$ is the second largest eigenvalue of (3)). We do not consider
relaxation based on the lower bound on $\vartheta^{2}$ in Theorem 4, since the
resulting $\omega$ is too close to one.

As can be seen, using $\omega^{\text{opt}}$ significantly accelerates the
convergence speed. Moreover, although $\omega^{\text{opt}}$ only provides the
optimal local rate, the positive effect shows quite immediately. However, the
value of $\omega^{\text{opt}}$ is a priori unknown in practice. Therefore we
also tested a simple heuristic, similar to one suggested in [13]. It is known
that the convergence of the Sinkhorn method can be monitored, e.g., through
the error $\|P_{\ell}\mathbf{1}_{n}-a\|_{1}$; cf. [11, Remark 4.14].
Therefore, since $\vartheta^{2}$ equals the asymptotic convergence rate of the
standard Sinkhorn method, we may take

$\hat{\vartheta}^{2}=\sqrt{\frac{\|P_{\ell}\mathbf{1}_{n}-a\|_{1}}{\|P_{\ell-2}\mathbf{1}_{n}-a\|_{1}}}$

as a current approximation. In the purple curve in Fig. 1 left, we updated
$\omega$ a single time after 20 steps of the standard method based on this
quantity, and using formula (5). This comes at almost no additional cost, but
yields the near optimal rate in this example. Of course such a heuristic could
be applied in a more systematic way, e.g., by monitoring the changes of
$\left(\frac{\|P_{\ell}\mathbf{1}_{n}-a\|_{1}}{\|P_{\ell-p}\mathbf{1}_{n}-a\|_{1}}\right)^{1/p}$
for a suitable value of $p$ over several iterations.

As a second example we consider a 1D transport problem between two random
measures on a uniform grid in $[0,1]$, and with $\ell_{1}$-norm as a cost. The
matrix $K$ in this case is given as

$K_{ij}=\exp\left(-\frac{\lvert\frac{i}{m-1}-\frac{j}{n-1}\rvert}{\varepsilon}\right).$

Again we choose $m=n=1000$ and $\varepsilon=0.01$. As can be seen in Fig. 1
right, this problems seems to be more difficult and the standard Sinkhorn
method is extremely slow. A suitable relaxation compensates this and restores
fast convergence, however, as illustrated by the slow convergence of the red
curve, the estimation of $\omega^{\text{opt}}$, and hence of $\vartheta^{2}$,
needs to be rather precise. Since here the convergence rate of the standard
method stabilizes later, we apply the above heuristic of estimating
$\vartheta^{2}$ after 200 iterations (purple curve). It is also possible to
update $\omega$ earlier using more expensive heuristics. For instance, the
green curve is obtained by computing after 50 iterations of the standard
method an approximation of $\vartheta$ as the second largest singular value of
the matrix
$\operatorname{diag}(1/a^{1/2}_{\ell})P_{\ell}\operatorname{diag}(1/b^{1/2}_{\ell})$,
where $a_{\ell}=u_{\ell}{}\circ{}Kv_{\ell}$ and
$b_{\ell}=v_{\ell}{}\circ{}K^{\mathsf{T}}u_{\ell}$. This could be done
iteratively, we used the Matlab function svds. This results in an almost
optimal convergence rate in this example. Of course, several similar
strategies could be devised.

Figure 1: Effect of different relaxation strategies in two examples.

## References

  * [1] C. Barcelo-Vidal and J.-A. Martin-Fernandez.  The mathematics of compositional analysis.  Aust. J. Stat., 45(4):57–71, 2016.
  * [2] C. Cotar, G. Friesecke, and C. Klüppelberg.  Density functional theory and optimal transportation with Coulomb cost.  Comm. Pure Appl. Math., 66(4):548–599, 2013.
  * [3] M. Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In C. J. C. Burges et al., editors, Advances in Neural Information Processing Systems 26, pages 2292–2300. Curran Associates, Inc., 2013.
  * [4] S. P. Eveson and R. D. Nussbaum.  An elementary proof of the Birkhoff-Hopf theorem.  Math. Proc. Cambridge Philos. Soc., 117(1):31–55, 1995.
  * [5] S. Ferradans, N. Papadakis, G. Peyré, and J.-F. Aujol.  Regularized discrete optimal transport.  SIAM J. Imaging Sci., 7(3):1853–1882, 2014.
  * [6] J. Franklin and J. Lorenz.  On the scaling of multidimensional matrices.  Linear Algebra Appl., 114/115:717–735, 1989.
  * [7] W. Hackbusch.  Iterative solution of large sparse systems of equations.  Springer, [Cham], second edition, 2016.
  * [8] P. A. Knight.  The Sinkhorn-Knopp algorithm: convergence and applications.  SIAM J. Matrix Anal. Appl., 30(1):261–275, 2008.
  * [9] V. Pawlowsky-Glahn, J. J. Egozcue, and R. Tolosana-Delgado.  Modeling and analysis of compositional data.  John Wiley & Sons, Ltd., Chichester, 2015.
  * [10] G. Peyré, L. Chizat, F.-X. Vialard, and J. Solomon.  Quantum entropic regularization of matrix-valued optimal transport.  European J. Appl. Math., 30(6):1079–1102, 2019.
  * [11] G. Peyré and M. Cuturi.  Computational optimal transport.  Found. Trends Mach. Learn., 11(5-6):355–607, 2019.
  * [12] R. Sinkhorn.  Diagonal equivalence to matrices with prescribed row and column sums.  Amer. Math. Monthly, 74:402–405, 1967.
  * [13] A. Thibault, L. Chizat, C. Dossal, and N. Papadakis.  Overrelaxed Sinkhorn-Knopp algorithm for regularized optimal transport.  arXiv 1711.01851, 2017.
  * [14] D. M. Young.  Iterative solution of large linear systems.  Academic Press, New York-London, 1971.