\section{Introduction}
\label{sec:intro}

A \emph{Coxeter group} $W$ is a group generated by a finite set
$S$ subject only to relations $s^2=1$ for $s\in S$ and
$(st)^{m_{st}}=1$ for $s\neq t\in S$, where $m_{st}=m_{ts}\in \{2,3,\ldots,\infty\}$.
Here the convention is that $m_{st}=\infty$ means that we do
not impose a relation between $s$ and $t$. We say that $W$ is
\emph{$2$-dimensional} if for any triple of distinct elements $s,t,r\in S$,
the group $\langle s,t,r\rangle$ is infinite. In other words,
$\frac{1}{m_{st}}+\frac{1}{m_{sr}}+\frac{1}{m_{tr}}\leq 1$.

Consider an arbitrary group $G$ with a finite symmetric generating set
$S$. For $g\in G$, let $\ell(g)$ denote
the \emph{word length} of $g$, that is, the minimal number $n$
such that $g=s_1\cdots s_n$ with $s_i\in S$ for $i=1,\ldots,
n$. Let $S^*$ denote the set of all words over $S$.
If $v\in S^*$ is a word of length $n$, then by $v(i)$ we
denote the prefix of $v$ of length $i$ for $i=1,\ldots, n-1$,
and the word $v$ itself for $i\geq n$. For $1\leq i\leq j\leq
n$ by $v(i,j)$ we denote the subword of $v(j)$ obtained by
removing $v(i-1)$. For a word $v\in S^*$, by $\ell(v)$ we denote
the word length of the group element that $v$ represents.

We say that $G$ is
\emph{biautomatic} if there exists a regular language $\mathcal
L\subset S^*$ (see Section~\ref{sec:regularity} for the definition of regularity) and a constant $C>0$ satisfying the following conditions (see \cite[Lem~2.5.5]{E}).
\begin{enumerate}[(i)]
\item For each $g\in G$, there is a word in $\mathcal L$
    representing $g$.
\item For each $s\in S$ and $g,g'\in G$ with $g'=gs,$ and each $v,v'\in \mathcal L$
    representing $g,g'$, for
    all $i\geq 1$ we have $\ell(v(i)^{-1}v'(i))\leq C$.
\item For each $s\in S$ and $g,g'\in G$ with $g'=sg,$ and each $v,v'\in \mathcal L$
    representing $g,g'$, for
    all $i\geq 1$ we have $\ell(v(i)^{-1}s^{-1}v'(i))\leq C$.
\end{enumerate}

Our paper concerns the two following well-known open questions (see e.g.\ \cite[\S6.6]{FHT}).

\begin{question}
	\label{q:1}
	Are Coxeter groups biautomatic?
\end{question}

\begin{question}
	\label{q:2}
	Are groups acting properly and cocompactly on $2$-dimensional $\mathrm{CAT}(0)$ spaces biautomatic?
\end{question}

All Coxeter groups are known to be automatic (i.e.\ having a regular language satisfying (i) and (ii)) by \cite{BH}.
Biautomaticity has been established only in special cases: \cite{E} (Euclidean and hyperbolic), \cite{NiRe2003} (right-angled),
\cite{Bahls2006} and \cite{CaMu2005} (no Euclidean reflection triangles), \cite{Cap2009} (relatively hyperbolic).
\medskip

Question~\ref{q:2} is widely open. The assumption of $2$-dimensionality is essential, since recently Leary--Minasyan \cite{LeMi} constructed a group acting properly and cocompactly on a $3$-dimensional $\mathrm{CAT}(0)$ space that is not biautomatic. Even in the case of $2$-dimensional buildings, except right-angled and hyperbolic cases, the answer was known
only in particular instances, e.g.\  for many (but not all) proper cocompact actions on Euclidean buildings by \cite{GeSh1}, \cite{GeSh2},
\cite{CaSh1995}, \cite{Nos2000}, and \cite{Sw}.

\smallskip

To define a convenient language, we need the following.
Let $W$ be an arbitrary Coxeter group. For $g\in W$, we denote
by $T(g)\subseteq S$ the set of $s\in S$ satisfying $\ell(gs)<\ell(g)$.
By \cite[Thm~2.16]{R}, the group $\langle T(g)\rangle$ is finite. By $w(g)$ we denote the
longest element in $\langle T(g) \rangle$ (which is unique by \cite[Thm~2.15(iii)]{R}, and consequently it is an involution). Let $\Pi(g)=gw(g)$. By
\cite[Thm~2.16]{R}, we have $\ell(\Pi(g))+\ell(w(g))=\ell(g)$.

We define the \emph{standard language} $\mathcal L\subset S^*$ for $W$ inductively
in the following way. Let $v\in S^*$ be a word of length $n$.
If $v$ represents the identity element of $W$, then $v\in \mathcal L$ if and only if $v$ is the empty word. Otherwise,
let $g\in W$ be the group element represented by $v$ and let $k=\ell(w(g))$. We declare $v\in \mathcal L$ if and
only if $v(n-k)\in \mathcal L$ and $v(n-k+1,n)$ represents $w(g)$. In particular, $v(n-k)$ represents $\Pi(g)$. It follows inductively that $n=\ell(g)$. Such a language is called \emph{geodesic}. Note that the standard language satisfies part~(i) of the definition of biautomaticity.

The paths in $W$ formed by the words in the standard language generalise the normal cube paths for $\mathrm{CAT}(0)$ cube complexes \cite[\S3]{NR} used to prove biautomaticity for right-angled (or, more generally, cocompactly cubulated) Coxeter groups \cite{NiRe2003}. Our main result is the following.

\begin{thm}
\label{thm:main}
If $W$ is a $2$-dimensional Coxeter group, then
it is biautomatic with $\mathcal L$ the standard language.
\end{thm}

Since the standard language is geodesic and preserved by the automorphisms of~$W$ stabilising~$S$, by \cite[Thm~6.7]{Sw} we have the following immediate consequence.

\begin{cor}
\label{cor:buildings}
Let $G$ be a group acting properly and cocompactly on a building of type $W,$ where $W$ is a $2$-dimensional Coxeter group. Then $G$ is biautomatic.
\end{cor}

One element of our proof of Theorem~\ref{thm:main} is:

\begin{thm}
\label{lem:regular}
Let $W$ be a Coxeter group. Then its standard language is
regular.
\end{thm}

In other words, the regularity and part (i) of the definition of biautomaticity are
satisfied for any Coxeter group $W$. However, it is not so
with part (ii). The \emph{$\widetilde A_3$ Euclidean group} is the Coxeter
group with
$S=\{p,r,s,t\}, m_{pr}=m_{rs}=m_{st}=m_{tp}=3,
m_{ps}=m_{rt}=2$.

\begin{thm}
\label{thm:second}
If $W$ is the $\widetilde A_3$ Euclidean group, then its
standard language does not satisfy part (ii) in the definition
of biautomaticity.
\end{thm}

Note, however, that by \cite[Cor~4.2.4]{E}, all Euclidean groups, in particular~$\widetilde A_3$, are biautomatic (with a different language).

\medskip

\noindent \textbf{Organisation.} In Section~\ref{sec:prel} we review the basic properties of Coxeter groups. In Section~\ref{sec:regularity} we prove Theorem~\ref{lem:regular}. For $2$-dimensional $W$, we verify parts~(iii) and~(ii) of the definition of biautomaticity in Sections~\ref{sec:partiii} and~\ref{sec:main}. This completes the proof of Theorem~\ref{thm:main}. We finish with the proof of Theorem~\ref{thm:second} in Section~\ref{sec:dim3}.

\medskip

\noindent \textbf{Acknowledgement.} We thank the referee for many helpful suggestions.

\section{Preliminaries}
\label{sec:prel}

By $X^1$ we denote the \emph{Cayley graph} of $W$, that is, the graph with vertex set $X^0=W$ and with edges joining
each $g\in W$ with $gs$, for $s\in S$. We call such an edge an
\emph{$s$-edge}. We call $gs$ the
\emph{$s$-neighbour} of $g$.

For $r\in W$ a conjugate of an element
of $S$, the \emph{wall} $\mathcal W_r$ of $r$ is the fixed point set of $r$ in $X^1$. We call $r$ the \emph{reflection} in $\mathcal W_r$ (for fixed $\mathcal W_r$ such $r$ is unique). If a midpoint of an edge $e$
belongs to a wall $\mathcal W$, then we say that $\mathcal W$ is \emph{dual} to~$e$ (for fixed~$e$ such a wall is unique).
We say that $g\in W$ is \emph{adjacent} to a wall~$\mathcal W$, if $\mathcal W$ is dual to an edge incident to $g$.
Each wall $\mathcal W$ separates $X^1$ into two components, and
a geodesic edge-path in $X^1$ intersects $\mathcal W$ at most once \cite[Lem~2.5]{R}.

For $T\subseteq S$, each coset $g\langle T\rangle\subseteq X^0$ for $g\in W$
is a \emph{$T$-residue}. A geodesic edge-path in $X^1$ with endpoints in a residue $R$ has all its vertices in $R$ \cite[Lem~2.10]{R}. We say that a wall $\mathcal W$ \emph{intersects}
a residue $R$ if $\mathcal W$ separates some elements of $R$. Equivalently, $\mathcal W$ is dual to an edge
with both endpoints in $R$.

\begin{thm}[{\cite[Thm~2.9]{R}}]
\label{thm:proj}
Let $W$ be a Coxeter group. Any residue $R$ of~$X^0$ contains a unique element $h$ with minimal $\ell(h)$. Moreover, for any $g\in R$ we have $\ell(h)+\ell(h^{-1}g)=\ell(g)$.
\end{thm}

As introduced in Section~\ref{sec:intro}, for $g\in W$ we denote
by $T(g)\subseteq S$ the set of $s\in S$ satisfying $\ell(gs)<\ell(g)$.
Let $R$ be the $T(g)$-residue containing $g$.
By \cite[Thm~2.16]{R}, the group $\langle T(g)\rangle$ is finite and, for $w(g)$ the
longest element in $\langle T(g) \rangle$, the unique element $h\in R$ from Theorem~\ref{thm:proj} is $\Pi(g)=gw(g)$. In particular,
we have $\ell(\Pi(g))+\ell(w(g))=\ell(g)$. Note that if $W$ is $2$-dimensional, then for each $g\in W$ we have $|T(g)|=1$ or $2$. See Figure~\ref{f:f0} for an example where $S=\{s,t,r\}$ with $m_{st}=2, m_{sr}=m_{tr}=4$, and $g=strst$.

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.6]{f0}
\end{center}
\caption{$T(g)=\{ s,t\}$ and $w(g)=st=ts$.}
\label{f:f0}
\end{figure}

For $g\in W$, let $\mathcal W(g)$ be the set of walls $\mathcal W$ in $X^1$ that separate $g$ from the identity element $\mathrm{id}\in W$ and such that there is no wall $\mathcal W'$ separating $g$ from $\mathcal W$.

\begin{rem}
\label{rem:WandR}
Let $g\in W$ and let $R$ be the $T(g)$-residue containing $g$. Since $R$ is finite, all the walls intersecting $R$ belong to $\mathcal W(g)$. However, there might be walls in $\mathcal W(g)$ that do not intersect $R$. See Figure~\ref{f:f0} for an example, where we indicated all three walls of $\mathcal W(g)$ for $g=strst$.
\end{rem}

By the following Parallel Wall Theorem, there exists a bound on the distance in~$X^1$ between $g$ and each of the walls of $\mathcal W(g)$.

\begin{thm}[{\cite[Thm~2.8]{BH}}]
\label{thm:parallel}
Let $W$ be a Coxeter group. There is a constant $Q=Q(W)$ such that for any $g\in W$ and a wall $\mathcal W$ at distance $> Q$ from $g$ in $X^1$, there is a wall $\mathcal W'$ separating $g$ from $\mathcal W$.
\end{thm}

By $X$ we denote the \emph{Cayley complex} of $W$. It is the
piecewise Euclidean $2$-complex with $1$-skeleton $X^1$, all
edges of length $1$, and a regular $2m_{st}$-gon spanned on
each $\{s,t\}$-residue with $m_{st}<\infty$. If $W$ is
$2$-dimensional, then $X$ is $\mathrm{CAT}(0)$, see \cite[\S II.5.4]{BHa} and the link condition in \cite[\S II.5.6]{BHa}. ($X$ coincides then with the `Davis complex' of $W$.)
Walls in $X^1$ extend to (convex) walls in $X,$ which still separate $X$.

We will consider the action of $G$ on $X^0=G$ by left multiplication. This induces obvious actions of $G$ on $X^1, X$ and the set of walls.
\section{Regularity}
\label{sec:regularity}

A \emph{finite state automaton over $S$} (FSA) is a finite directed graph $\Gamma$ with vertex set $V$, edge set $E\subseteq V\times V$, an edge labeling $\phi\colon E\to \mathcal P(S^*)$ (the power set of $S^*$), a distinguished set of \emph{start states} $S_0\subseteq V$, and a distinguished set of \emph{accept states} $F\subseteq V$. A word $v\in S^*$ is \emph{accepted by $\Gamma$} if there exists a decomposition $v=v_0\cdots v_m$ of $v$ into subwords and an edge-path $e_0\cdots e_m$ in $\Gamma$ such that $e_0$ has initial vertex in $S_0$, $e_m$ has terminal vertex in~$F$, and $v_i\in \phi(e_i)$ for each $i=0,\ldots,m$. A subset of $S^*$ is a \emph{regular language} if it is the set of accepted words for some FSA over $S$.

The proof of the regularity of the standard language relies on Theorem~\ref{thm:parallel} and the following lemma.

\begin{lemma}
\label{lem:append}
Let $W$ be a Coxeter group. Let $g\in W$, let $T\subseteq S$ be such that
$\langle T \rangle$ is finite, and let $w$ be the longest
element in $\langle T \rangle$. Then $T(gw)=T$ if and only if
\begin{enumerate}[(i)]
\item
$T$ is disjoint from $T(g)$, and
\item
for each
$t\in S\setminus T$,
the wall dual to $(gw,gwt)$ does not lie in $\mathcal W(g)$.
\end{enumerate}
\end{lemma}

Note that for $g\in W$ and $s\in S$, the wall dual to $(g,gs)$ lies in $\mathcal W(g)$ if and only if it separates $g$ from $\mathrm{id}$. Consequently, condition~(i) could be written equivalently as: for each
$t\in T$, the wall dual to $(g,gt)$ does not lie in $\mathcal W(g)$.

\begin{proof}[Proof of Lemma~\ref{lem:append}]
Suppose first $T(gw)=T$. Then, for $R$ the $T$-residue containing $gw$, by the discussion after Theorem~\ref{thm:proj}, the unique element $h\in R$ with minimal $\ell(h)$ is $g$. Thus for each $t\in T$ we
have $\ell(gt)> \ell(g)$ and so condition~(i) holds.
Furthermore, for $t\in S\setminus T$, the wall~$\mathcal W$
dual to the edge $(gw,gwt)$ does not separate $gw$
from $\mathrm{id}$. Additionally, the wall $\mathcal W$ cannot separate $gw$ from $g$: If it did, then after
conjugating by $(gw)^{-1}$, the reflection in $\mathcal W$ could become simultaneously the generator~$t$ and a word in the elements of $T$, contradicting $t\in S\setminus T$ by \cite[Lem~2.1(ii)]{R}. Thus $\mathcal W$ does not separate $g$ from $\mathrm{id}$, and so condition~(ii) holds.

Conversely, suppose that we have $T\subseteq S$
satisfying conditions~(i) and~(ii).
Then, by condition~(i), for $R$ the $T$-residue containing $g$, we have that the minimal word length element $h\in R$ from Theorem~\ref{thm:proj} coincides with $g$, and so the element of $R$ of maximal word length is $gw$. Consequently, we have $T(gw)\supseteq T$.
Suppose, for a contradiction, that there is
$t\in T(gw)\setminus T$. Then the wall $\mathcal W$
dual to the edge $(gw,gwt)$ separates $gw$ from $\mathrm{id}$. The same argument as in the previous paragraph implies that $\mathcal W$ does not separate $gw$ from~$g$, so it separates $g$ from $\mathrm{id}$. Furthermore, if a wall $\mathcal W'$ separated $\mathcal W$ from $g$, then $\mathcal W'$ would also have to separate $gw$ from $g$, contradicting $\ell(g)+\ell(w)=\ell(gw)$. Consequently, $\mathcal W\in \mathcal W(g)$, which contradicts condition~(ii).
\end{proof}

We now define an FSA $\Gamma$ over $S$ that will accept exactly the standard language.

\begin{defin}
\label{def:reg}
Let $Q$ be the constant from Theorem~\ref{thm:parallel}. For $g\in W$, let $\mathcal U_Q(g)$ be the set of walls in $X^1$ intersecting the closed ball in $X^1$ of radius $Q$ centred at~$g$. By Theorem~\ref{thm:parallel}, we have $\mathcal W(g)\subseteq \mathcal U_Q(g)$.

Consider the set $\hat V$ of pairs of the form $(g, \mathcal U)$, where $g\in W$, and $\mathcal U$ is a subset of $\mathcal U_Q(g)$.
We define an equivalence relation $\sim$ on $\hat V$ by $(g,\mathcal U)\sim (h, \mathcal U')$ if $\mathcal U'=hg^{-1}\mathcal U$. We take the vertices of our FSA $\Gamma$ to be $V=\hat V/\sim$. To lighten the notation, we denote the equivalence class of $(g,\mathcal U)$ by $[g,\mathcal U]$.

In any equivalence class of $\sim$, there is exactly one representative of the form $(\mathrm{id}, \mathcal U)$. Suppose that we have
$T\subseteq S$ such that $\langle T\rangle$ is finite. Let $w$ be the longest element of $\langle T\rangle$. If
\begin{enumerate}[(i)]
\item
for each $t\in T,$ the wall dual to $(\mathrm{id},t)$ lies outside $\mathcal U$, and
\item
for each $t\in S\setminus T,$ the wall dual to $(w,wt)$ lies outside $\mathcal U$,
\end{enumerate}
then we put an edge $e$ in $\Gamma$ from $[\mathrm{id}, \mathcal U]$ to $[w, \mathcal U']$, where
$\mathcal U'$ is defined as the set of walls in $\mathcal U_Q(w)$ that
\begin{enumerate}[(a)]
\item
lie in $\mathcal U$ or intersect the residue $\langle T\rangle$, and
\item
are not separated from $w$ by a wall satisfying~(a).
\end{enumerate}

We let the label~$\phi(e)$ to be the set of all minimal length words representing~$w$.
We let all states be accept states of $\Gamma$ and let the set of start states $S_0$ contain only~$[\mathrm{id}, \emptyset]$.
\end{defin}

\begin{proof}[Proof of Theorem~\ref{lem:regular}]
Let $\Gamma$ be the FSA from Definition~\ref{def:reg}, and let $\mathcal L$ be the standard language.
We argue inductively on $j\geq 0$ that, among the words $v\in S^*$ of length $\leq j$,
\begin{itemize}
\item
$\Gamma$ accepts exactly the words in $\mathcal L$, and
\item
the accept state of each such word $v$ is $[g,\mathcal W(g)],$ where $v$ represents $g$.
\end{itemize}
This is true for $j=0$ by our choice of $S_0$. Now let $n>0$ and suppose that we have verified the inductive hypothesis for all $j<n$. Let $v$ be a word in $S^*$ of length $n$.

Suppose first that $v$ is a word in $\mathcal L$ representing $g\in W$. By the definition of~$\mathcal L$, for $k=\ell(w(g))$, we have $v(n-k)\in \mathcal L$. Moreover, $v(n-k+1,n)$ represents~$w(g)$. By the inductive hypothesis, $\Gamma$ accepts $v(n-k)$. Furthermore, $v(n-k)$ labels some edge-path in $\Gamma$ from $S_0$ to $[\Pi(g),\mathcal W(\Pi(g))]$.
Let $T=T(g)$ and $w=w(g)$. By Lemma~\ref{lem:append}, applied replacing $g$ with~$\Pi(g)$, we have that
\begin{enumerate}[(i)]
\item for each $t\in T$, the wall dual to $(\Pi(g),\Pi(g)t)$ does not lie in $\mathcal W(\Pi(g))$, and
\item for each $t\in S\setminus T,$ the wall dual to $(g,gt)$ does not lie in $\mathcal W(\Pi(g))$.
\end{enumerate}
Thus, translating by $\Pi(g)^{-1}$, we see that $\Gamma$ has an edge from $[\mathrm{id},\Pi(g)^{-1}\mathcal W(\Pi(g))]=[\Pi(g),\mathcal W(\Pi(g))]$ to $[w,\mathcal U']=[g,\Pi(g)\mathcal U']$, labelled by $v(n-k+1,n)$, and so $\Gamma$ accepts~$v$. Furthermore,
by conditions~(a) and~(b) in Definition~\ref{def:reg}, we have that $\Pi(g)\mathcal U'$ consists of walls of $\mathcal U_Q(g)$ that lie in $\mathcal W(\Pi(g))$ or intersect the residue $g\langle T\rangle$ and are not separated from $g$ by any other such wall. Since $\mathcal W(g)\subseteq \mathcal U_Q(g)$, this implies $\Pi(g)\mathcal U'=\mathcal W(g)$.

Conversely, let $v$ be accepted by $\Gamma$ and suppose that $v=v_0\cdots v_m$ as in the definition of an accepted word.
By the inductive hypothesis, the word $v_0\cdots v_{m-1}$ belongs to $\mathcal L$ and represents $g\in W$ such that $e_m$ starts at
$[g,\mathcal W(g)]=[\mathrm{id}, g^{-1}\mathcal W(g)]$. By the definition of the edges, $v_{m}$ represents the longest element~$w$ in some finite~$\langle T \rangle$, and $\mathcal U=g^{-1}\mathcal W(g)$ satisfies conditions~(i) and~(ii) in Definition~\ref{def:reg}.
Translating by $g$, we obtain that $g$ and $T$ satisfy conditions~(i) and~(ii) of Lemma~\ref{lem:append}. Consequently, we have $T=T(gw)$, and so $v$ belongs to~$\mathcal L$.
\end{proof}

\section{$g$ and $sg$}
\label{sec:partiii}
\begin{lemma}
\label{lem:part3}
Let $W$ be a $2$-dimensional Coxeter group. Then its standard language satisfies part (iii) of the definition of biautomaticity.
\end{lemma}

We will need the following.

\begin{sublemma}
\label{sub}
Let $W$ be a $2$-dimensional Coxeter group.
There is a constant $D=D(W)$ such that for any wall $\mathcal W$ adjacent to $\mathrm{id}$, any $f\in W$ adjacent to $\mathcal W$, and any vertices $h,h'\in W$ on geodesic edge-paths from $\mathrm{id}$ to $f$ satisfying $\ell(h)=\ell(h')$, we have $\ell(h^{-1}h')< D$.
\end{sublemma}

\begin{proof}
Let $Q=Q(W)$ be the constant from Theorem~\ref{thm:parallel}. Suppose
that $h,h'\in W$ lie on geodesic edge-paths~$\gamma,\gamma'$ from $\mathrm{id}$ to $f$ and satisfy $\ell(h)=\ell(h')$.
Note that each vertex $g\in W$ of $\gamma$ lies at distance $\leq Q$ from $\mathcal W$ in $X^1$,
since otherwise there would be a wall $\mathcal W'$ separating $g$
from~$\mathcal W$, and so $\mathcal W'$ would intersect $\gamma$
at least twice.

Since $W$ is $2$-dimensional, we have that $X$ is a $\mathrm{CAT}(0)$ space, with path-metric that we denote $|\cdot, \cdot|$,
and the extension of~$\mathcal W$ to $X$ (for which we keep the same notation) is a convex tree. Let $x,y\in \mathcal W$ be the midpoints of the edges dual to $\mathcal W$ incident to $\mathrm{id},f$, respectively. Let $N(\mathcal W)$ be the closed $Q$-neighbourhood of $\mathcal W$ in $X$, w.r.t.\ the $\mathrm{CAT}(0)$ metric. Note that $N(\mathcal W)$ is quasi-isometric to $\mathcal W$, so in particular $N(\mathcal W)$ is Gromov-hyperbolic (for definition, see e.g.\ \cite[III.H.1.1]{BHa}). Moreover, since $X$ and $X^1$ are quasi-isometric, we have that $\gamma\subset N(\mathcal W)$ is a $(\lambda,\epsilon)$-quasigeodesic (for definition, see \cite[I.8.22]{BHa}), where the constants $\lambda,\epsilon$ depend only on $W$. Consequently, by the stability of quasi-geodesics \cite[III.H.1.7]{BHa}, for a constant $C=C(W)$, there is a point $z$ on the geodesic from $x$ to $y$ with $|h,z|\leq C$. Analogously, there is a vertex $h''$ on $\gamma'$ with $|z,h''|\leq C$, and so $|h,h''|\leq 2C$.

Thus, since $X$ and $X^1$ are quasi-isometric, there is a constant $D=D(W)$ with $\ell(h^{-1}h'')< \frac{D}{2}$. By the triangle inequality in $X^1$, we have $|\ell(h)-\ell(h'')|< \frac{D}{2}$. Thus, by $\ell(h)=\ell(h')$, the distances on $\gamma'$ from $h''$ and $h'$ to $\mathrm{id}$ differ by less than $\frac{D}{2}$. Consequently,
we have $\ell(h''^{-1}h')< \frac{D}{2}$, and so $\ell(h^{-1}h')< D$, as desired.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:part3}] Let $\mathcal L$ be the standard language. Let $D$ be the constant from Sublemma~\ref{sub}. Let $K$ be the maximal word length of the longest element of a finite
$\langle T\rangle$ over all $T\subseteq S$, and let $C=\max\{K,D\}$.

We prove part~(iii) of the definition of biautomaticity
inductively on $\ell(g)$, where we assume without loss of generality
$\ell(sg)>\ell(g)$. If $g=\mathrm{id}$, then there is nothing to prove.
Suppose now $g\neq \mathrm{id}$, and let $\mathcal W$ be the wall in $X^1$ dual to the $s$-edge incident to $\mathrm{id}$. Let $v,v'\in \mathcal L$ represent $g,sg,$ respectively.

Assume first that $g$ is not adjacent to $\mathcal W$. Let $\mathcal W'$ be a wall adjacent to $g$ separating $g$ from $\mathrm{id}$. Then $\mathcal W'$
also separates $g$ from~$s$. Consequently, $s\mathcal W'$
separates $sg$ from $\mathrm{id}$. Conversely, if a wall $\mathcal W'$ is adjacent to $sg$ and separates $sg$ from $\mathrm{id}$, then it also
separates $sg$ from $s$, and so $s\mathcal W'$ separates $g$ from $\mathrm{id}$. Consequently,
$T(sg)=T(g)$ and so $w(g)=w(sg)$, hence $\Pi(sg)=s\Pi(g)$. In
other words, for $k=\ell(w(g))$, the
words $v'(\ell(sg)-k)$ and $sv(\ell(g)-k)$ represent the same element $s\Pi(g)$ of $W$. Then
part (iii) of the definition of biautomaticity for $g$ follows inductively
from part~(iii) for $\Pi(g)$, for $i< \ell(sg)-k$, or from the definition of $K$, for $i\geq \ell(sg)-k$.

Secondly, assume that $g$ is adjacent to $\mathcal W$. Then $(g,sg)$ is an edge of
$X^1$. Let $f=sg$ and for $0\leq i\leq \ell(g)$ let $h,h'$ be the elements of $W$
represented by $sv(i)$ and $v'(i+1)$. Then, by the definition of
$D$, we have $\ell(v(i)^{-1}sv'(i+1))<D$, as desired.
\end{proof}

\section{$g$ and $gs$}
\label{sec:main}

For $g\in W$ and $k\geq 0$, we set $\Pi^k(g)=\overbrace{\Pi\circ
\cdots \circ\Pi}^{k}(g)$. The main result of this section is the following.

\begin{prop}
\label{prop:main}
Let $W$ be a $2$-dimensional Coxeter group.
Let $g,g'\in W$ be such that $g'\in g \langle s,t \rangle$ for
some $s,t\in S$ with $m_{st}<\infty$ (possibly $s=t$). Then there are $0\leq k,k'\leq 3$ with
$k+k'>0$, such that $\Pi^{k'}(g')\in \Pi^k(g)\langle p,r\rangle$
for some $p,r\in S$ with $m_{pr}<\infty$ (possibly $p=r$).
\end{prop}

We obtain the following consequence, which together with Theorem~\ref{lem:regular} and Lemma~\ref{lem:part3} completes the proof of Theorem~\ref{thm:main}.

\begin{cor}
\label{cor:fellow_travel}
Let $W$ be a $2$-dimensional Coxeter group. Then its standard language satisfies part (ii) of the definition of
biautomaticity.
\end{cor}
\begin{proof}
As before, let $K$ be the maximal word length of the longest element of a finite
$\langle T\rangle$ over all $T\subseteq S$. Assume without loss of generality
$\ell(gs)>\ell(g)$.

Let $0\leq i\leq \ell(g)$. By Proposition~\ref{prop:main}, there is $0\leq j\leq \ell(g)$ with $|j-i|\leq \frac{3K}{2}$ and $0\leq i'\leq \ell(g)+1$ such that $v(j)$ and $v'(i')$ represent elements of $W$ in a common finite residue. Consequently, we have $\ell\big(v(j)^{-1}v'(i')\big)\leq K,$ and so in particular $|j-i'|\leq K$. Therefore $\ell\big(v(i)^{-1}v'(i)\big)\leq |i-j|+\ell\big(v(j)^{-1}v'(i')\big)+|i'-i|\leq 5K$.
\end{proof}

In the proof of Proposition~\ref{prop:main} we will use the following \emph{truncated piecewise Euclidean structure}
on the barycentric subdivision $X'$ of the Cayley complex $X$ of~ $W$. Consider the function $q\colon\mathbf{N}_{\geq 2}\to \mathbf{N}_{\geq 2}$, defined as

\[q(m)=\begin{cases}
m, & \text{for } m=2,3, \\
4, & \text{for } m=4,5, \\
    6, & \text{for } m\geq 6.
\end{cases}
\]

Note that each triangle $\sigma$ of $X'$ is a triangle in the barycentric subdivision of a
regular $2m$-gon of $X$ spanned on an $\{s,t\}$-residue with $m_{st}=m<\infty$. Consequently, in the usual piecewise Euclidean structure, $\sigma$ has angles $\frac{\pi}{2m},\frac{\pi}{2},\big(1-\frac{1}{m}\big)\frac{\pi}{2}$. Moreover, the edge opposite to $\frac{\pi}{2m}$ is half of the edge of $X^1$, so it has length $\frac{1}{2}$. In the truncated piecewise Euclidean structure, we choose a different metric on $\sigma$, namely that of a triangle in the barycentric subdivision of
a regular $2q(m)$-gon. More precisely, the angles of $\sigma$ are $\frac{\pi}{2q(m)},\frac{\pi}{2},\big(1-\frac{1}{q(m)}\big)\frac{\pi}{2}$, while the length of the edge opposite to $\frac{\pi}{2q(m)}$ is still $\frac{1}{2}$.

In the following, let $v$ be a vertex of $X'$. The \emph{link} of $v$ in $X'$ is the metric graph whose vertices correspond to the edges of $X'$ incident to $v$. Vertices of the link corresponding to edges $e_1,e_2$ of $X'$ are connected by an edge of length $\theta$, if $e_1$ and~$e_2$ lie in a common triangle $\sigma$ of $X'$ and form angle $\theta$ in $\sigma$. A \emph{loop} in the link is a locally embedded closed edge-path.

\begin{lemma}
\label{lem:truncated}
The truncated piecewise Euclidean structure satisfies the \emph{link condition}, i.e.\ each loop in the link of a vertex $v$ of $X'$ has length $\geq 2\pi$.
\end{lemma}

\begin{proof}[Proof of Lemma~\ref{lem:truncated}] If $v$ is the barycentre on an edge of $X$, then its link is a simple bipartite graph all of whose edges have length $\frac{\pi}{2}$. Hence its loops have length $\geq 4\frac{\pi}{2}=2\pi$.
If $v$ is the barycentre of a polygon of $X$, then its link is a circle that had length $2\pi$ in the usual piecewise Euclidean structure.
The angles at the barycentre of a polygon in the truncated Euclidean structure are at least as large as the angles in the usual piecewise Euclidean structure, and consequently in the truncated Euclidean structure the link has length $\geq 2\pi$.

It remains to consider a vertex $v\in X^0$, and its link $L'$ in $X'$. For each triangle~$\sigma$ of $X'$ incident to $v$ there is exactly one other triangle $\tau$ of $X'$ incident to $v$ with common hypothenuse, and they lie in the same polygon of $X$. Let $L$ be the graph obtained from $L'$ by merging into one edge each pair of edges corresponding to such $\sigma$ and~$\tau$.
Note that $L$ is isometric to $L'$.
The graph $L$ has a vertex corresponding to each $s\in S$ and an edge of length $\big(1-\frac{1}{q(m_{st})}\big)\pi\geq \frac{\pi}{2}$ joining the vertices corresponding to $s,t$, for each $s,t\in S$ with $m_{st}<\infty$. In particular, all the loops in $L$ of combinatorial length $\geq 4$ have metric length $\geq 2\pi$. To obtain the same for loops in $L$ of combinatorial length $3$, we need to verify that for each triple of distinct $s,t,r\in S$, we have
\begin{equation*}
    \frac{1}{q(m_{st})}+\frac{1}{q(m_{tr})}+\frac{1}{q(m_{sr})}\leq 1.\tag{$*$}
\end{equation*}

If $q(m_{st}),q(m_{tr}), q(m_{sr})\neq 2$, then ($*$) holds. If $q(m_{st}),q(m_{tr})\neq 2$ and $q(m_{sr})=2$, then $m_{st},m_{tr}\neq 2$ and $m_{sr}=2$. Since $W$ is $2$-dimensional, we have $m_{st},m_{tr}\geq 4$ or $m_{st}\geq 6$ or $m_{tr}\geq 6$. We then have, respectively, $q(m_{st}),q(m_{tr})\geq 4$ or $q(m_{st})\geq 6$ or $q(m_{tr})\geq 6$, and so ($*$) holds in this case as well. Finally,
if $q(m_{st})=q(m_{sr})=2$, then $m_{st}=m_{sr}=2$, contradicting the $2$-dimensionality of $W$.
\end{proof}

Below, for two edges $e_1,e_2$ incident to a vertex $v$ of $X'$, by their \emph{angle} at $v$ we mean the distance in the link of $v$ between the vertices that $e_1,e_2$ correspond to. Since $X'$ satisfies the link condition, this is the same as the Alexandrov angle if the latter is $<\pi$.

\begin{lemma}
\label{lem:angles}
Let $W$ be a $2$-dimensional Coxeter group.
Let $\gamma, \gamma'$ be geodesic edge-paths in $X^1$
with common endpoints. Suppose that there are walls $\mathcal W_i$ in $X$ with $i=1,2,3,$ such that
$\gamma$ intersects them in the opposite order to $\gamma'$, and that $\mathcal W_2$ is the middle one in
both of these orders. For $i=1,3,$ let $\theta_i$ be the angle in the truncated structure at $x_i=\mathcal W_2\cap\mathcal W_i$
formed by the segments in $\mathcal W_2, \mathcal W_i$ from $x_i$ to $\gamma\cap \mathcal W_2$ and $\gamma\cap\mathcal W_i$.
Then $\theta_1+\theta_3<\pi$.
\end{lemma}

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.63]{f1}
	\end{center}
	\caption{Lemma~\ref{lem:angles}}\label{f:f1}
\end{figure}

See Figure~\ref{f:f1} for an illustration. Note that in the definition of either $\theta_i$ we could replace $\gamma$ by $\gamma'$.

In the proof we will need the following terminology. A \emph{combinatorial $2$-complex} is a $2$-dimensional CW complex in which the attaching maps of $2$-cells are closed edge-paths. For example, the Cayley complex $X$ of a Coxeter group is a combinatorial 2-complex. A \emph{disc diagram} $D$ is a compact contractible combinatorial 2-complex with a fixed embedding in $\mathbf{R}^2$. Its \emph{boundary path} is the attaching map of
the cell at $\infty$. If $X$ is a combinatorial 2-complex, \emph{a disc diagram in $X$} is a cellular map $\varphi \colon D\to X$ that is \emph{combinatorial}, i.e.\ its restriction to each cell of $D$ is a homeomorphism onto a cell of $X$.
The \emph{boundary path} of a disc diagram $\varphi \colon D\to X$ is the composition of the boundary path of $D$ and $\varphi$. We say that $\varphi$ is \emph{reduced}, if it is locally injective on $D-D^0$.

\begin{proof}[Proof of Lemma~\ref{lem:angles}]
Let $\varphi \colon D\to X$ be a reduced disc diagram in $X$ with boundary
$\gamma^{-1}\gamma'$ (for the existence of $\varphi$, see for example \cite[\S V.1--2]{LS}).
Consider the piecewise Euclidean structure on the barycentric subdivision $D'$ of $D$ that is the pullback under $\varphi$ of the truncated Euclidean structure on $X'$. By Lemma~\ref{lem:truncated} and \cite[II.5.4]{BH}, the induced path-metric on $D$ is $\mathrm{CAT}(0)$. Furthermore, for each wall $\mathcal W$ in $X$, the preimage $\varphi^{-1}(\mathcal W)$ is a geodesic in $D$.
Thus $D$ contains a geodesic triangle formed by the segments of  $\varphi^{-1}(\mathcal W_i)$ joining their three intersection points.
Its angles indicated in Figure~\ref{f:f1} equal $\theta_1,\theta_3$. Since the Alexandrov angles of that triangle do not exceed the angles of the comparison triangle in the Euclidean plane \cite[II.1.7(4)]{BHa}, we have $\theta_1+\theta_3<\pi$.
\end{proof}

\begin{cor}
\label{cor:step1}
Let $W$ be a $2$-dimensional Coxeter group.
Let $f\in W$ with $T(f)=\{s,t\}$, with $s\neq t$.
Let $h=\Pi(f)$ and let $R$ be the $\{s,t\}$-residue containing $f$ and $h$.
Let $g\in R$ and let $m$ be the distance in $X^1$ between $g$ and $h$. Suppose $T(g)=\{s,r\}$ with $r\neq s,t$.
Then:
\begin{enumerate}[(i)]
\item $m\leq 3$.
\item If $m=3$, then $m_{sr}=2$.
\item If $m_{st}=3$ and $m=2$, then $m_{sr}=2$.
\item If $m_{st}=4$, then $m\leq 2$.
\item If $m=m_{st}-1$, then $m_{st}\leq 3$, and for $m_{st}=3$ we have $m_{sr}=2$.
\end{enumerate}
\end{cor}

\begin{proof} Note that $T(g)=\{s,r\}$ implies in particular
$g\neq f,h$. Let $\gamma_0$ be the geodesic edge-path in $X^1$ from $f$ to $h$ not containing $g$. Let $\gamma_1$ be
the geodesic edge-path of length $m_{sr}$ with vertices in the $\{s,r\}$-residue containing $g$, starting at $g$ with the $r$-edge. Let $\gamma$ be any
geodesic edge-path from $f$ to $\mathrm{id}$ containing $\gamma_0$. Let $\gamma'$ be any geodesic edge-path from $f$ to $\mathrm{id}$ containing $\gamma_1$.
Let $\mathcal W_1$ be the first wall intersecting~$\gamma$. Let $\mathcal W_2$ be the wall dual to the $s$-edge incident to $g$.
Let $\mathcal W_3$ be the wall dual to the $r$-edge incident to $g$. See Figure~\ref{fig:corollary}. Note that $\mathcal W_3$ does not
intersect $R$ (since then $\mathcal W_2$ and $\mathcal W_3$ would intersect twice in $X$) and, analogously, $\mathcal W_1$ does
not intersect the $\{s,r\}$-residue of $g$. Consequently, we are in the setup of Lemma~\ref{lem:angles} and we let $\theta_1,\theta_3$ be as in that lemma, so that $\theta_1+\theta_3<\pi$.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.6]{f2}
	\end{center}
	\caption{Corollary~\ref{cor:step1}}\label{fig:corollary}
\end{figure}

Observe that we have $\theta_1=(m-1)\frac{\pi}{q(m_{st})}$ and $\theta_3=(m_{sr}-1)\frac{\pi}{q(m_{sr})}$.

To prove part (i), assume $m\geq 4$. We then have $\theta_1\geq \frac{\pi}{2}$. However, $\theta_3\geq \frac{\pi}{2}$, which
contradicts Lemma~\ref{lem:angles}.

For part (ii), if $m=3$ then we only have $\theta_1\geq \frac{\pi}{3}$. However, assuming $m_{sr}\geq 3$, we would have $\theta_3\geq \frac{2\pi}{3}$,
which also contradicts Lemma~\ref{lem:angles}.

For part (iii), if $m=2$ and $m_{st}=3$, then we have $\theta_1=
\frac{\pi}{3}$. Assuming $m_{sr}\geq 3$, we would have $\theta_3\geq \frac{2\pi}{3}$ as before,
which contradicts Lemma~\ref{lem:angles}.

To prove part (iv), if we had $m_{st}=4$ and $m\geq 3$, then $\theta_1\geq \frac{\pi}{2}$ and $\theta_3\geq
\frac{\pi}{2}$ would
also contradict Lemma~\ref{lem:angles}.

For part (v), assume $m=m_{st}-1$. The case $m_{st}\geq 5$ is excluded by part (i), and the case $m_{st}=4$ is excluded by part (iv). For $m_{st}=3$ we
have $m_{sr}=2$ by part (iii).
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop:main}]
If $s=t$, then without loss of generality $s\in T(g)$, and we
can take $k=1, k'=0$.

Assume now $s\neq t$. Let $R=g \langle s,t \rangle$, and let $f,h\in R$ be the elements
with maximal and minimal word length, respectively.
Let $m,m'$ be the distances in~$X^1$ between $h$ and
$g,g'$, respectively. We can assume $\Pi(g),\Pi(g')\notin R$. Then in
particular $m,m'\neq m_{st}$ and if $m\neq 0$ we have
$|T(g)|=2$ and $T(g)$ contains exactly one of $s,t$. Without loss of generality we suppose then
$T(g)=\{s,r\}$ for some $r\neq s,t$.

Note that from Corollary~\ref{cor:step1}(i) it follows that $m\leq 3$. Furthermore, by Corollary~\ref{cor:step1}(ii) if
$m=3$, then $m_{sr}=2$. An analogous statement holds for $m'$.

\smallskip

\noindent \textbf {Case 1: $m=3$, or $m=2$ and $m_{sr}\geq 3$.}

If $m=3$, then denoting by $\hat g$ the $s$-neighbour of $g$, we have $T(\hat g)=\{t,r\}$. Since $m_{sr}=2$, we have $m_{tr}\geq 3$.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.57]{f3}
	\end{center}
	\caption{Proof of Proposition~\ref{prop:main}, Case 1.}\label{fig:step2}
\end{figure}

Applying Corollary~\ref{cor:step1}(v), with $f$ replaced by $\hat g$ and $g$ replaced by the $t$-neighbour of $\hat g$, gives $m_{tr}=3$, and so $m_{st}\geq 6$.
Consequently, in $X^1$ we have the configuration described in Figure~\ref{fig:step2}(a),
where for each edge $(q,\hat q)$ of $X^1$ the vertex $q$ is drawn higher than $\hat q$ if $\ell(q)>\ell(\hat q)$.
For each edge-path in $X^1$ labelled $sr,rs,$ or $trt$, with endpoints $q,\hat q$ satisfying $\ell(q)-\ell(\hat q)=2$ or $3$, respectively, there is another edge-path from $q$ to $\hat q$ labelled $rs,sr,$ or $rtr$, respectively. The word lengths of the consecutive vertices of such a path
are $\ell(q),\ell(q)-1,\ell(q)-2=\ell(\hat q),$ or $\ell(q),\ell(q)-1,\ell(q)-2,\ell(q)-3=\ell(\hat q),$ respectively.
Thus the configuration described in Figure~\ref{fig:step2}(a) extends to the configuration in Figure~\ref{fig:step2}(b). In particular, we have $m'\neq 3$,
since otherwise, for $r'\in S$ satisfying $T(g')=\{t,r'\}$, denoting by $\hat{g}'$ the $t$-neighbour of~$g'$, we have $T(\hat{g}')=\{s,r'\}$ and so $r'=r$. Since $m_{tr'}=2$, we have $3\leq m_{sr'}=m_{sr}$, which is a contradiction. Consequently, $m'\leq 2$.

Consider any of the two vertices labelled by $u$ in Figure~\ref{fig:step2}(b). Note that $T(u)=\{t\}$,
since having $|T(u)|=2$ would force the $t$-neighbour $\hat u$ of $u$ to have $|T(\hat u)|\geq 3$.
This implies that $\Pi^3(g)$ lies on the lower $\{s,t\}$-residue $R'$ in Figure~\ref{fig:step2}(b).
Furthermore, note that $T(h)=\{r\}$, since having $T(h)=\{r,p\}$ for some $p\in S$
would force the $r$-neighbour $\hat h$ of $h$ to have $T(\hat
h)=\{t,p\}$, contradicting Corollary~\ref{cor:step1}(v) with $g$ replaced by $\hat
h$, and $f$ replaced by the $s$-neighbour of $\hat h$, since it would imply $m_{st}\leq 3$.
Consequently, in any of the cases $m'=0,1,2$, there is
$k'\leq 3$ with $\Pi^{k'}(g')\in R'$, as desired.

If $m=2$ and $m_{sr}\geq 3$, then the same proof goes through with
the following minor changes. Namely, $m_{sr}=3$ and $m_{tr}=2$ follow from Corollary~\ref{cor:step1}(v)
applied with $f$ replaced by $g$ and $g$ replaced by the $s$-neighbour of $g$. The remaining part of the
proof is the same, with $s$ and $t$ interchanged, except that it is $\Pi(g)$ instead of $\Pi^3(g)$ that lies in $R'$.
Namely, in $X^1$ we have the configuration described in Figure~\ref{fig:step2}(a), with the top square removed, $s$ and $t$ interchanged, and $\hat g$ replaced with $g$. Consequently, we have the configuration described in Figure~\ref{fig:step2}(b), with the same modifications. We obtain $k'\leq 3$ with $\Pi^{k'}(g')\in R'$ as before.

\smallskip

\noindent \textbf {Case 2: $m=2$ and $m_{sr}=2$.}

We have $m_{tr}\geq 3$ and the configuration from Figure~\ref{fig:step3} inside $X^1$. Note that if $m'=2$, then we can assume $T(g')=\{t\}$. Indeed, if $T(g')=\{t,p\}$, then we can assume $m_{tp}=2$ since otherwise interchanging $g,g'$ we can appeal to Case~1. Thus $p\neq r$, and so the $t$-neighbor $\hat {g}'$ of $g'$ has $|T(\hat {g}')|\geq 3$, which is a contradiction.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.57]{f4}
	\end{center}
	\caption{Proof of Proposition~\ref{prop:main}, Case 2.}\label{fig:step3}
\end{figure}

Consequently both $\Pi(g)$ and $\Pi^{k'}(g')$ for some $k'\leq 2$ lie in the $\{t,r\}$-residue $R'$ from Figure~\ref{fig:step3}. This completes Case~2.

\smallskip

Note that if, say, $m=1,m'=0$, then we can take $k=1,k'=0.$
Thus it remains to consider the case where $m'=m=1$.

\smallskip

\noindent \textbf {Case 3: $m'=m=1$, and $T(g')=\{t,r\}.$} In other words, the second element of $T(g')$ coincides with that of $T(g)$.

If one of $m_{sr},m_{tr}$, say $m_{sr}$, equals $2$, then we can take $k=1,k'=0$, and we are done. If $m_{sr}=m_{tr}=3$, then we can take $k=k'=1$. It remains to consider the case, where, say, $m_{sr}\geq 4, m_{tr}\geq 3$.
Let $\gamma_0,\gamma_0'$ be the geodesic edge-paths from $f$ to $g,g'$, respectively.
If $m_{tr}\geq 4$, then we apply Lemma~\ref{lem:angles} with any $\gamma$ starting with $\gamma_0\overbrace
{rsr\cdots}^{m_{sr}}$, and any $\gamma'$ starting with $\gamma'_0\overbrace
{rtr\cdots}^{m_{tr}}$. We take $\mathcal W_1,\mathcal W_2,\mathcal W_3$ to be the walls dual to $r$-edges incident to $g,h,g',$ respectively. Then $\theta_1,\theta_3\geq \frac{\pi}{2}$, which is a contradiction. Analogously, if $m_{sr}\geq 6$, then $\theta_1\geq \frac{2\pi}{3},\theta_3\geq \frac{\pi}{3}$, contradiction.

We can thus assume $m_{tr}= 3,$ and $m_{sr}=4$ or $5$. In particular, $m_{st}\geq 3$. We now apply Corollary~\ref{cor:step1}, with $f$ replaced by
the $r$-neighbour $u$ of $h$ and $g$ replaced by the $s$-neighbour $\hat u$ of $u$, see Figure~\ref{fig:case3}. Since $T(u)=\{s,t\}$ with $m_{st}\geq 3$ and $T(\hat u)=\{t,r\}$ with $m_{tr}= 3$, Corollary~\ref{cor:step1}(v) yields a contradiction.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.57]{f5}
	\end{center}
	\caption{Proof of Proposition~\ref{prop:main}, Case 3.}\label{fig:case3}
\end{figure}

\smallskip

\noindent \textbf {Case 4: $m'=m=1$, and $T(g')=\{t,p\}$ for some $p\neq r$.}

First note that $T(h)=\{r,p\}$ and so $m_{pr}<\infty$. If $m_{sr}=m_{tp}=2$, then we can take $k'=k=1$ and we are done. We now focus on the case $m_{sr}\geq 3$ and $m_{tp}\geq 3$.
By Corollary~\ref{cor:step1}(v), applied with $f$ replaced by~$g$ and $g$ replaced by $h$, we obtain $m_{sr}=3$ and $m_{rp}=2$. In particular, since $m_{tp}<\infty$,  we have $m_{tr}\geq 3$.
Let $\hat h$ be the $p$-neighbour of~$h$. We then apply Lemma~\ref{lem:angles} to geodesic edge-paths $\gamma,\gamma'$ from $g$ to $\mathrm{id}$, where $\gamma$ starts with the edge-path of length $m_{sr}$ in the $\{s,r\}$-residue of $g$ starting with the $r$-edge, and $\gamma'$ starts with the $s$-edge, the $p$-edge, followed by the edge-path of length $m_{tr}$ in the $\{t,r\}$ residue of $\hat h$ starting with the $t$-edge. See Figure~\ref{fig:case4}. We consider the walls $\mathcal W_1, \mathcal W_2$ dual to the $r$-edges incident to $g,h$, respectively, and $\mathcal W_3$ dual to the $t$-edge incident to $\hat h$. We have $\theta_1= \frac{\pi}{3}, \theta_3\geq \frac{2\pi}{3}$, which is a contradiction.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.6]{f6}
	\end{center}
	\caption{Proof of Proposition~\ref{prop:main}, Case 4, $m_{sr}\geq 3$ and $m_{tp}\geq 3$.}\label{fig:case4}
\end{figure}

It remains to consider the case where, say, $m_{sr}\geq 3$ and $m_{tp}=2$. Then again by Corollary~\ref{cor:step1}(v), applied with $f$ replaced by $g$ and $g$ replaced by $h$, we obtain $m_{sr}=3$ and $m_{rp}=2$. Let $u$ be the $r$-neighbour of~$h$. Then $\Pi(g)$ lies in the $\{p,s\}$-residue $R'$ of $u$. Let $\hat h=\Pi(g')$, and let $\hat u$ be the $p$-neighbour of $u$, see Figure~\ref{fig:lastcase}. We have $m_{sp}\geq 6$ and so by Corollary~\ref{cor:step1}(v), applied with $f$ replaced by $u$ and $g$ replaced by $\hat u$, we obtain $T(\hat u)=\{s\}$. We claim that $T(\hat h)=\{r\}$ and so $\Pi(\hat h)$ also lies in $R'$, finishing the proof. To justify the claim, suppose $T(\hat h)=\{r,q\}$ with $q\neq r$. If $m_{rq}\geq 3$, then
we consider the walls $\mathcal W_1, \mathcal W_2$ dual to the $r$-edges incident to $g,h$, respectively, and $\mathcal W_3$ dual to the $q$-edge incident to $\hat h$, which leads to a contradiction as in the previous paragraph. If $m_{rq}=2$, then $q\neq s$ and so $T(\hat u)=\{s,q\}$, which is a contradiction.
This justifies the claim and completes Case~4.
\end{proof}

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.63]{f7}
	\end{center}
	\caption{Proof of Proposition~\ref{prop:main}, Case 4, $m_{sr}\geq 3$ and $m_{tp}=2$.}\label{fig:lastcase}
\end{figure}

\section{$\widetilde A_3$ Euclidean group}
\label{sec:dim3}

In this section it will be convenient to view the Cayley graph $X^1$ of the $\widetilde A_3$ Coxeter group $W$ as the dual graph to its Coxeter complex, which is the following subdivision of $\mathbf{R}^3$. (The reader might find it convenient to relate this subdivision intro tetrahedra with the standard subdivision of $\mathbf{R}^3$ into unit cubes.) Its vertices are triples of integers $(x,y,z)$ that are all odd or all even. Edges connect each vertex $(x,y,z)$ to vertices of the form $(x\pm 2,y,z),(x,y\pm 2,z),(x,y,z\pm 2),(x\pm 1,y\pm 1,z\pm 1)$, where the three signs can be chosen independently. See for example \cite[Thm~A]{Munro}, where this Coxeter complex is described as a subdivision of the hyperplane $\sigma$ in $\mathbf{R}^4$ defined by $x_1+x_2+x_3+x_4=0$, and the linear isomorphism with our subdivision of $\mathbf{R}^3$ is given by $(x,y,z)\mapsto (x+y+z,x-y-z, y-z-x, z-x-y)$. Furthermore, in Step~1 of the proof of \cite[Thm~A]{Munro}, we show that the tetrahedra of the Coxeter complex are obtained by subdividing $\sigma$ along a family of hyperplanes that, after identifying $\sigma$ with $\mathbf{R}^3,$ have equations $x\pm y=c, x\pm z=c,$ or $ y\pm z=c$, for $c$ even.

In particular, in the second paragraph of Step~1 of the proof of \cite[Thm~A]{Munro}, we describe explicitly one of the tetrahedra as, after identifying $\sigma$ with $\mathbf{R}^3$, spanned on the clique with vertices
$(-1,-1,-1),(-1,-1,1),(-2,0,0),(0,0,0)$. Using the action of $W$, this gives the following description of all the tetrahedra of our subdivision.
Namely, tetrahedra are spanned (up to permuting the coordinates) on cliques with vertices $(x,y,z-1),(x,y,z+1),(x+1,y-1,z),(x+1,y+1,z)$.
Each such tetrahedron has exactly two edges of length $2$, and the segment $e=((x,y,z),(x+1,y,z))$ joining their centres has length $1$. We can equivariantly embed $X^1$ into $\mathbf{R}^3$ by mapping each vertex into the centre of a tetrahedron, and mapping each edge affinely. Consequently, we can identify elements $g\in W$ with segments of the form $e_g=((x,y,z),(x+1,y,z))$, where $y+z$ is odd, up to permuting the coordinates. We identify $\mathrm{id}\in W$ with $e_{\mathrm{id}}=((0,0,1),(0,1,1))$. In particular, the point $O=(0,0,0)$ belongs to the identity tetrahedron. Note that for each $g\in W, s\in S$, the segments $e_g,e_{gs}$ are incident. Furthermore, walls in $X^1$ extend to subcomplexes of $\mathbf{R}^3$ isometric to Euclidean planes, and such a wall is adjacent to $g\in W$ if and only if it contains a face of the tetrahedron containing $e_g$.

\begin{lemma}
\label{lem:stepin A3}
Let $|x_0|+1<y_0<z_0$. Let $g\in W$ be such that
\begin{enumerate}[(i)]
\item $e_g=((x_0,y_0,z_0),(x_0+1,y_0,z_0))$, or
\item $e_g=((x_0,y_0,z_0),(x_0,y_0,z_0+1))$.
\end{enumerate}
Then $\ell(w(g))$ equals, respectively,
\begin{enumerate}[(i)]
\item $3$, or
\item $2$.
\end{enumerate}
Furthermore, $e_{\Pi(g)}$ is equal to the translate of $e_g$ by, respectively,
\begin{enumerate}[(i)]
\item $(0,-1,-1)$, or
\item $(0,0,-1)$.
\end{enumerate}
\end{lemma}

\begin{proof} In case (i), suppose first that $x_0+y_0$ is even. Then $e_g$ lies in the tetrahedron with vertices $(x_0,y_0,z_0-1),(x_0,y_0,z_0+1),(x_0+1,y_0-1,z_0),(x_0+1,y_0+1,z_0)$. The walls adjacent to~$g$ are the hyperplanes containing the faces of this tetrahedron, which are $x+y=x_0+y_0, x-y=x_0-y_0, x+z=x_0+1+z_0, x-z=x_0+1-z_0$. Projecting $e_g,O,$ and these walls onto the $xy$ plane (Figure~\ref{fig:proj1}(a)), or the $xz$ plane (Figure~\ref{fig:proj1}(b)), we obtain that $e_g$ is separated from $O$ exactly by the first and fourth among these walls.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.63]{fb}
	\end{center}
	\caption{Proof of Lemma~\ref{lem:stepin A3}, case (i), $x_0+y_0$ even.}\label{fig:proj1}
\end{figure}

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=1]{cube}
	\end{center}
	\caption{Proof of Lemma~\ref{lem:stepin A3}, case (i), $x_0+y_0$ even: the two walls.}\label{fig:cube}
\end{figure}

Consequently, $gT(g)g^{-1}$ consists of the reflections in the first and fourth of these walls. These reflections preserve the cube spanned by $e_g$ and its translates by $(0,-1,0),(0,0,-1),$ and $(0,-1,-1)$, see Figure~\ref{fig:cube}. The longest element (of length~$3$) in the group that these reflections generate maps $e_g$ to its translate by $(0,-1,-1)$.

Secondly, suppose that $x_0+y_0$ is odd. Then $e_g$ lies in the tetrahedron with vertices $(x_0,y_0-1,z_0),(x_0,y_0+1,z_0),(x_0+1,y_0,z_0-1),(x_0+1,y_0,z_0+1)$. Thus the walls adjacent to $g$ are $x+y=x_0+1+y_0, x-y=x_0+1-y_0, x+z=x_0+z_0, x-z=x_0-z_0$. Hence, as illustrated in Figure~\ref{fig:proj2}(a,b), $e_g$ is separated from $O$ exactly by the second and third among these walls.
Consequently, $gT(g)g^{-1}$ consists of the reflections in the second and third of these walls. The longest element (of length $3$) in the group they generate maps $e_g$ to its translate by $(0,-1,-1)$ as before.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.63]{fc}
	\end{center}
	\caption{Proof of Lemma~\ref{lem:stepin A3}, case (i), $x_0+y_0$ odd.}\label{fig:proj2}
\end{figure}

In case (ii), suppose first that $y_0+z_0$ is odd. Then $e_g$ lies in the tetrahedron with vertices $(x_0,y_0-1,z_0),(x_0,y_0+1,z_0),(x_0-1,y_0,z_0+1),(x_0+1,y_0,z_0+1)$.
Thus the walls adjacent to $g$ are $x+z=x_0+z_0, x-z=x_0-z_0, y+z=y_0+z_0+1, y-z=y_0-z_0-1$.
Hence, as illustrated in Figure~\ref{fig:proj3}(a,b), $e_g$ is separated from $O$ exactly by the first and second among these walls.
Consequently, $gT(g)g^{-1}$ consists of the reflections in the first and second of these walls. These reflections commute and preserve the square spanned by $e_g$ and its translate by $(0,0,-1)$. The longest element in the group these reflections generate (i.e.\ their composition) maps $e_g$ to its translate by $(0,0,-1)$.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.63]{fd}
	\end{center}
	\caption{Proof of Lemma~\ref{lem:stepin A3}, case (ii), $y_0+z_0$ odd.}\label{fig:proj3}
\end{figure}

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.63]{fe}
	\end{center}
	\caption{Proof of Lemma~\ref{lem:stepin A3}, case (ii), $y_0+z_0$ even.}\label{fig:proj4}
\end{figure}

Secondly, suppose that $y_0+z_0$ is even. Then $e_g$ lies in the tetrahedron with vertices $(x_0-1,y_0,z_0),(x_0+1,y_0,z_0),(x_0,y_0-1,z_0+1),(x_0,y_0+1,z_0+1)$.
Thus the walls adjacent to $g$ are $x+z=x_0+z_0+1, x-z=x_0-z_0-1, y+z=y_0+z_0, y-z=y_0-z_0$.
Hence, as illustrated in Figure~\ref{fig:proj4}(a,b), $e_g$ is separated from $O$ exactly by the third and
fourth among these walls.
Consequently, $gT(g)g^{-1}$ consists of the (commuting)
reflections in the third and fourth of these walls.
The longest element in the group they generate
maps~$e_g$ to its translate by $(0,0,-1)$ as before.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:second}] Let $\mathcal L$ be the standard language.
For each $C>0$ consider the following $g,g'\in W$ with incident segments
$$e_g=((x_0,y_0,z_0),(x_0+1,y_0,z_0)),\ e_{g'}=((x_0,y_0,z_0),(x_0,y_0,z_0+1))$$
with $x_0,z_0$ even and $y_0$ odd, satisfying
$|x_0|+C<y_0\leq z_0-C$. Suppose that
$g,g'$ are represented by $v,v'\in\mathcal L$ of length $N,N'$ (which differ by $1$).
By Lemma~\ref{lem:stepin A3}, for $n,n'\leq C$ we have that $v(N-3n)$ represents the element of $W$ corresponding to the segment
$e_g-n(0,1,1)$ and $v'(N'-2n')$ represents the element of $W$ corresponding to the segment
$e_{g'}-n'(0,0,1)$. In particular, for $i=3n=2n',$ we see that the
segments corresponding to $v(N-i)$ and $v'(N'-i)$ are
$((x_0,y_0-n,z_0-n),(x_0+1,y_0-n,z_0-n))$ and $
((x_0,y_0,z_0-\frac{3}{2}n),
(x_0,y_0,z_0+1-\frac{3}{2}n))$.
Thus they are at Euclidean distance $\geq n$, so in particular
$\ell(v(N-i)^{-1}v'(N'-i))\geq n$. This shows that part
(ii) of the definition of biautomaticity does not hold for
$\mathcal L$.
\end{proof}

\begin{bibdiv}
\begin{biblist}

\bib{Bahls2006}{article}{
	author={Bahls, Patrick},
	title={Some new biautomatic Coxeter groups},
	journal={J. Algebra},
	volume={296},
	date={2006},
	number={2},
	pages={339--347}}

\bib{BHa}{book}{
	author={Bridson, Martin R.},
	author={Haefliger, Andr\'e},
	title={Metric spaces of non-positive curvature},
	series={Grundlehren der Mathematischen Wissenschaften [Fundamental
		Principles of Mathematical Sciences]},
	volume={319},
	publisher={Springer-Verlag},
	place={Berlin},
	date={1999}}

\bib{BH}{article}{
	author={Brink, Brigitte},
	author={Howlett, Robert B.},
	title={A finiteness property and an automatic structure for Coxeter
		groups},
	journal={Math. Ann.},
	volume={296},
	date={1993},
	number={1},
	pages={179--190}}

\bib{Cap2009}{article}{
	author={Caprace, Pierre-Emmanuel},
	title={Buildings with isolated subspaces and relatively hyperbolic
		Coxeter groups},
	journal={Innov. Incidence Geom.},
	volume={10},
	date={2009},
	pages={15--31}}

\bib{CaMu2005}{article}{
	author={Caprace, Pierre-Emmanuel},
	author={M\"{u}hlherr, Bernhard},
	title={Reflection triangles in Coxeter groups and biautomaticity},
	journal={J. Group Theory},
	volume={8},
	date={2005},
	number={4},
	pages={467--489}}

\bib{CaSh1995}{article}{
	author={Cartwright, Donald I.},
	author={Shapiro, Michael},
	title={Hyperbolic buildings, affine buildings, and automatic groups},
	journal={Michigan Math. J.},
	volume={42},
	date={1995},
	number={3},
	pages={511--523}}

\bib{E}{book}{
	author={Epstein, David B. A.},
	author={Cannon, James W.},
	author={Holt, Derek F.},
	author={Levy, Silvio V. F.},
	author={Paterson, Michael S.},
	author={Thurston, William P.},
	title={Word processing in groups},
	publisher={Jones and Bartlett Publishers, Boston, MA},
	date={1992}}

\bib{FHT}{article}{
	author={Farb, Benson},
	author={Hruska, Chris},
	author={Thomas, Anne},
	title={Problems on automorphism groups of nonpositively curved polyhedral
		complexes and their lattices},
	conference={
		title={Geometry, rigidity, and group actions},
	},
	book={
		series={Chicago Lectures in Math.},
		publisher={Univ. Chicago Press, Chicago, IL},
	},
	date={2011},
	pages={515--560}}

\bib{GeSh1}{article}{
	author={Gersten, Stephen M.},
	author={Short, Hamish},
	title={Small cancellation theory and automatic groups},
	journal={Invent. Math.},
	volume={102},
	date={1990},
	number={2},
	pages={305--334}}

\bib{GeSh2}{article}{
	author={Gersten, Stephen M.},
	author={Short, Hamish},
	title={Small cancellation theory and automatic groups: Part II},
	journal={Invent. Math.},
	volume={105},
	date={1991},
	number={3},
	pages={641--662}}

\bib{LeMi}{article}{
	title={Commensurating {HNN}-extensions: non-positive curvature and biautomaticity},
	author={Leary, Ian},
	author={Minasyan, Ashot},
	eprint={arXiv:1907.03515},
	status={to appear},
	journal={Geom. Topol.},
	date={2020}}

\bib{LS}{book}{
   author={Lyndon, Roger C.},
   author={Schupp, Paul E.},
   title={Combinatorial group theory},
   note={Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89},
   publisher={Springer-Verlag, Berlin-New York},
   date={1977},
   pages={xiv+339}}

\bib{Munro}{article}{
	author={Munro, Zachary},
	title={Weak modularity and $\widetilde{A}_n$ buildings},
	status={submitted},
	date={2019},
	eprint={arXiv:1906.10259}}

\bib{NR}{article}{
   author={Niblo, Graham A.},
   author={Reeves, Lawrence D.},
   title={The geometry of cube complexes and the complexity of their
   fundamental groups},
   journal={Topology},
   volume={37},
   date={1998},
   number={3},
   pages={621--633}}

\bib{NiRe2003}{article}{
	author={Niblo, Graham A.},
	author={Reeves, Lawrence D.},
	title={Coxeter groups act on ${\rm CAT}(0)$ cube complexes},
	journal={J. Group Theory},
	volume={6},
	date={2003},
	number={3},
	pages={399--413}}

\bib{Nos2000}{article}{
	author={Noskov, Gennady A.},
	title={Combing Euclidean buildings},
	journal={Geom. Topol.},
	volume={4},
	date={2000},
	pages={85--116}}

\bib{R}{book}{
   author={Ronan, Mark},
   title={Lectures on buildings},
   series={Perspectives in Mathematics},
   volume={7},
   publisher={Academic Press, Inc., Boston, MA},
   date={1989},
   pages={xiv+201}}

\bib{Sw}{article}{
	author={\'{S}wi{\k{a}}tkowski, Jacek},
	title={Regular path systems and (bi)automatic groups},
	journal={Geom. Dedicata},
	volume={118},
	date={2006},
	pages={23--48}}

\end{biblist}
\end{bibdiv}

\end{document}


\section{Introduction}

Polarization describes the trajectory of the electric field vector of light as it oscillates. Polarimetry and polarization imaging enable technologies in many fields, such as machine vision \cite{wolff_polarization-based_1990,koshikawa_model-based_1985}, remote sensing \cite{tyo_review_2006,schott_fundamentals_2009}, biomedical optics \cite{ghosh_tissue_2011}, astronomy \cite{vlemmings_2007,deglinnocenti_polarization_2004}, and free-space optical communication \cite{Zhang:17,Ma:17,10.1117/12.2312038}. Many quantum information protocols also depend on the determination of polarization states \cite{gasparoni_realization_2004,kok_linear_2007,obrien_photonic_2009,kagalwala_single-photon_2017}. A new generation of polarization imaging cameras is currently under development, which will further accelerate the application of polarimetry in many fields \cite{rubin_matrix_2019}. \par
The state of polarization can be described by the Stokes parameters \cite{stokes_2009,born_principles_1999} or the coherency matrix \cite{goodman_statistical_2000}, which is a generalization of the Jones calculus \cite{jones_new_1941}. The Stokes parameters, $s_0,s_1,s_2,s_3$, and the coherency matrix, $\mathbf{J}$, are related by

\begin{gather}
    \mathbf{J}=\frac{1}{2}\begin{pmatrix}
    s_0+s_1 & s_2+is_3 \\
    s_2-is_3 & s_0-s_1
    \end{pmatrix}. \label{eq:jones}
\end{gather}
The coherency matrix provides all second-order statistical information about the polarization state. \par
As shown in later sections, non-physical coherency matrices (for example, with negative eigenvalues) arise in common polarimetry schemes due to experimental errors, such as fluctuations of the light source, imperfect alignment of optical components, and spectral bandwidth of the source.  Several techniques based on pre-processing, calibration, estimation of the Stokes parameters \cite{Zallat:s,valenzuela_joint_recon,Paxman:s,faisan_filtering_est} and in-situ optimization\cite{foreman_priori_2008,zhi_error_2017, shemirani_Compensation_2010} or novel polarimetric schemes \cite{shi_automatic_2006,collins_galway_2013,lopez-mago_overall_2019,clarke_interference_2004} have been developed to reduce the effect of such experimental errors. One such method of particular interest is the constrained maximum likelihood (CML) method \cite{hu_cml_2013} due to its similarities to our own work in terms of both motivation and application.\par
In this article, we present a method of correcting these non-physical results by finding the closest physical coherency matrix via convex optimization. This method is applied in post-processing, and does not depend on \textit{a priori} information or the experimental setup. Having such a method is especially useful when dealing with other degrees of freedom in addition to polarization. For example, when measuring the polarization profile of a vector beam, we might have the result where only a few points are non-physical due to experimental errors \cite{suzuki_comprehensive_2019}. Using our method, we can find the closest approximate physical coherency matrix for these points rather than invalidating all points and repeating the entire measurement. It is also potentially useful when dealing with measurements that cannot be easily repeated, such as the polarimetry of single photons. This method can be easily generalized to be used for multi-photon Stokes parameters \cite{abouraddy_quantum_2002}.

\section{Experimental Setup} \label{sec:setup}

\begin{figure}
    \centering
    \includegraphics[width=0.5\linewidth]{setup_polarimetry.pdf}
    \caption{Experimental polarimetry setup: (a) modified standard method; (b) polarimeter method. H: half-wave plate; Q: quarter-wave plate; Pol: linear polarizer.}
    \label{fig:setup_polarimetry}
\end{figure}

We used the two independent polarimetry schemes shown in Fig.~\ref{fig:setup_polarimetry} to measure the coherency matrices of both linearly and elliptically polarized light to verify the validity of the developed methods. In both schemes, the light from the laser is vertically polarized, and passes through either a half-wave plate (HWP) or a quarter-wave plate (QWP). The HWP preserves the linearity of the laser light, but changes the angle of polarization, while the QWP changes linear polarization to elliptical polarization. The exact polarization state after the waveplates depends on $\theta$, which is the angle between the fast axis of the waveplates and the horizontal axis. In Fig.~\ref{fig:setup_polarimetry} (a), we use a modified version of the standard method for measuring the Stokes parameters \cite{born_principles_1999,collett_polarized_1993}. The detection scheme consists of another QWP, a linear polarizer, and an intensity detector. The following four intensity measurements are required to measure all four Stokes parameters: $I(0^\circ,0^\circ)$, $I(0^\circ,90^\circ)$, $I(0^\circ,45^\circ)$, and $I(45^\circ,45^\circ)$, where $I(\psi,\phi)$ is the intensity measured by the detector when the fast axis of the QWP (in the detection scheme) is at angle $\psi$ w.r.t. the horizontal axis and the axis of transmission of the polarization is at angle $\phi$ w.r.t. the horizontal axis. The Stokes parameters can be calculated from the intensity measurements using the following equations,
\begin{gather}
    s_0=I(0^\circ,0^\circ)+I(0^\circ,90^\circ), \label{EqS0}\\
    s_1=I(0^\circ,0^\circ)-I(0^\circ,90^\circ), \\
    s_2=2I(45^\circ,45^\circ)-s_0, \\
    s_3=2I(0^\circ,45^\circ)-s_0. \label{EqS3}
\end{gather} \par
Care was taken to ensure proper alignment of the quarter-wave-plate and linear polarizer. However, only four data points are measured, which increases the chance non-physical results due to fluctuations of the laser light between the four intensity measurements. In the polarimeter method (Fig.~\ref{fig:setup_polarimetry} (b)), the measurement is done solely with a polarimeter, and the Stokes parameters are given automatically. The polarimeter employs a spinning waveplate and curve-fitting technique to obtain the Stokes parameters \cite{schaefer_measuring_2007}. While this method is fast (sampling rate up to \SI{400}{Hz}), the polarimeter still sometimes produces non-physical results especially if the input power exceeds 2 mW as per company specification. In both methods different input states were prepared using a quarter wave plate and rotated by 10 degrees for one half of a complete rotation which is sufficient to obtain a complete cycle of intensity. Using both methods, we measured the Stokes parameters of high intensity light ($\sim\SI{16}{mW}$) and low intensity light  ($\sim\SI{1.4}{mW}$) for both linearly and elliptically polarized light. Measurements with high input power of about 15 mW was used to produce non-physical results using the polarimeter.

\section{Polarimetry as a Convex Optimization Problem} \label{sec:method}

As stated previously, experimental errors can lead to non-physical results where the coherency matrix has negative eigenvalues. Such non-physical coherency matrices result in degrees of polarization (DOP) greater than 1. The DOP quantifies the portion of the light that is polarized, and it can be obtained from the Stoke parameters or the coherency matrix using \cite{born_principles_1999}
\begin{gather}\label{eq_DOP_def}
    \mathrm{DOP}^2=\frac{s_1^2+s_2^2+s_3^2}{s_0^2}= \frac{2}{s_0^2}\Tr(\mathbf{J}^2)-1.
\end{gather}

Throughout the paper, the measured coherency matrix, $\mathbf{J}_\mathrm{measured}$, is constructed from the Stokes parameters in Eqs.~\eqref{EqS0}--\eqref{EqS3} using Eq.~\eqref{eq:jones} and normalized such that $\operatorname{Tr}(\mathbf{J}_\mathrm{measured})=1$.

We want to find the corrected coherency matrix, $\mathbf{J}_{\mathrm{corrected}}$, that is closest to $\mathbf{J}_{\mathrm{measured}}$ under the constraint that $\mathbf{J}_{\mathrm{corrected}}$ be physical.  This is equivalent to solving the following optimization problem,
\begin{mini!}|l|
    {\mathbf{J}_{\mathrm{corrected}}}{\|\mathbf{J}_{\mathrm{measured}} - \mathbf{J}_{\mathrm{corrected}}\|}{}{} \label{objective}
    \addConstraint{\mathbf{J}_{\mathrm{corrected}}}{\geq 0}{} \label{constraint1}
    \addConstraint{\Tr(\mathbf{J}_{\mathrm{corrected}})}{= 1}{}. \label{constraint2}
\end{mini!}

This problem is an example of a convex optimization problem, which is an optimization problem where the objective and constraint functions $f_i(x): \mathcal{C} \rightarrow \mathbb{R}$ are convex, i.e. they satisfy the condition that for all $x,y \in \mathcal{C}$,
\begin{equation}
    f_{i}(t x + (1-t)y) \leq t f_{i}(x) + (1-t) f_i(y),
    \label{convex}
\end{equation}
where $t \in[0,1]$ and $\mathcal{C}$ is some convex set \cite{boyd_vandenberghe_2004}.  A convex set $\mathcal{C}$ is defined as a set where, for all $x,y \in \mathcal{C}$ and $t \in [0,1]$, $t x + (1-t)y \in \mathcal{C}$.  The constraint presented in Eq.~\eqref{constraint1} restricts the possible choices for $\mathbf{J}_{\mathrm{corrected}}$ to the set of positive semi-definite matrices, which are known to form a convex set \cite{neumann}.  The objective function Eq.~\eqref{objective} in our problem is convex due to the definition of norms, namely that they are subadditive and absolutely scalable.  Finally, we know that Eq.~\eqref{constraint2} is convex because of the linearity of trace, $\Tr(\alpha \mathbf{A} + \beta \mathbf{B}) = \alpha \Tr(\mathbf{A}) + \beta \Tr(\mathbf{B})$, which satisfies Eq.~\eqref{convex} with equality.  Thus, our problem is convex.  Since the solution to a convex optimization problem is unique and provides a lower bound on more general optimization problems, the ability to construct and solve a convex optimization problem has proven useful in a wide variety of topics such as the reconstruction of quantum channels \cite{huang_2020}, the selection of sensors to minimize error in a measurement \cite{joshi_boyd_2009}, and multi-period trading \cite{boyd_busseti_diamond_kahn_koh_nystrup_speth_2017}.  As such, a number of tools and techniques for solving convex optimization problems efficiently have been developed. In particular we opted to use Matlab's CVX library\cite{cvx,gb08} due to its ability to handle complex matrices and its ease of use compared to other options.  \par

\begin{figure}[htbp]
    \centering
    \includegraphics[width=.8\linewidth]{figtolerance.pdf}
    \caption{Schematic for the construction of a convex optimization problem to determine the coherency matrices with the highest and lowest DOP (respectively $\mathbf{J}_{\mathrm{max}}$ and $\mathbf{J}_{\mathrm{min}}$) for a given $\mathbf{J}_{\mathrm{measured}}$ and error tolerance $\epsilon$. The blue arrows are the Stokes vectors of the corresponding coherency matrices. $\mathbf{I}/2$ corresponds to the zero vector, where $\mathbf{I}$ is the identity matrix.}
    \label{fig:schematic}
\end{figure}

We also want to determine the upper and lower bounds on the DOP for $\mathbf{J}_{\mathrm{corrected}}$ given some tolerance $\epsilon$ for the acceptable difference between $\mathbf{J}_{\mathrm{corrected}}$ and $\mathbf{J}_{\mathrm{measured}}$. The appropriate choice for the value of $\epsilon$ will be determined by the amount of noise in the measurement of $\mathbf{J}_{\mathrm{measured}}$.  If there is a lot of noise, a larger value must be selected for the tolerance in order to obtain solutions that still lie within the Poincar\'e sphere.  Let $\mathbf{J}_{\min}$ denote the value for $\mathbf{J}_{\mathrm{corrected}}$ with the lowest DOP for the specified tolerance $\epsilon$; likewise, $\mathbf{J}_{\max}$ be the value for $\mathbf{J}_{\mathrm{corrected}}$ with the largest DOP. If we consider the representation of coherence matrices on the Poincar\'{e} sphere as shown in Fig.~\ref{fig:schematic}, the Stokes vectors for  $\mathbf{J}_{\min}$ and  $\mathbf{J}_{\max}$ must lie within a ball of radius $\epsilon$ centered on $\mathbf{J}_{\mathrm{measured}}$. With this information and Eq.~\eqref{eq_DOP_def}, we might be tempted to construct convex optimization problems as
\begin{mini}|l|
    {\mathbf{J}_{\min}}{\Tr(\mathbf{J}_{\min}^2)}{}{}
    \addConstraint{\|\mathbf{J}_{\min}-\mathbf{J}_{\mathrm{measured}}\|}{\leq \epsilon}{}
    \addConstraint{\Tr(\mathbf{J}_{\min})}{= 1}{}
    \addConstraint{\mathbf{J}_{\min}}{\geq 0}{}
    \label{naive_min}
\end{mini}
for finding $\mathbf{J}_{\min}$ or
\begin{maxi}|l|
    {\mathbf{J}_{\max}}{\Tr(\mathbf{J}_{\max}^2)}{}{}
    \addConstraint{\|\mathbf{J}_{\max}-\mathbf{J}_{\mathrm{measured}}\|}{\leq \epsilon}{}
    \addConstraint{\Tr(\mathbf{J}_{\max})}{= 1}{}
    \addConstraint{\mathbf{J}_{\max}}{\geq 0}{}
    \label{naive_max}
\end{maxi}
for finding $\mathbf{J}_{\max}$, but attempting to solve either of these problems is actually impossible using MATLAB's CVX library.  This is due to the rules (called the Disciplined Convex Programming (DCP) ruleset) that the library uses to determine if an expression is a valid convex optimization problem.  In particular, the library cannot determine whether the objective functions of Eq.~\eqref{naive_min} or Eq.~\eqref{naive_max} are convex because they involve the squaring of variables that are not scalars.  However, if we consider other ways of characterizing the DOP, it is possible to reformulate Eq.~\eqref{naive_min} or Eq.~\eqref{naive_max} so that they satisfy the DCP rules.  By Eq.~\eqref{eq_DOP_def}, we also know that the DOP of a coherency matrix corresponds to the length of its Stokes vector.  If a ray (labelled $\tau$ in Fig.~\ref{fig:schematic}) is drawn from the origin of the Poincar\'{e} sphere in the direction of the Stokes vector for $\mathbf{J_\mathrm{measured}}$, the parameter $\tau$ can be introduced to describe the length of Stokes vectors that lie on the ray such that a larger value for $\tau$ describes a longer Stokes vector.  This means that $\tau$ also describes the DOP of the coherency matrices that correspond to these Stokes vectors, and that $\mathbf{J}_{\mathrm{max}}$ and $\mathbf{J}_{\mathrm{min}}$ are found where this ray intersects the $\epsilon$-ball.  Thus, we require that the sought $\mathbf{J}_{\mathrm{max}}$ and $\mathbf{J}_{\mathrm{min}}$ lie on the ray using the expression,
\begin{equation}
    \left\|\mathbf{J}_{\min, \max} - \tau\mathbf{J}_{\mathrm{measured}} - \frac{1-\tau}{2}\mathbf{I}\right\| = 0,
    \label{convexline}
\end{equation}
so that $\mathbf{J}_{\max}$ and $\mathbf{J}_{\min}$ can be found by maximizing and minimizing $\tau$, respectively. Our objective function is now just $\tau$, which is clearly a convex function, and it will satisfy the DCP rules of MATLAB's CVX library. It is important to note that the value of $\tau$ obtained via optimization not only depends upon $\mathbf{J}_{\mathrm{measured}}$ and $\epsilon$, but also on the constraint both $\mathbf{J}_{\min, \max}$ be non-negative as in the problem~\eqref{objective}--~\eqref{constraint2}.
Because the l.h.s. of Eq.~\eqref{convexline} is a norm of a linear expression over a convex set, the constraint function \eqref{convexline} is convex.  Now we can combine the constraints~\eqref{constraint1}, ~\eqref{constraint2}, and ~\eqref{convexline} with the requirement that $\mathbf{J}_{\min, \max}$ be $\epsilon$-close to $\mathbf{J}_{\mathrm{measured}}$ to formulate the following convex optimization problems for obtaining physically corrected coherency matrices $\mathbf{J}_{\min, \max}$ with the minimal and maximal DOP:

To recover the physically-constrained coherency matrix $\mathbf{J}_{\min}$ with the minimal DOP that is $\epsilon$-close to the measured  $\mathbf{J}_{\mathrm{measured}}$, we solve the convex optimization problem
\begin{mini}|l|
    {\tau, \mathbf{J}_{\min}}{\tau}{}{}
    \addConstraint{\|\mathbf{J}_{\min} - \tau\mathbf{J}_{\mathrm{measured}} - \frac{1-\tau}{2}\mathbf{I}\|}{= 0}{}
    \addConstraint{\|\mathbf{J}_{\min}-\mathbf{J}_{\mathrm{measured}}\|}{\leq \epsilon}{}
    \addConstraint{\Tr(\mathbf{J}_{\min})}{= 1}{}
    \addConstraint{\mathbf{J}_{\min}}{\geq 0}{}.
    \label{min_dop}
\end{mini}
Likewise, to obtain the physically-constrained coherency matrix $\mathbf{J}_{\max}$ with the maximal DOP that is $\epsilon$-close to the measured  $\mathbf{J}_{\mathrm{measured}}$, we solve
\begin{maxi}|l|
    {\tau, \mathbf{J}_{\max}}{\tau}{}{}
    \addConstraint{\|\mathbf{J}_{\max} - \tau\mathbf{J}_{\mathrm{measured}} - \frac{1-\tau}{2}\mathbf{I}\|}{= 0}{}
    \addConstraint{\|\mathbf{J}_{\max}-\mathbf{J}_{\mathrm{measured}}\|}{\leq \epsilon}{}
    \addConstraint{\Tr(\mathbf{J}_{\max})}{= 1}{}
    \addConstraint{\mathbf{J}_{\max}}{\geq 0}{}.
    \label{max_dop}
\end{maxi}

\section{Results} \label{sec:results}

To solve Eqs.~\eqref{objective}--~\eqref{constraint2}, ~\eqref{min_dop}, and ~\eqref{max_dop}, we had to specify a norm.  We chose to use the Frobenius norm, which is defined by
\begin{equation}
    \left\|\mathbf{A}\right\|_\mathrm{F} = \sqrt{\Tr(\mathbf{A}^\dag\mathbf{A})},
\end{equation}
because, according to Eq.~\eqref{eq_DOP_def}, the Frobenius norm of a coherency matrix is related to its DOP.  While the use of the Frobenius norm may have been the natural choice given our interest in the DOP, the convex optimization problems outlined in Eqs.~\eqref{objective}--~\eqref{constraint2}, ~\eqref{min_dop}, and ~\eqref{max_dop} can be solved using any norm. Certain experimental applications may find that the use of a particular norm is more beneficial than others, however.  As an example, the use of the 1-norm may lead to better results for compressed-sensing applications.  Additionally, different norms may be useful for modelling different kinds of noise present in the system.  A comparison of the results of the minimization and maximization methods using the Frobenius norm, the 1-, $\infty$-, and 2-norms are displayed in Fig.~\ref{fig:norm}.  For an $m$-by$n$ matrix $\mathbf{A}$, these norms are defined in the following way
\begin{gather}
    \|\mathbf{A}\|_{1} = \max_{1 \leq j \leq n} \sum_{i=1}^m |a_{ij}|, \qquad
    \|\mathbf{A}\|_{\infty} = \max_{1 \leq i \leq m} \sum_{j=1}^n |a_{ij}|, \qquad
    \|\mathbf{A}\|_{2} = \sigma_{\max}(\mathbf{A}) \leq \|\mathbf{A}\|_\mathrm{F},
\end{gather}
where $\sigma_{\max}(\mathbf{A})$ is the largest singular value of $\mathbf{A}$.  As can be seen in Fig.~\ref{fig:norm}, the 1- and $\infty$-norms always give the same result for the DOP.  This is because the coherency matrix is a $2\times2$ symmetric matrix, which means that the maximum absolute column sum will always equal the maximum absolute row sum.  For linearly polarized light, the values of DOP obtained from the minimization problem Eq.~\eqref{min_dop} using the 1-norm (or $\infty$-norm) are always greater than those obtained using the Frobenius norm or the 2-norm.  Additionally, using either the 2-norm or the Frobenius norm gives the same results for linearly polarized light.  For elliptically polarized light, the results obtained using the Frobenius norm are higher than those obtained using the 2-norm, with the plots of the two forming upper and lower bounds on the results obtained using the 1-norm ($\infty$-norm).\par
\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{cropped_norm_comparisons.pdf}
    \caption{DOP of $\mathbf{J}_{\mathrm{\max}}$ and $\mathbf{J}_{\mathrm{\min}}$ for linearly polarized light (first and second columns respectively) and for ellptically polarized light (third and fourth columns respectively) obtained by solving Eqs.~\eqref{min_dop} and ~\eqref{max_dop} using the Frobenius norm, the 1-norm, the 2-norm, and the $\infty$-norm.  The first and second rows used high intensity light measured with the standard method and the polarimeter method respectively.  The third and fourth rows used low intensity light measured using the standard method and polarimeter method respectively.}
    \label{fig:norm}
\end{figure}
\begin{figure}
    \centering
    \includegraphics[width=.95\linewidth]{lp_fig.pdf}
    \caption{DOP of $\mathbf{J}_{\mathrm{measured}}$ and $\mathbf{J}_{\mathrm{corrected}}$ (left column) and the location of their corresponding vectors on the Poincar\'{e} sphere (right column) for linearly polarized light: (a), (b) high intensity light measured with the standard method; (c), (d) high intensity light measured with the polarimeter method; (e), (f) low intensity light measured with the standard method; (g), (h) low intensity light measured with the polarimeter method.  In each case, $\mathbf{J}_{\mathrm{corrected}}$ was obtained by solving Eqs.~\eqref{objective}--~\eqref{constraint2}.  The minimum and maximum DOP were calculated from the solutions to Eqs.~\eqref{min_dop} and ~\eqref{max_dop} using a tolerance of $\epsilon = 0.1$.}
    \label{fig:lp_fig}
\end{figure}
\begin{table}[htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|}
        \multicolumn{8}{c}{Linearly Polarized Data} \\
        \hline
        & \multicolumn{4}{|c|}{Measured}  & \multicolumn{3}{|c|}{Corrected} \\
        \hline
        Data Set& $\theta$ & $s_1/s_0$ & $s_2/s_0$ & $s_3/s_0$ & $s_1/s_0$ & $s_2/s_0$ & $s_3/s_0$ \\
        \hline
        \multirow{3}{4em}{High Intensity Standard} & 5 & -0.928 & -0.382 & -0.033 & -0.924 & -0.381 & -0.033 \\
        & 35 & 0.781 & -0.644 & -0.002 & 0.772 & -0.636 & -0.002 \\
        & 40 & 0.945 & -0.335 & -0.005 & 0.942 & -0.334 & -0.005 \\
        \hline
        \multirow{6}{4em}{High Intensity Polarimeter} & 5 & -0.947 & -0.325 & -0.038 & -0.945 & -0.325 & -0.038 \\
        & 10 & -0.771 & -0.639 & -0.038 & -0.770 & -0.637 & -0.038 \\
        & 15 & -0.503 & -0.866 & -0.039 & -0.502 & -0.864 & -0.038 \\
        & 20 & -0.199 & -0.982 & -0.039 & -0.199 & -0.979 & -0.039 \\
        & 25 & 0.160 & -0.989 & -0.036 & 0.160 & -0.987 & -0.036 \\
        & 30 & 0.494 & -0.869 & -0.033 & 0.494 & -0.869 & -0.033 \\
        \hline
        \multirow{2}{4em}{Low Intensity Polarimeter} & 0 & -0.999 & -0.010 & -0.043 & -0.999 & -0.010 & -0.043  \\
        & 90 & -0.999 & -0.005 & -0.056 & -0.998 & -0.005 & -0.056 \\
        \hline
    \end{tabular}
    \caption{Values of the Stokes parameters obtained from the experimental data (under the "Measured" column) and from the results of applying our convex optimization method (Eqs.~\eqref{objective}-~\eqref{constraint2}) (under the "Corrected" column) for linearly polarized light where the DOP $\geq$ 1 when calculated using the experimental data.}
    \label{tab:lp_data}
\end{table}
\begin{figure}
    \centering
    \includegraphics[width=.95\linewidth]{cp_fig.pdf}
    \caption{DOP of $\mathbf{J}_{\mathrm{measured}}$ and $\mathbf{J}_{\mathrm{corrected}}$ (left column) and the location of their corresponding vectors on the Poincar\'{e} sphere (right column) for elliptically polarized light: (a), (b) low intensity light measured with the standard method; (c), (d) high intensity light measured with the standard method; (e), (f) low intensity light measured with the polarimeter method; (g), (h) high intensity light measured with the polarimeter method.  In each case, $\mathbf{J}_{\mathrm{corrected}}$ was obtained by solving Eqs.~\eqref{objective}--~\eqref{constraint2}.  The minimum and maximum DOP were calculated from the solutions to Eqs.~\eqref{min_dop} and ~\eqref{max_dop} using a tolerance of $\epsilon = 0.1$.}
    \label{fig:cp_fig}
\end{figure}
\begin{table}[htbp]
    \small
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|}
        \hline
        \multicolumn{8}{|c|}{Elliptically Polarized Data} \\
        \hline
        \multicolumn{1}{|c|}{Data Set} & \multicolumn{4}{|c|}{Measured}  & \multicolumn{3}{|c|}{Corrected} \\
        \hline
        & $\theta$ & $s_1/s_0$ & $s_2/s_0$ & $s_3/s_0$ & $s_1/s_0$ & $s_2/s_0$ & $s_3/s_0$ \\
        \hline
        \multirow{9}{4em}{Low Intensity Standard} & 0 & -0.990 & 0.105 & 0.139 & -0.985 & 0.104 & 0.138 \\
        & 10 & -0.944 & -0.232 & 0.384 & -0.903 & -0.222 & 0.369 \\
        & 20 & -0.683 & -0.473 & 0.590 & -0.670 & -0.464 & 0.579 \\
        & 50 & -0.042 & 0.070 & 1.00 & -0.042 & 0.070 & 0.997 \\
        & 60 & -0.196 & 0.354 & 1.02 & -0.179 & 0.324 & 0.929 \\
        & 70 & -0.513 & 0.496 & 0.944 & -0.434 & 0.419 & 0.798 \\
        & 80 & -0.826 & 0.333 & 0.703 & -0.728 & 0.294 & 0.620 \\
        & 90 & -0.993 & 0.075 & 0.344 & -0.943 & 0.071 & 0.326 \\
        & 180 & -0.992 & 0.117 & 0.112 & -0.987 & 0.117 & 0.111 \\
        \hline
        \multirow{5}{4em}{High Intensity Standard} & 0 & -0.999 & 0.058 & 0.013 & -0.998 & 0.058 & 0.013 \\
        & 70 & -0.616 & 0.558 & 0.663 & -0.580 & 0.525 & 0.623 \\
        & 80 & -0.908 & 0.356 & 0.402 & -0.861 & 0.338 & 0.381 \\
        & 120 & -0.225 & -0.438 & -0.896 & -0.220 & -0.429 & -0.876 \\
        & 130 & -0.020 & -0.185 & -0.991 & -0.020 & -0.184 & -0.983 \\
        \hline
        \multirow{9}{4em}{Low Intensity Polarimeter} & 10 & -0.917 & -0.356 & -0.232 & -0.907 & -0.353 & -0.230 \\
        & 20 & -0.640 & -0.549 & -0.555 & -0.634 & -0.544 & -0.550 \\
        & 30 & -0.295 & -0.510 & -0.813 & -0.293 & -0.508 & -0.810 \\
        & 40 & -0.062 & -0.264 & -0.967 & -0.062 & -0.263 & -0.963 \\
        & 90 & -0.992 & -0.073 & -0.114 & -0.991 & -0.073 & -0.114 \\
        & 100 & -0.894 & -0.408 & 0.237 & -0.884 & -0.404 & 0.234 \\
        & 110 & -0.595 & -0.602 & 0.565 & -0.585 & -0.591 & 0.556 \\
        & 120 & -0.246 & -0.554 & 0.821 & -0.241 & -0.543 & 0.805 \\
        & 130 & -0.008 & -0.291 & 0.960 & -0.008 & -0.290 & 0.957 \\
        \hline
        \multirow{10}{4em}{High Intensity Polarimeter} & 10 & -0.904 & -0.342 & -0.278 & -0.899 & -0.340 & -0.277 \\
        & 20 & -0.610 & -0.529 & -0.602 & -0.606 & -0.525 & -0.598 \\
        & 30 & -0.262 & -0.474 & -0.847 & -0.261 & -0.471 & -0.843 \\
        & 40 & -0.032 & -0.223 & -0.979 & -0.031 & -0.222 & -0.975 \\
        & 50 & -0.019 & 0.110 & -0.995 & -0.019 & 0.110 & -0.994 \\
        & 100 &-0.877 & -0.399 & 0.299 & -0.869 & -0.396 & 0.296 \\
        & 110 & -0.578 & -0.569 & 0.609 & -0.570 & -0.561 & 0.600 \\
        & 120 & -0.224 & -0.502 & 0.851 & -0.221 & -0.496 & 0.840 \\
        & 130 & 0.010 & -0.222 & 0.985 & 0.010 & -0.219 & 0.976 \\
        & 140 & 0.010 & 0.116 & 0.994 & 0.010 & 0.116 & 0.993 \\
        \hline
    \end{tabular}
    \caption{Values of the Stokes parameters obtained from the experimental data (under the "Measured" column) and from the results of applying our convex optimization method (Eqs.~\eqref{objective}-~\eqref{constraint2}) (under the "Corrected" column) for elliptically polarized light where the DOP $\geq$ 1 when calculated using the experimental data.}
    \label{tab:cp_data}
\end{table}
The results of our program, shown in Code 1 \cite{leamer_git}, applied to four sets of measured coherency matrices of linearly polarized light and four sets of measured coherency matrices of elliptically polarized light are respectively displayed in Fig.~\ref{fig:lp_fig} and Fig.~\ref{fig:cp_fig}.  Additionally, we present the values of the Stokes parameters for the points where the DOP $\geq$ 1 when calculated from the experimental data for linearly polarized (Table~\ref{tab:lp_data}) and elliptically polarized light (Table~\ref{tab:cp_data}).  The "Measured" column contains the measured values, while the "Corrected" column contains the values obtained by solving our minimization problem ~\eqref{objective}--~\eqref{constraint2}. In the non-physical cases where the DOP of $\mathbf{J}_\mathrm{measured}$ is greater than 1, the DOP of  $\mathbf{J}_{\mathrm{corrected}}$ obtained from our method is exactly 1. In the cases where $\mathbf{J}_\mathrm{measured}$ is physical, the obtained $\mathbf{J}_{\mathrm{corrected}}$ is equal to $\mathbf{J}_\mathrm{measured}$.  In both measurement schemes shown in Fig.~\ref{fig:setup_polarimetry}, we found that measuring the vertically polarized light through a QWP gave more non-physical results than that of a HWP. \par
We also found  $\mathbf{J}_{\min, \max}$ with the minimum and maximum DOP given a tolerance parameter of $\epsilon = 0.1$, which was done by solving the optimization problems defined in Eqs.~\eqref{min_dop} and ~\eqref{max_dop}, respectively. In most cases, the maximum DOP is found to be 1 and the minimum DOP is a constant value, which depends on $\epsilon$, lower than the measured DOP. Given the constraints in Eqs.~\eqref{min_dop} and ~\eqref{max_dop}, this is to be expected. There are a few exceptional points. In Fig.~\ref{fig:cp_fig}(c) at $\theta = 30^{\circ}, 40^{\circ}$, the maximum DOP is lower than 1. This is caused by the constraint that $\mathbf{J}_{\max}$ be $\epsilon$-close to $\mathbf{J}_{\mathrm{measured}}$, which makes the Stoke vector for $\mathbf{J}_{\max}$ lie inside the Poincar\'{e} sphere. Another exceptional case is demonstrated by the missing points on both the max DOP and min DOP plots in Fig.~\ref{fig:cp_fig}(a) at $\theta = 70^{\circ}$. Here, due to the same constraint above, the vectors corresponding to both $\mathbf{J}_\mathrm{max}$ and $\mathbf{J}_\mathrm{min}$ lie outside the Poincar\'{e} sphere, and thus, no solutions for both Eqs.~\eqref{min_dop} and ~\eqref{max_dop} can be found.

\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{cropped_rmse_fig3.pdf}
    \caption{RMSE for the values of the Stokes parameters obtained from the unconstrained data (`uncon', blue circles), our convex optimization method (Eq.~\eqref{convex}, `conv opt', red crosses), the CML method (`cml', yellow squares), and the empirical method (`emp',purple triangles) as a function of the SNR \cite{hu_cml_2013}.  Each row of the figure corresponds to the results obtained by applying these methods to a set of data that was randomly generated using a different mean polarization state.  The results for the $s_1$, $s_2$, and $s_3$ parameters are grouped by column for each data set.}
    \label{fig:rmse}
\end{figure}

The normalized Stokes vectors corresponding to $\mathbf{J}_{\mathrm{corrected}}$ and $\mathbf{J}_{\mathrm{measured}}$ for each of the data points are displayed in the right column of Fig.~\ref{fig:lp_fig} for linearly polarized light and in the right column of Fig.~\ref{fig:cp_fig} for elliptically polarized light.  In every case, the vectors for $\mathbf{J}_{\mathrm{corrected}}$ and $\mathbf{J}_{\mathrm{measured}}$ are parallel. In the cases where the vector of $\mathbf{J}_{\mathrm{measured}}$ is outside the Poincar\'{e} sphere, the vector of $\mathbf{J}_{\mathrm{corrected}}$ ends on the surface of the Poincar\'{e} sphere.  This indicates that our method is successful at preserving the direction of the measured Stoke vectors while correcting for experimental errors. \par
 Another method for correcting the non-physical results in polarimetry experiments that is similar to the convex optimization method we have presented thus far is the constrained maximum likelihood (CML) estimator \cite{hu_cml_2013}.  In this work, Hu and Goudai develop an optimization scheme based on the Lagrange multiplier technique and apply it to correcting non-physical results obtained from the measurement of four points on the Poincar\'{e} sphere.  Additionally, the ``empirical" estimator method is presented in \cite{hu_cml_2013}. This method is applied by dividing the measured $s_1$, $s_2$, and $s_3$ parameters by the unconstrained DOP to obtain a set of new Stokes parameters that have a DOP of 1. \par

In Fig.~\ref{fig:rmse}, we compare the CML and empirical methods with our convex optimization technique by considering the estimation accuracy as a function of the signal-to-noise ratio (SNR) for the $s_1$, $s_2$, and $s_3$ parameters. Let $\ket{D}$, $\ket{A}$, $\ket{L}$, and $\ket{R}$ denote the Stoke vectors for diagonal, antidiagonal, left, and right polarizations, respectively (see also the labels in the Poincar\'e spheres in Figs.~\ref{fig:lp_fig} and ~\ref{fig:cp_fig}). For every value of SNR and for every polarization state $\ket{pol} \in \left\{ \ket{D}, \ket{A}, \ket{L}, \ket{R} \right\}$, we generate 50,000 samples of the Stokes vector $\ket{pol}$ contaminated by the additive Gaussian noise with zero mean and variance $\sigma^2 = \frac{1}{\mathrm{SNR}}$. The SNR is chosen to be in the range of 100 to 1000, where most polarimeters operate. The  accuracy of a polarimetry method is characterized via the root mean square error (RMSE). The RMSE between the reconstructed values for the Stokes parameter $s_k^\mathrm{est}$ and the known true value $s_k^0$ is given by
\begin{equation}
    \mathrm{RMSE}(s_k^{\mathrm{est}}) = \sqrt{\left\langle s_k^{\mathrm{est}} - s_k^0 \right\rangle ^2}, \qquad k=1,2,3,
\end{equation}
where $\langle \cdot \rangle$ represents the average over 50,000 samples. RMSE as a function of the SNR for each method and the unconstrained data are shown in Fig.~\ref{fig:rmse}. In every case, our convex optimization scheme outperforms the CML and empirical estimator methods albeit with a minor improvement in RMSE ($\sim 0.05$ at most). This would seem to imply that these methods are largely interchangeable, but our convex optimization scheme does have the advantage of being easier to implement as well as supporting a variety of noise models by utilizing different matrix norms.

\section{Conclusion}

We presented the convex optimization methods for the purpose of robust polarimetry as described in Sec.~\ref{sec:method}. We have demonstrated the validity of these methods using the experimentally measured results obtained for different polarization states and via different polarimetry schemes described in Sec.~\ref{sec:setup}. The performance of the developed techniques are discussed in Sec.~\ref{sec:results}. The presented methods do not depend on any \textit{a priori} information or calibration of the components nor on the type of experimental noise or error, and can be easily integrated into the post-processing of many polarimetry protocols.

\section*{Funding}

Defense Advanced Research Projects Agency (DARPA)(D19AP00043); U.S. Office of Naval Research (N000141912374); Louisiana Board of Regents’ Graduate Fellowship Program.

\section*{Acknowledgments}

This work was supported by the Defense Advanced Research Projects Agency (DARPA) grant number D19AP00043 under mentorship of Dr. Michael Fiddy. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of DARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. RTG also acknowledges funding from the U.S. Office of Naval Research under grant number N000141912374. J.M.L. was supported by the Louisiana Board of Regents’ Graduate Fellowship Program.

\section*{Disclosures}

The authors declare no conflicts of interest.

\newpage