#  $\mathrm{SE}(3)$ Synchronization by Eigenvectors
of Dual Quaternion Matrices

Ido Hadi  Tamir Bendory  Nir Sharon

###### Abstract

In synchronization problems, the goal is to estimate elements of a group from
noisy measurements of their ratios. A popular estimation method for
synchronization is the spectral method. It extracts the group elements from
eigenvectors of a block matrix formed from the measurements. The eigenvectors
must be projected, or “rounded,” onto the group. The rounding procedures are
constructed ad hoc and increasingly so when applied to synchronization
problems over non-compact groups.

In this paper, we develop a spectral approach to synchronization over the non-
compact group $\mathrm{SE}(3)$, the group of rigid motions of
$\mathbb{R}^{3}$. We based our method on embedding $\mathrm{SE}(3)$ into the
algebra of dual quaternions, which has deep algebraic connections with the
group $\mathrm{SE}(3)$. These connections suggest a natural rounding procedure
considerably more straightforward than the current state-of-the-art for
spectral $\mathrm{SE}(3)$ synchronization, which uses a matrix embedding of
$\mathrm{SE}(3)$. We show by numerical experiments that our approach yields
comparable results to the current state-of-the-art in $\mathrm{SE}(3)$
synchronization via the spectral method. Thus, our approach reaps the benefits
of the dual quaternion embedding of $\mathrm{SE}(3)$, while yielding
estimators of similar quality.

##  1 Introduction

Synchronization problems arise as part of data processing pipelines in several
contexts, including single-particle reconstruction in cryogenic electron
microscopy [21, 3], structure from motion problems [27, 1] and simultaneous
localization and mapping (SLAM) problems [2, 23]. A synchronization problem is
an estimation problems over a group $G$ in which group elements
$g_{1},\dots,g_{n}\in G$ are estimated from measurements of their ratios
$g_{i}g_{j}^{-1}$. These measurements are inherently ambiguous, since the set
of ratios of $g_{1}g,\dots,g_{n}g\in G$ for any $g\in G$ are the same as the
ratios of the original group elements. Thus, in synchronization problems, the
goal is to estimate the group elements up to right-multiplication by an
arbitrary element of $G$.

The spectral method is a widely used method for solving synchronization
problems. It seeks to approximate a solution by finding eigenvectors of a
block matrix formed by embedding the group into a matrix algebra. The
embedding enables the richer algebraic structure of matrix algebras, and in
particular their spectral decomposition, to be leveraged to solve the
synchronization problem. Importantly, the eigenvectors of the observation
matrix are not themselves a solution of the synchronization problem. They have
to be projected back onto the group, a projection that is typically non-
linear. This procedure is often referred to as “rounding” in the
synchronization literature. In typical rounding procedures, a matrix formed by
these eigenvectors is chopped into blocks and these blocks are subsequently
mapped onto elements of the group.

Consider a synchronization problem over a relative simple compact group in the
absence of measurement noise. As we explain in greater detail in Section 3.2,
even in this ideal setting, typically there is a gap between the
synchronization problem and the eigenproblem used to solve it. Oversimplifying
to an extent, we can say that every solution to synchronization problem is a
solution of the eigenproblem used by the spectral method, but not every
solution of the eigenproblem is a solution of the synchronization problem.
This issue is exacerbated for synchronization over non-compact group, the
focal point of this paper. The solutions of the eigenproblem form a compact
set, the set of unit eigenvectors which span the relevant eigenspaces of the
measurement matrix. Yet, unlike the case of synchronization over compact
groups, the possible solutions of a synchronization problems over non-compact
groups form a non-compact set. Therefore, the gap between the two problems can
be said to be much larger.

In practice, this gap between the eigenproblem and the synchronization problem
must be bridged by the rounding procedure. It ensures that the output of the
synchronization method is comprised of elements of the group. However,
existing rounding procedures are made to do so in an ad hoc manner.
Specifically, they do not stem from a well characterized relationship between
the synchronization problem and the eigenproblem or the relationship between
their respective algebraic contexts, the group and the algebra in which it is
embedded. They are merely constructed to ensure that the result of a
synchronization problem is an element of the group.

In this paper, we address the issues we raised above in the non-compact case
of $\mathrm{SE}(3)$ synchronization, the group of rigid motions, rotations and
translations, of $\mathbb{R}^{3}$. In [2], an analog of the spectral method
was developed for $\mathrm{SE}(3)$ synchronization, which utilized an
embedding of $\mathrm{SE}(3)$ into a matrix algebra. We replace this matrix
algebra embedding with an embedding into the algebra of dual quaternions.
Unlike the matrix algebra embedding used by [2], the algebra of dual
quaternions is much closer to the structure of $\mathrm{SE}(3)$, in a sense we
explain in Section 2.4. Two recent advances in dual quaternion linear algebra
were a spectral theorem for matrices of dual quaternions [18] and a power
iteration capable of approximating its spectra [7]. These two results allow us
to develop an elegant spectral synchronization method. The algebraic context
eliminates the gap between the synchronization problem and the eigenproblem,
at least in the absence of measurement noise. In addition, the rounding step
itself stems directly from the algebraic relationship between elements of the
algebra itself and the set on which $\mathrm{SE}(3)$ is represented. In
addition, it is computationally simpler than the rounding procedure of [2].

The structure of this paper is as follows. We begin in Section 2 with a survey
of the necessary background material. Among other things, we define the
algebra of dual quaternions, matrix algebras with dual quaternion entries and
their properties. In Section 3, we delve deeper into synchronization problems
and the spectral method. We define the problem rigorously, introduce the
spectral method and conclude by laying out our approach, relying on dual
quaternion embedding of $\mathrm{SE}(3)$. Finally, in Section 4, we
demonstrate empirically that our approach yields comparable results to the
current state-of-the-art spectral method for $\mathrm{SE}(3)$ synchronization
developed by [2]. Thus, we offer a better theoretical foundation tying
$\mathrm{SE}(3)$ synchronization problems with eigenproblems, while still
maintaining the quality of estimation of the current state-of-the-art spectral
method.

##  2 Background: Dual Quaternions and Matrices of Dual Quaternions

We provide a succinct background information on dual quaternions and dual
quaternion matrices. In Section 2.1 and Section 2.2 we construct the dual
quaternions and describe some of their properties. In Section 2.3 we survey
the well known representation of $\mathrm{SO}(3)$ on the algebra of
quaternions and in Section 2.4 we survey the lesser known representation of
$\mathrm{SE}(3)$ on the algebra of dual quaternions. In Section 2.5 we define
the free modules of dual quaternions and algebras of matrices with dual
quaternion elements. This section culminates in the spectral theorem for
matrices of dual quaternions, which was recently proved by [18]. Finally, in
Section 2.6 we survey the power iteration for matrices of dual quaternions,
which was recently developed by [7].

###  2.1 Dual Numbers

The algebra of dual numbers is the set $\mathbb{D}=\left\\{a+b\bm{\epsilon}\
\middle|\ a,b\in\mathbb{R}\right\\}$ with addition and multiplication defined
by

$\displaystyle\left(a_{1}+b_{1}\bm{\epsilon}\right)+\left(a_{2}+b_{2}\bm{\epsilon}\right)$
$\displaystyle=\left(a_{1}+a_{2}\right)+\left(b_{1}+b_{2}\right)\bm{\epsilon}$
(1)
$\displaystyle\left(a_{1}+b_{1}\bm{\epsilon}\right)\left(a_{2}+b_{2}\bm{\epsilon}\right)$
$\displaystyle=a_{1}a_{2}+\left(a_{1}b_{2}+b_{1}a_{2}\right)\bm{\epsilon}.$
(2)

If $a+b\bm{\epsilon}\in\mathbb{D}$, it is convenient to refer to $a$ as the
real coordinate and $b$ as the dual coordinate. It is easy to see from their
definition that the dual numbers are defined analogously to the complex
numbers. Whereas the complex numbers are the algebra over the reals generated
by $1$ and $i$ such that $i^{2}=-1$, the algebra of dual numbers is generated
by $1$ and $\bm{\epsilon}$ such that $\bm{\epsilon}^{2}=0$. This similarity
accounts for the similar properties of the algebras of dual numbers and
complex numbers. Namely, the underlying vector space of both is
$\mathbb{R}^{2}$, addition and multiplication operations of both are
associative and commutative and both algebras have a unit, $1$.

Despite the aforementioned similarities, these two algebras are fundamentally
very different. The algebra of complex numbers is a field, while the algebra
of dual numbers is not. It has zero divisors, i.e., non-zero elements whose
product is zero. Indeed, recall that an element $x$ of an algebra is said to
be nilpotent if there is a positive integer $n$ such that $x^{n}=0$. The only
nilpotent complex number is $0$. The following proposition characterizes the
nilpotent dual numbers, and it is obvious it has many non-zero nilpotents.

######  Proposition 2.1.

An $x=a+b\bm{\epsilon}\in\mathbb{D}$ is nilpotent if and only if $a=0$. Also,
$x^{2}=0$ for every nilpotent.  $\square$

######  Proof.

If $a\neq 0$, it is easy to show that (2) implies that
$x^{n}=a^{n}+\left(\dots\right)\bm{\epsilon}\neq 0$. If $a=0$, then
$x^{2}=b^{2}\bm{\epsilon}^{2}=0$. $\blacksquare$

As the next proposition shows, nilpotent dual numbers are the only dual
numbers which are not invertible.

######  Proposition 2.2.

If $x=a+b\bm{\epsilon}\in\mathbb{D}$, $x$ is invertible if and only it is not
nilpotent. In that case, $x^{-1}=a^{-1}-ba^{-2}\bm{\epsilon}$.  $\square$

######  Proof.

Let $y=c+d\bm{\epsilon}$. From (2) it follows that $xy=1$ if

$ac=1,\qquad ad+bc=0.$

The first equation has a solution if and only if $a\neq 0$. By Proposition
2.1, this holds if and only if $x$ is not nilpotent. The formula for $x^{-1}$
is easily obtained by solving this system of equations when $a\neq 0$.
$\blacksquare$

A final point of analogy between the dual and complex numbers, is that both
admit a square root. Following [17], given $x=a+b\bm{\epsilon}$ and
$y=c+d\bm{\epsilon}$, we write $x>y$ if $a>c$, or $a=c$ and $b>d$. We say a
dual number $x=a+b\bm{\epsilon}\in\mathbb{D}$ is non-negative if $x\geq 0$ and
positive if $x>0$. In [17, Sec. 2], the following definition of a square root
was given:

$\sqrt{x}=\begin{cases}\sqrt{a}+\frac{b}{2\sqrt{a}}\bm{\epsilon}&x\mbox{ is
positive and invertible},\\\ 0&x=0.\end{cases}$ (3)

In all other cases, the square root is undefined. Using this definition, it is
possible to show that $\sqrt{xy}=\sqrt{x}\sqrt{y}$. This multiplicative
identity implies that for any $x=a+b\bm{\epsilon}\in\mathbb{D}$ with $a\neq
0$, we have
$\sqrt{x^{2}}=\left|a\right|+\mathop{\mathrm{sgn}}(a)b\bm{\epsilon}$, where
$\mathop{\mathrm{sgn}}(a)=1$ for $a>0$, zero when $a=0$ and $-1$ when $a<0$.
Such considerations motivated [17] to define the following absolute value on
dual numbers:

$\left|x\right|=\begin{cases}\left|a\right|+\mathop{\mathrm{sgn}}(a)b\bm{\epsilon}&a\neq
0\\\ \left|b\right|\bm{\epsilon}&a=0.\end{cases}$

It has the following properties [17, Theorem 2], which are generalized forms
of the usual absolute value defined on the real line:

######  Theorem 2.3.

For any $x,y\in\mathbb{D}$:

  1. 1.

$\left|x\right|=0$ if and only if $x=0$.

  2. 2.

$\left|x\right|=x$ if $x\geq 0$ and $\left|x\right|>x$ otherwise.

  3. 3.

$\left|x\right|=\sqrt{x^{2}}$ if $x$ is invertible.

  4. 4.

$\left|xy\right|=\left|x\right|\left|y\right|$ for any $x,y\in\mathbb{D}$.

  5. 5.

$\left|x+y\right|\leq\left|x\right|+\left|y\right|$.

$\square$

###  2.2 Dual Quaternions

The algebra of dual quaternions is easiest to define using the algebra of
quaternions. The algebra of quaternions is the set
$\mathbb{H}=\left\\{a+b\mathbf{i}+c\mathbf{j}+d\mathbf{k}\ \middle|\
a,b,c,d\in\mathbb{R}\right\\}$. We typically refer to $b$, $c$ and $d$ as the
$\mathbf{i}$, $\mathbf{j}$ or $\mathbf{k}$ coordinates, respectively. In the
literature, $a$ is sometimes referred to as the real part of the quaternion,
but in order to eliminate confusion with the real and dual parts of a dual
number, we simply refer to it as the first coordinate of the quaternion.
Addition in $\mathbb{H}$ is defined coordinate-wise and multiplication is
defined by the following relations among its generators:

$\mathbf{i}^{2}=\mathbf{j}^{2}=\mathbf{k}^{2}=\mathbf{i}\mathbf{j}\mathbf{k}=-1.$
(4)

As a vector space, $\mathbb{H}\cong\mathbb{R}^{4}$. Also,
$\mathbb{R}\subset\mathbb{H}$ by constraining the $\mathbf{i}$, $\mathbf{j}$
and $\mathbf{k}$ coordinates to zero. The center of algebra, the set of
elements for which multiplication commutes with all other elements of the
algebra, is $\mathbb{R}$. There is an involution on the quaternions, defined
analogously to the complex conjugation,
$q^{*}=a-b\mathbf{i}-c\mathbf{j}-d\mathbf{k}$ for
$q=a+b\mathbf{i}+c\mathbf{j}+d\mathbf{k}$. This involution is referred to as
quaternion conjugation and we say that $q^{*}$ is the conjugate of $q$.
Similarly to the complex norm, there is a norm on the quaternions defined as
$\left|q\right|\coloneqq\sqrt{q^{*}q}=\sqrt{a^{2}+b^{2}+c^{2}+d^{2}}$, which
can be shown to imply $\mathbb{H}\cong\mathbb{R}^{4}$ as a normed vector
space. We note here that $\left|q\right|^{2}=q^{*}q=qq^{*}$, and so the
inverse of every non-zero $q\in\mathbb{H}$ is $\frac{q^{*}}{q^{*}q}$. Overall,
the algebra of quaternions is an involutive normed division algebra.

The algebra of dual quaternions is $\mathbb{DH}=\left\\{a+b\bm{\epsilon}\
\middle|\ a,b\in\mathbb{H}\right\\}$. Essentially, it means a dual quaternion
is a dual number with quaternion coordinates instead of real coordinates. From
this, we immediately see that $\mathbb{D}\subset\mathbb{DH}$ and also that
$\mathbb{H}\subset\mathbb{DH}$, the former by constraining $a,b\in\mathbb{R}$
and the latter by setting $b=0$. Addition and multiplication are still defined
by (1) and (2) with the quaternion binary operations replacing the real ones.
The trivial involution on $\mathbb{D}$, the identity, and quaternion
conjugation, induce an involution on $\mathbb{DH}$,
$x^{*}=a^{*}+b^{*}\bm{\epsilon}$ for $x=a+b\bm{\epsilon}\in\mathbb{DH}$.
Because $\mathbb{D}$ is the center of $\mathbb{DH}$, we can use the usual
notation for division whenever $d=a+b\bm{\epsilon}\in\mathbb{D}$ is invertible
and $x\in\mathbb{DH}$, and so we write

$\frac{x}{d}\coloneqq xd^{-1}=d^{-1}x.$ (5)

As a vector space, $\mathbb{DH}\cong\mathbb{R}^{8}$. We use the same names for
the coordinates we used for the dual numbers. Given
$a+b\bm{\epsilon}\in\mathbb{DH}$, we call $a$ the real coordinate and $b$ the
dual coordinate.

The algebra of dual numbers is a unital algebra, since both $\mathbb{D}$ and
$\mathbb{H}$ are. It is non-commutative, since $\mathbb{H}$ is. It is not a
division algebra, since $\mathbb{D}$ is not. This combination of features set
it apart from both the algebra of quaternions and the algebra of dual numbers.
Despite this, many of their features generalize well to the dual quaternions.
As we did for the dual numbers, we begin by noting that its nilpotents are
characterized in exactly the same way as the nilpotents of the dual numbers.
Indeed, one need only replace $\mathbb{D}$ with $\mathbb{DH}$ in Proposition
2.1 to obtain the proper characterization.

Note here that zero is the only nilpotent in the algebra of quaternions.
Therefore, one can say the first part of Proposition 2.2 holds for
quaternions, namely, that a quaternion is invertible if and only if it is not
nilpotent. We show now that the dual quaternions share this property. Before
that, we prove a lemma pointing out several important features of the
involutive structure of $\mathbb{DH}$.

######  Lemma 2.4.

If $x=a+b\bm{\epsilon}\in\mathbb{DH}$, then
$x^{*}x=\left|a\right|^{2}+\left(ab^{*}+ba^{*}\right)\bm{\epsilon}$ is a dual
number and $x^{*}x=xx^{*}$.  $\square$

######  Proof.

The first equality is easily proved by substituting $x^{*}$ and $x$ into (2).
To prove the result is a dual number, we note first that the norm of a
quaternion is a real number. In addition, $q^{*}+q\in\mathbb{R}$ for every
quaternion $q$ and $\left(ab^{*}\right)^{*}=ba^{*}$, which implies
$ab^{*}+ba^{*}$ is also real. The second identity follows from a direct
calculation. $\blacksquare$

######  Proposition 2.5.

If $x=a+b\bm{\epsilon}\in\mathbb{DH}$, $x$ is invertible if and only if it is
not nilpotent. In that case, $x^{-1}=\frac{x^{*}}{x^{*}x}$.  $\square$

######  Proof.

If $a=0$, we have $xy=bc\bm{\epsilon}\neq 1$ for every
$y=c+d\bm{\epsilon}\in\mathbb{DH}$. Therefore, $x$ is invertible only if
$a\neq 0$, that is, only if $x$ is not nilpotent. If $a\neq 0$, it follows
from Lemma 2.4 that the real coordinate of $x^{*}x$ is positive. Thus, by
Proposition 2.2 $x^{*}x$ is invertible. Finally, taking
$y=\frac{x^{*}}{x^{*}x}$ one obtains that $yx=1$. The equality $xy=1$ follows
easily from the second equality in Lemma 2.4. $\blacksquare$

In [17], absolute value was also defined for dual quaternions. If
$x=a+b\bm{\epsilon}\in\mathbb{DH}$, then

$\left|x\right|=\begin{cases}\left|a\right|+\frac{ab^{*}+ba^{*}}{2\left|a\right|}\bm{\epsilon}&a\neq
0\\\ \left|b\right|\bm{\epsilon}&a=0.\end{cases}$ (6)

It can be readily seen that when $x$ is a dual number, (6) and (3) agree. In
[17, Thm. 4], the following properties of the absolute value of dual
quaternions were proved:

######  Theorem 2.6.

Let $x,y\in\mathbb{DH}$.

  1. 1.

$\left|x\right|$ is a dual number.

  2. 2.

If $x$ is invertible, then $\left|x\right|=\sqrt{qq^{*}}$.

  3. 3.

$\left|x\right|=\left|x^{*}\right|$.

  4. 4.

$\left|x\right|\geq 0$ for all $x$ and $\left|x\right|=0$ if and only if
$x=0$.

  5. 5.

$\left|xy\right|=\left|x\right|\left|y\right|$.

  6. 6.

$\left|x+y\right|\leq\left|x\right|+\left|y\right|$.

$\square$

###  2.3 Representing $\mathrm{SO}(3)$ on the quaternions

The algebra of quaternions, which we surveyed in Section 2.2, has a close
relationship with the special orthogonal group $\mathrm{SO}(3)$, the group of
norm and orientation-preserving linear transformations of the Euclidean space
$\mathbb{R}^{3}$. The subset $\mathbb{H}_{1}\coloneqq\left\\{q\in\mathbb{H}\
\middle|\ \left|q\right|=1\right\\}$ is actually a subgroup of the
multiplicative group of $\mathbb{H}$. This follows easily from the fact
$\left|q\right|^{2}=q^{*}q=qq^{*}$. In particular, this also implies that the
inverse of every $q\in\mathbb{H}_{1}$ is its conjugate $q^{*}$, making the
group structure of $\mathbb{H}_{1}$ closed under involution and dependent on
the involutive structure of the algebra of quaternions. A well known result
states that $\mathbb{H}_{1}$ is a double cover of $\mathrm{SO}(3)$ [8, Sec.
4.9]. We succinctly construct the covering map here. We begin by identifying
$\mathbb{R}^{3}\cong\mathbb{T}$ as vector spaces, where
$\mathbb{T}=\left\\{a\mathbf{i}+b\mathbf{j}+c\mathbf{k}\ \middle|\
a,b,c\in\mathbb{R}\right\\}\subset\mathbb{H}$. Then, for every
$q\in\mathbb{H}_{1}$, define a map $\mathbb{R}^{3}\to\mathbb{R}^{3}$ by
$\varphi(q)(x)=qxq^{*}$, where $x\in\mathbb{R}^{3}$ is treated as a quaternion
in $\mathbb{T}$ via the identification above. We then have the following:

######  Proposition 2.7.

The covering map is a $2$-to-$1$ surjective group homomorphism
$\varphi:\mathbb{H}_{1}\to\mathrm{SO}(3)$, such that
$\varphi^{-1}(g)=\left\\{q,-q\right\\}$ for every $g\in\mathrm{SO}(3)$.
$\square$

This double cover allows one to represent elements of $\mathrm{SO}(3)$ on
$\mathbb{H}_{1}$. More specifically, one can represent $\mathrm{SO}(3)$ on
$\mathbb{H}_{1+}=\left\\{q\in\mathbb{H}_{1}\ \middle|\ q+q^{*}\geq 0\right\\}$
by choosing an appropriate $q\in\varphi^{-1}(g)$.

###  2.4 Representing $\mathrm{SE}(3)$ on the dual quaternions

The special Euclidean group $\mathrm{SE}(3)$ is the group of rigid motions of
$\mathbb{R}^{3}$, i.e., rotations and translations of $\mathbb{R}^{3}$, but
not reflections. It is a semidirect product
$\mathrm{SE}(3)=\mathrm{SO}(3)\ltimes\mathbb{R}^{3}$. Its elements are most
directly represented as pairs of the form
$\left(R,t\right)\in\mathrm{SO}(3)\times\mathbb{R}^{3}$ with the group
operation defined as
$\left(R_{1},t_{1}\right)\circ\left(R_{2},t_{2}\right)=\left(R_{1}R_{2},t_{1}+R_{1}t_{2}\right)$.
Here, $\circ$ can be thought of as the composition of two affine
transformations.

Let $\mathbb{DH}_{1}=\left\\{x\in\mathbb{DH}\ \middle|\ x^{*}x=1\right\\}$ be
the set of unit dual quaternions. Let
$\mathbb{DT}=\left\\{1+\frac{1}{2}t\bm{\epsilon}\ \middle|\
t\in\mathbb{T}\right\\}$, where we defined $\mathbb{T}$ in Section 2.3. Note
that $\mathbb{H}_{1}\subset\mathbb{DH}_{1}$ and
$\mathbb{DT}\subset\mathbb{DH}_{1}$. We state an analogue of Proposition 2.7.
It is a synopsis of [20, Chp. 9] and its proof can be found there.

######  Proposition 2.8.

We have:

  1. 1.

$\mathbb{DH}_{1}=\mathbb{DT}\rtimes\mathbb{H}_{1}$.

  2. 2.

Let $\psi:\mathbb{DH}_{1}\to\mathrm{SE}(3)$ be defined by
$\psi(q,t)(x)=\left(\varphi(q),t\right)$. Here, $\varphi$ is the double cover
defined in Proposition 2.7, $q\in\mathbb{H}_{1}$ and
$1+\frac{1}{2}t\bm{\epsilon}\in\mathbb{DT}$ so $t$ is identified with an
element of $\mathbb{R}^{3}$. Then $\psi$ is a $2$-to-$1$ surjective group
homomorphism such that $\psi^{-1}(g)=\left\\{-x,x\right\\}$ for all
$g\in\mathrm{SE}(3)$.

$\square$

Proposition 2.8 offers a way to represent elements of $\mathrm{SE}(3)$ in much
the same way we represent elements of $\mathrm{SO}(3)$ on the quaternions. We
represent $(R,\mathbf{t})\in\mathrm{SE}(3)$ by $x=qt\in\mathbb{DH}_{1}$, where
$q$ is a unit quaternion with non-negative first coordinate representing the
rotation $R$ and $\mathbf{t}$ is represented by
$t=1+\frac{1}{2}t^{\prime}\bm{\epsilon}$,
$t^{\prime}=t_{1}\mathbf{i}+t_{2}\mathbf{j}+t_{3}\mathbf{k}$. Its action on
$\mathbb{R}^{3}$ can be defined similarly to what we saw in the quaternion
case. Given $\mathbf{s}\in\mathbb{R}^{3}$, let $s=1+s^{\prime}\bm{\epsilon}$,
$s^{\prime}=t_{1}\mathbf{i}+t_{2}\mathbf{j}+t_{3}\mathbf{k}$. Note the absence
of a $\frac{1}{2}$ factor in this embedding of $\mathbb{R}^{3}$ into the dual
quaternions, compared to how the translational part is represented on
$\mathbb{DT}$ in Proposition 2.8. The action of
$(R,\mathbf{t})\in\mathrm{SE}(3)$ on $\mathbf{s}$ is then $s\mapsto xsx^{*}$.
Indeed, we have:

$\displaystyle xsx^{*}$
$\displaystyle=\left(q+\frac{1}{2}t^{\prime}q\bm{\epsilon}\right)\left(1+s^{\prime}\bm{\epsilon}\right)\left(q^{*}+\frac{1}{2}q^{*}t^{\prime*}\bm{\epsilon}\right)$
$\displaystyle=qq^{*}+\left(\frac{1}{2}t^{\prime}qq^{*}+qs^{\prime}q^{*}+\frac{1}{2}qq^{*}t^{\prime*}\right)\bm{\epsilon}$
$\displaystyle=1+\left(qs^{\prime}q^{*}+t^{\prime}\right)\bm{\epsilon}.$

In expanding the products in the second transition we used the fact
$\bm{\epsilon}^{2}=0$, which implied no products of two dual coordinates could
appear in the result. The dual coordinate of the result is exactly the action
of $(R,\mathbf{t})$ on $\mathbf{s}$, because $qs^{\prime}q^{*}$ is the action
of $R$ on $\mathbf{s}$ by Proposition 2.7 and because of the manner in which
we represented $\mathbb{R}^{3}$ on quaternions when we constructed
$t^{\prime}$ and $s^{\prime}$.

[7] proved that it is possible to project an almost arbitrary dual quaternion
onto the unit dual. Their result is stated here as follows:

######  Theorem 2.9.

Let $x=a+b\bm{\epsilon}\in\mathbb{DH}$ be non-zero.

  1. 1.

If $a\neq 0$, then $\frac{q}{\left|q\right|}$ is a unit dual quaternion
solving

$\min_{v\in\mathbb{DH}_{1}}\left|v-x\right|^{2}.$ (7)

  2. 2.

If $a=0$, then any $q^{\prime}=a^{\prime}+b^{\prime}\bm{\epsilon}$ such that
$a^{\prime}=\frac{b}{\left|b\right|}$ and $b^{*}b^{\prime}+b^{\prime*}b=0$
solves (7).

$\square$

This theorem exposes an aspect of the close tie between $\mathrm{SE}(3)$ and
the algebra of dual quaternions. We focus on its first part. It can be
interpreted as the idea that every invertible dual quaternion is essentially a
unit dual quaternion multiplied by a dual number. Thus, in a sense, the
multiplicative structure of the algebra of dual quaternions is almost entirely
generated by the group of unit dual quaternions. This property has a geometric
interpretation via the absolute value function. Namely, dividing a dual
quaternion by its absolute value yields a solution to the optimization problem
(7), a sort of projection function. This function itself is defined via the
dual quaternion absolute value (6), which itself intimately related to the
algebraic structures on the algebra of dual quaternions as indicated in
Theorem 2.6.

Finally, we refer the interested reader to Appendix A, where we compare
various representations of $\mathrm{SE}(3)$, focusing on features which are
perhaps most salient in applied work.

###  2.5 Matrices of Dual Quaternions and Their Spectral Decomposition

Modules are an extensively studied generalization of the notion of a vector
space to vectors and matrices with entries from an arbitrary algebra. See [10]
for an introduction to module theory. Here, we provide a synopsis of the
necessary information. A (right-)module $\mathbb{M}$ over an algebra
$\mathbb{A}$ is a commutative group $\left(\mathbb{M},+\right)$ along with a
map $\mathbb{M}\times\mathbb{A}\to\mathbb{M}$, $(m,x)\mapsto m\cdot x$, which
satisfies the following properties. First, it is distributive in the sense
that $m\cdot(x+y)=m\cdot x+m\cdot y$ and $(m_{1}+m_{2})\cdot x=m_{1}\cdot
x+m_{2}\cdot x$. Second, the operation is associative, $\left(m\cdot
x\right)\cdot y=m\cdot(xy)$. We often refer to this map as the action of
$\mathbb{A}$ on $\mathbb{M}$ and often omit the multiplication sign.
Oversimplifying to an extent, a module can be thought of as a vector space in
which the underlying field was replaced by an arbitrary algebra.

We focus on two types of free modules of the algebra of dual quaternions,
$\mathbb{DH}^{n}$ and $\mathbb{DH}^{n\times n}$. Given a positive integer $n$,
the free $\mathbb{DH}$-module is
$\mathbb{DH}^{n}=\left\\{\mathbf{m}=\left(m_{1},\dots,m_{n}\right)^{\top}\
\middle|\ m_{j}\in\mathbb{DH},j=1,\dots,n\right\\}$. It is acted upon by
$\mathbb{DH}$ via entry-wise right-multiplication, i.e.,
$\left(\mathbf{m}x\right)_{j}=m_{j}x$. Addition is defined entry-wise.
Moreover, $\mathbb{DH}^{n\times n}$ can be thought of as the module of all
$n\times n$ matrices of dual quaternions. As an $\mathbb{DH}$-module, one can
identify it with $\mathbb{DH}^{n^{2}}$, and so addition is also performed
entry-wise and so is right-multiplication by a dual quaternion. However, it
actually is an algebra, not just a module, with the multiplication of matrices
defined in the familiar way. Similarly, one can define the product
$\mathbf{A}\mathbf{x}$ of a matrix $\mathbf{A}\in\mathbb{DH}^{n\times n}$ and
$\mathbf{x}\in\mathbb{DH}^{n}$ in the usual way. It is instructive to think of
$\mathbf{A}$ as a $\mathbb{DH}$-linear operator on $\mathbb{DH}^{n}$ in the
sense that
$\mathbf{A}\left(\mathbf{x}a+\mathbf{y}b\right)=\left(\mathbf{A}\mathbf{x}\right)a+\left(\mathbf{A}\mathbf{y}\right)b$
for any $\mathbf{x},\mathbf{y}\in\mathbb{DH}^{n}$ and $a,b\in\mathbb{DH}$.

Several types of real and complex matrices have dual quaternions counterparts.
The conjugate transpose of a matrix $\mathbf{A}\in\mathbb{DH}^{n\times n}$ is
$\left(\mathbf{A}^{*}\right)_{ij}=\mathbf{A}_{ji}^{*}$. This can easily be
shown to be an involution on $\mathbb{DH}^{n\times n}$. We say a matrix
$\mathbf{A}\in\mathbb{DH}^{n\times n}$ is Hermitian if
$\mathbf{A}=\mathbf{A}^{*}$. It is unitary if
$\mathbf{A}^{*}\mathbf{A}=\mathbf{A}\mathbf{A}^{*}=\mathbf{I}_{n}$, where
$\mathbf{I}_{n}$ is the identity matrix, which is defined in usual way.

Deepening the analogy with real and complex matrices, a notion of eigenvector
and eigenvalue exists for matrices of dual quaternions. We say
$\lambda\in\mathbb{DH}$ is a (right-)eigenvalue of the matrix
$\mathbf{A}\in\mathbb{DH}^{n\times n}$ if there is
$\mathbf{x}\in\mathbb{DH}^{n}$ such that
$\mathbf{A}\mathbf{x}=\mathbf{x}\lambda$. As the name suggests, the non-
commutativity of $\mathbb{DH}$ means one can also define a left-eigenvalue of
a matrix of dual quaternions, though we will not be presenting any results on
these. Whenever we speak of eigenvalues and eigenvectors of dual quaternion
matrices we will be referring to right-eigenvalues and right-eigenvectors.

We are now ready to state the spectral theorem for Hermitian matrices of dual
quaternions [18, Thm. 4.1]:

######  Theorem 2.10.

Let $\mathbf{A}\in\mathbb{DH}^{n\times n}$. If $\mathbf{A}$ is Hermitian, then
there are a unitary $\mathbf{U}\in\mathbb{DH}^{n\times n}$ and a diagonal
$\bm{\Sigma}\in\mathbb{DH}^{n\times n}$ with dual number elements such that
$\mathbf{A}=\mathbf{U}\bm{\Sigma}\mathbf{U}^{*}$. The diagonal elements of
$\bm{\Sigma}$ have the form
$\sigma_{j}=\alpha_{j}+\beta_{j}\bm{\epsilon}\in\mathbb{D}$ with
$\alpha_{1}\geq\alpha_{2}\geq\dots\geq\alpha_{n}$. Here, $\sigma_{j}$ is the
eigenvalue of $\mathbf{A}$ corresponding to the eigenvector $\mathbf{u}_{j}$,
the $j$th column of $\mathbf{U}$.  $\square$

This theorem essentially states that Hermitian matrices of dual quaternions
have a full set of eigenvectors. Furthermore, in the dual quaternion case, as
in the complex case, the eigenvalues turn out to be self-adjoint, that is,
they satisfy $\sigma^{*}=\sigma$, with respect to the appropriate involution.
This highlights the striking similarities between this theorem and the well-
known spectral theorem of complex Hermitian matrices.

###  2.6 Power Iteration for Hermitian Matrices of Dual Quaternion

In a recent paper, [7] developed a dual quaternion analog of the power
iteration, capable of approximating the top eigenvalue of a Hermitian dual
quaternion matrix and its corresponding eigenvalue. We clarify below the sense
in which an eigenvalue is the top eigenvalue. Let
$\mathbf{A}\in\mathbb{DH}^{n\times n}$ be a Hermitian matrix of dual
quaternions. Given some initializer $\mathbf{v}^{{0}}\in\mathbb{DH}^{n}$, the
power iteration defined in [7] is

$\mathbf{y}^{(k)}=\mathbf{A}\mathbf{v}^{(k-1)},\quad\lambda^{(k-1)}=\left(\mathbf{v}^{(k-1)}\right)^{*}\mathbf{y}^{(k)},\quad\mathbf{v}^{(k)}=\frac{\mathbf{y}^{(k)}}{\left\|\mathbf{y}^{(k)}\right\|_{2}}.$
(8)

Here, the dual quaternion norm used is defined as follows:

$\left\|\mathbf{x}\right\|_{2}=\begin{cases}\sqrt{\sum_{j=1}^{n}\left|x_{j}^{\prime}\right|^{2}}\bm{\epsilon}&\mathbf{x}=\mathbf{x}^{\prime}\bm{\epsilon},\mathbf{x}^{\prime}\in\mathbb{H}^{n},\\\
\sqrt{\sum_{j=1}^{n}\left|x_{j}\right|^{2}}&\mbox{otherwise}.\end{cases}$ (9)

For simplicity, we refer to $\left\|\mathbf{x}\right\|_{2}$ as a norm, even
though it is not a norm in the usual linear-algebraic sense. Several addition
definitions are required. Following [7], we write
$c_{k}=\tilde{O}_{D}\left(s^{k}\right)$ for some $s<1$ if
$c_{k}=a_{k}+b_{k}\bm{\epsilon}\in\mathbb{D}$ and for some polynomial $h(k)$
we have $a_{k}=O\left(s^{k}h(k)\right)$ and $b_{k}=O\left(s^{k}h(k)\right)$.
[7] proved the following result:

######  Theorem 2.11 (Theorem 4.1 of [7]).

Let $\mathbf{u}_{1},\dots,\mathbf{u}_{n}$ be the eigenvectors of $\mathbf{A}$
ordered so that their corresponding eigenvalues
$\sigma_{j}=\alpha_{j}+\beta_{j}\bm{\epsilon}\in\mathbb{D}$ satisfy
$\left|\alpha_{1}\right|>\left|\alpha_{2}\right|\geq\dots\geq\left|\alpha_{n}\right|$.
If $\mathbf{v}^{(0)}=\sum_{j=1}^{n}\mathbf{u}_{j}\gamma_{j}$ with
$\gamma_{j}\in\mathbb{DH}$ such that $\gamma_{1}$ has a non-zero real
coordinate, then the sequence defined by (8) satisfies

$\mathbf{v}^{(k)}=\mathbf{u}_{1}c\left(1+\tilde{O}_{D}\left(\left|\frac{\alpha_{2}}{\alpha_{1}}\right|^{k}\right)\right),\quad\lambda^{(k)}=\sigma_{1}\left(1+\tilde{O}_{D}\left(\left|\frac{\alpha_{2}}{\alpha_{1}}\right|^{2k}\right)\right),$

where
$c=\mathop{\mathrm{sgn}}(\alpha_{1})\frac{\gamma_{1}}{\left|\gamma_{1}\right|}$.
$\square$

This theorem essentially shows that the power iteration (8) converges to
$\mathbf{u}_{1}$ and its corresponding eigenvalue. At every iteration,
$\mathbf{v}^{(k)}$ and $\lambda^{(k)}$ are essentially the desired values
multiplied by some dual number, which approaches $1$ at an exponential rate.
In this and in the general form of the iteration (8), the dual quaternion
power iteration is strikingly similar to the well-established power iteration
for real and complex matrices [25, Lecture 27].

###  2.7 Isometries of eigenspaces of matrices of dual quaternions

At this point, we have established the background material and notation
required to point out two important facts. First, the eigenspaces of a
Hermitian matrix of dual quaternion are invariant to the action of unit dual
quaternions. Indeed, if $x\in\mathbb{DH}$ and $\mathbf{x}\in\mathbb{DH}^{n}$
is an eigenvector of $\mathbf{A}\in\mathbb{DH}^{n\times n}$ corresponding to
eigenvalue $\lambda\in\mathbb{D}$, then

$\mathbf{A}\left(\mathbf{x}x\right)=\mathbf{x}\lambda
x=\left(\mathbf{x}x\right)\lambda.$

Therefore, $\mathbf{x}x$ is also an eigenvector corresponding to eigenvalue
$\lambda$. The last transition follows, because the $x$ and $\lambda$ commute,
since the latter is in the center of $\mathbb{DH}$.

The second fact relates to the isometries of $\mathbb{DH}^{n}$ with respect to
the dual quaternion norm defined in (9). Given $\mathbf{x}\in\mathbb{DH}^{n}$
and an invertible $x\in\mathbb{DH}$, we have

$\left\|\mathbf{x}x\right\|_{2}=\left\|\mathbf{x}\right\|_{2}\left|x\right|.$

This can be proved by considering both cases of (9) separately and using
Theorem 2.6. Therefore,
$\left\|\mathbf{x}\right\|=\left\|\mathbf{x}x\right\|_{2}$ if and only
$\left|x\right|=1$, which is equivalent to $x^{*}x=1$, i.e., $x$ is a unit
dual quaternion. Therefore, the unit dual quaternions are the isometries of a
free module of dual quaternions with respect to the norm structure induced by
(9).

Combining these two facts together, we conclude that for a fixed unit dual
number $q$, the $\mathbb{DH}\to\mathbb{DH}$ map $\mathbf{x}\mapsto\mathbf{x}q$
has two important properties. First, it preserves the norm (9). Second, it
maps eigenvectors of Hermitian matrices of dual quaternions to eigenvectors
corresponding to the same eigenvalue. These two properties play a key role in
the spectral approach to synchronization we develop in the next section.

##  3 The Spectral Approach to Synchronization Problems via Dual Quaternions

In this section, we apply the dual quaternion representation of
$\mathrm{SE}(3)$ to the problem of $\mathrm{SE}(3)$ synchronization. In
Section 3.1, we describe group synchronization problems and noise types which
were considered in the literature. In Section 3.2, we describe the spectral
method, a prevalent solution to group synchronization problems. As we describe
in Section 3.3, this approach can be generalized to the dual quaternions
algebra and therefore can be used to address $\mathrm{SE}(3)$ synchronization
problems. We dedicate Section 4 to numerical experiments demonstrating that
our proposed method indeed works on simulated data.

###  3.1 Group Synchronization: Problem Statement

Let $G$ be a group. Let $g_{1},\dots,g_{n}$ be elements of $G$ and let
$g_{ij}=g_{i}g_{j}^{-1}$ be their ratios, $1\leq i,j\leq n$. A synchronization
problem is an estimation problem in which one attempts to estimate
$\left\\{g_{i}\ \middle|\ 1\leq i\leq n\right\\}$, the absolute group
elements, from their ratios $\left\\{g_{ij}\ \middle|\ 1\leq i<j\leq
n\right\\}$. Often, the clean ratios are perturbed by some sort of noise.
Because $g_{1}g,\dots,g_{n}g$ generate the same set of clean measurements for
every arbitrary $g\in G$, we can only hope to estimate $g_{1},\dots,g_{n}$ up
to a global right-multiplication by an arbitrary element of $G$.

In order to describe the typical noise models, it is convenient to represent
the group faithfully as some subgroup of the general linear group, the group
of invertible matrices. Thus, we assume in this section that one has an
injective homomorphism $\rho:G\to\mathrm{GL}_{k}(\mathbb{F})$, with
$\mathbb{F}=\mathbb{R}$ or $\mathbb{F}=\mathbb{C}$. The absolute group
elements and their ratios are mapped onto $\mathrm{GL}_{k}(\mathbb{F})$ via
$\rho$ in a consistent manner. Namely,
$\rho(g_{ij})=\rho(g_{i})\rho(g_{j})^{-1}$. The elements of $G$ are
represented by elements of $\mathbb{F}^{k\times k}$, the $k\times k$ matrices
with entries in $\mathbb{F}$. We refer to $\mathbb{F}^{k\times k}$ as the
representation space and to the image of $\rho$ as the representing subspace.
Throughout this subsection, we suppress the homomorphism $\rho$ and assume the
absolute group elements and their ratios are already faithfully represented in
some matrix algebra.

Given a group represented in this manner, three kinds of noise sources are
usually considered in the literature. First, pertrubative noise can be applied
to each clean ratio. This has two forms. Multiplicative noise perturbs the
clean ratio, while still remaining in the group, so that we measure
$\widehat{g}_{ij}=g_{ij}\varepsilon_{i,j}$, with $\varepsilon_{i,j}\in G$.
Additive noise perturbs the clean ratio within the representation space, so
that we measure $\widehat{g}_{ij}=g_{ij}+\varepsilon_{i,j}$, with
$\varepsilon_{i,j}\in\mathbb{F}^{k\times k}$. We here assume that pertrubative
noise is either multiplicative for all ratios, or additive for all ratios.

The last two kinds of noise are best viewed as applied to a set of
measurements. This set of measurements may be assumed to be either a complete
set of clean measurements $\left\\{g_{ij}\ \middle|\ 1\leq i<j\leq
n\right\\}$, a measurement set afflicted with pertrubative noise,
$\left\\{\widetilde{g}_{ij}\ \middle|\ 1\leq i<j\leq n\right\\}$, or a subset
of one of these. Every set of measurements can be envisaged as an undirected
graph of order $n$, in which each vertex is labeled with an absolute group
element and the edges correspond to the measurements in the set. See Figure 1
for an example.

The last two kinds of noise are best viewed as acting on the measurement
graph. The first, which we term selection noise, merely removes a subset of
the edges of the measurement graph. The second, which is often called
corruptive or adversarial noise, replaces the labels of a subset of edges with
a randomly generated labels which are independent from the clean group ratios.
In both kinds of noise, the affected subset of edges may be chosen randomly or
deterministically. The measurement graph has a subgraph formed by edges which
were not corrupted. We assume that this subgraph is connected, regardless of
the method used to choose the subset of edges affected by selection or
corruptive noise. Figure 1 shows an example of a measurement graph with
corruptive noise.

$g_{0}$$g_{1}$$g_{2}$$g_{3}$$g_{4}$$g_{5}$$g_{6}$$g_{7}$$g_{8}$$g_{9}$$g_{01}$$g_{03}$$g_{04}$$g_{05}$$g_{14}$$g_{25}$$g_{26}$$g_{29}$$g_{34}$$g_{37}$$g_{45}$$g_{48}$$g_{49}$$g_{57}$$g_{58}$$g_{59}$$g_{69}$
Figure 1: An example synchronization measurement graph with $10$ absolute
group elements, labeled from $0$ to $9$. Vertices appear in blue circles.
Edges are labeled with ratio measurements. Edges of the subgraph of non-
corrupted measurements are dyed green. Edge labels of this subgraph can be
thought of as either clean or afflicted with perturbative noise. In a
synchronization problem, the goal is to estimate the absolute group elements
in a manner that is as consistent as possible with the measurements of their
ratios.

All combinations of the three kinds of noise were considered in the
literature, both in numerical investigations of estimation methods and in
their theoretical analysis [2, 5, 6, 12, 13, 19, 22, 26]. The literature cited
provides a mere illustrative selection.

###  3.2 Group Synchronization via the Spectral Method

Let $g_{1},\dots,g_{n}$ be elements of a group $G$. We emphasize at the outset
of this subsection that all elements of $G$ are faithfully represented within
some matrix algebra $\mathbb{F}^{k\times k}$. Whenever perturbative noise is
considered, it is always assumed to be multiplicative.

The spectral method relates synchronization problems to eigenproblems on a
matrix, which is essentially a generalized adjacency matrix of the
synchronization graph. Let $\mathbf{Y}\in\mathbb{F}^{nk\times nk}$ be a block
matrix such that the $(i,j)$th block $\mathbf{Y}_{ij}$, $i<j$, is the
measurement of the ratio $g_{i}g_{j}^{-1}$. If the measurement is clean,
perturbed (multiplicatively) or corrupted, we assign
$\mathbf{Y}_{ji}=\mathbf{Y}_{ij}^{-1}$. If the measurement is missing, we set
$\mathbf{Y}_{ij}=\mathbf{Y}_{ji}=\mathbf{0}_{k\times k}$. The diagonal blocks
are $\mathbf{Y}_{ii}=\mathbf{I}_{k}$ for $i=1,\dots,n$. Essentially, the block
on the $i$th row of blocks and $j$th column of blocks is a measurement of the
ratio of $g_{i}g_{j}^{-1}$. Since these measurements label the edges of the
synchronization graph, this is a generalization of the notion of the adjacency
matrix of a graph.

In the absence of noise, it is evident that
$\mathbf{Y}=\mathbf{g}\mathbf{g}^{-1}$. Here,
$\mathbf{g}\in\mathbb{F}^{nk\times k}$ is the column block matrix with $g_{i}$
as its $i$th block and $\mathbf{g}^{-1}\in\mathbb{F}^{k\times nk}$ is the row
block matrix with $g_{i}^{-1}$ as its $i$th block. It is immediate that
$\mathbf{Y}\mathbf{g}=n\mathbf{g}$ and that $n$ is the only non-zero
eigenvalue of $\mathbf{Y}$. Thus, the columns of $\mathbf{g}$ form a basis of
the eigenspace of $\mathbf{Y}$ associated with $n$. Furthermore, the kernel of
$\mathbf{Y}$ is the orthogonal complement of the space spanned by the columns
of $\left(\mathbf{g}^{-1}\right)^{\top}\in\mathbb{F}^{nk\times k}$. Thus,
$\mathbb{F}^{n}$ is the direct sum of the kernel of $\mathbf{Y}$ and the
eigenspace of $\mathbf{Y}$ associated with $n$. Overall, in the absence of
noise, the eigenspaces structure of the measurement matrix $\mathbf{Y}$
contains information on $\mathbf{g}$, and therefore contains information on
the absolute group elements.

In the presence of noise, the measurement matrix $\mathbf{Y}$ can be viewed as
a disrupted form of an hypothetical, clean measurement matrix of the form we
described in the previous paragraph. The eigenspaces of the measurement matrix
can also be viewed as a disruptions of the eigenspaces of this hypothetical
matrix. If the disruption is mild enough, the eigenspaces of the top $k$
eigenvalues of $\mathbf{Y}$ is expected to preserve enough of the information
of the eigenspace associated with the eigenvalue $n$ of this hypothetical
matrix. By projecting these top eigenvectors of the measurement matrix onto
the representation of $G$, it is possible to obtain an estimate of the
absolute group elements. This step may also somewhat alleviate the disruption
of the eigenspace caused by the noise. The resulting estimation method can be
formulated as a two step procedure:

  1. 1.

Find a set of unit eigenvectors of $\mathbf{Y}$ associated with its largest
$k$ eigenvectors. These can be placed in a matrix
$\mathbf{U}\in\mathbb{R}^{nk\times k}$.

  2. 2.

Project these eigenvectors onto $G$.

Implementing this two step method is fairly straightforward using existing
numerical algebra libraries. The first step is can be easily implemented using
all modern numerical eigenproblem solvers. The second step, often referred to
as “rounding” in the synchronization literature [19, 22], can be more
involved, depending largely on $G$ and its chosen representation. A few
examples will serve to illustrate the range in the complexity of this task.

######  Example 3.1.

If $G=\mathrm{SO}(2)$ is represented as unit complex numbers, the result of
the first step is a unit vector of complex numbers. Simply dividing each of
its entries by its complex norm yields a vector of unit complex numbers. This
is possible, provided the disruption caused by the noise is mild enough so as
to ensure all entries of the eigenvector are non-zero. This rounding procedure
was used to great effect in $\mathrm{SO}(2)$ synchronization, e.g. [16, 22].
$\square$

######  Example 3.2.

If $G=\mathrm{SO}(k)$ is represented as real orthogonal $k\times k$ matrices,
the result of the first step is a $nk\times k$ matrix which can be treated as
a column block matrix with $k\times k$ blocks. The projection is carried out
block-wise. The SVD of each block is calculated, yielding a decomposition
$\mathbf{B}=\mathbf{U}\Sigma\mathbf{V}^{\top}$, where $\mathbf{U}$ and
$\mathbf{V}$ are orthogonal matrices and $\Sigma$ is a diagonal matrix. The
rounding step is completed by replacing every block with the image of the map
$\mathbf{B}\mapsto\mathbf{U}\mathrm{diag}\left(1,\dots,1,\det\left(\mathbf{U}\mathbf{V}^{\top}\right)\right)\mathbf{V}^{\top}$.
$\square$

######  Example 3.3.

In [2], $G=\mathrm{SE}(3)$ was represented on the real $4\times 4$ matrices of
the form

$\left[\begin{matrix}\mathbf{R}&\mathbf{t}\\\
\mathbf{0}^{\top}&1\end{matrix}\right].$ (10)

This matrix represents $\left(R,\mathbf{t}\right)\in\mathrm{SE}(3)$, where $R$
is a rotation represented as $\mathbf{R}$, a real $3\times 3$ orthogonal
matrix with determinant of $1$. Consider the matrix
$\mathbf{V}\in\mathbb{R}^{4n\times 4}$, the columns of which are the top
eigenvectors of the measurement matrix which were calculated in the first
step. The rounding procedure considered by [2] begins by extracting every
fourth row of $\mathbf{V}$. Denoting the resulting $\mathbb{R}^{n\times 4}$
matrix by $\mathbf{V}_{4}$, all solutions of
$\mathbf{V}_{4}\mathbf{u}=\mathbf{0}$ are found by finding an orthonormal
basis $\mathbf{u}_{1},\mathbf{u}_{2},\mathbf{u}_{3}$ for the kernel of
$\mathbf{V}_{4}$. A unit vector solution for
$\mathbf{V}_{4}\mathbf{u}_{4}=\left(1,\dots,1\right)^{\top}$ is also found.
Since nothing guarantees that solutions to these equations even exist, they
are approximated in the least squares sense. Let
$\mathbf{U}\in\mathbb{R}^{4\times 4}$ be the matrix with columns
$\mathbf{u}_{1},\mathbf{u}_{2},\mathbf{u}_{3},\mathbf{u}_{4}$. Let
$\mathbf{V}^{\prime}=\mathbf{V}\mathbf{U}$ and substitute every forth row of
the resulting matrix with $\left(0,0,0,1\right)$. Now, each of the $4\times 4$
blocks of $\mathbf{V}^{\prime}$ has almost the form (10). If this matrix is
complex, zero out the imaginary part of every entry. Finally, the top $3\times
3$ submatrix of every block is projected onto $\mathrm{SO}(3)$ by utilizing
its SVD in the manner described in Example 3.2.  $\square$

Non-linear transformations are employed in all three examples. However, the
simplicity of the rounding step in Example 3.1 for $\mathrm{SO}(2)$ is
contrasted by the multi-step, complicated procedure shown in the Example 3.3
for $\mathrm{SE}(3)$, the focus of this paper. This difference stems from
inherent features of the representation of the group. The group
$\mathrm{SO}(2)$ is embedded within the complex plane in a way which respects
the algebraic properties of the representation space. First, the norm of a
complex number is directly related to the conjugation operation, i.e.,
$\left|z\right|=\sqrt{zz^{*}}$ for any $z\in\mathbb{C}$. The submanifold of
the complex plane into which $\mathrm{SO}(2)$ is embedded, the unit circle, is
entirely defined in terms of this conjugation operation, i.e.,
$\mathbb{T}=\left\\{z\in\mathbb{C}\ \middle|\ zz^{*}=1\right\\}$. Second, the
embedding takes into consideration the $*$-algebra structure of the complex
plane. The group inverse is the conjugation operation.

These features do not hold for the matrix representation (10) of
$\mathrm{SE}(3)$. As we discuss in greater detail in Appendix A, this
representation merely embeds $\mathrm{SE}(3)$ within the multiplicative group
of the matrix algebra of real $4\times 4$ matrices. It does not rely or
respect the other algebraic structures of the representation space. Merely
transposing (10) almost always yields a matrix which does not represent an
element of $\mathrm{SE}(3)$.

We now discuss the nature of the rounding procedure. On the surface, all it
does is ensure that the output of the spectral method are elements of the
group, but a closer look reveals a more complicated situation. In the
noiseless case, which is simplest, we saw that the measurement matrix has a
single non-zero eigenvalue. We consider now the linear isometries of its
eigenspace with respect to the standard Euclidean norm. These isometries form
a compact group. Numerical linear algebra tools ensure we shall obtain unit
eigenvectors of the measurement matrix. These may be $\frac{1}{n}\mathbf{g}$,
where the $\frac{1}{n}$ term ensures these columns are unit eigenvectors.
However, more often they are expected to be $\frac{1}{n}\mathbf{g}\mathbf{S}$,
where $\mathbf{S}$ is an isometry of the eigenspace of the non-zero eigenvalue
of the measurement matrix.

Let us consider the three examples above. In $\mathrm{SO}(2)$ synchronization
(Example 3.1), the group of isometries is $\mathrm{SO}(2)$ itself, represented
by unit complex numbers. Indeed, since the eigenspace is one-dimensional,
every isometry has the form $\mathbf{x}\mapsto\mathbf{x}x$ for
$x\in\mathbb{C}$. By substituting $\mathbf{x}x$ into the standard Euclidean
norm, it is easy to show that it is an isometry if and only if
$\left\|\mathbf{x}x\right\|=\left\|x\right\|\left|x\right|$, which holds if
and only if $\left|x\right|=1$. Therefore, $x\in\mathrm{SO}(2)$. It follows
that in the noiseless case, the spectral method recovers the absolute group
elements up to a right-multiplication by an element of $\mathrm{SO}(2)$. And
so, in the presence of noise, the rounding step alleviates a disruption in the
eigenspace structure and nothing more.

This is not the case in the other two examples. There, the rounding has to
perform other tasks, which are unrelated to the disruption of the eigenspaces
caused by the noise and will be required even in its absence. Again, it is
instructive to consider the noiseless case first. In $\mathrm{SO}(k)$
synchronization (Example 3.2), the non-zero eigenspace is a $k$-dimensional
subspace of $\mathbb{R}^{n}$ and its isometry group with respect to the
standard Euclidean norm on $\mathbb{R}^{n}$ is $\mathrm{O}(k)$, the group of
orthogonal transformations of $\mathbb{R}^{k}$. The group $\mathrm{SO}(k)$ is
a proper subgroup of $\mathrm{O}(k)$ and so the unit eigenvectors in the
eigenspace can be separated into two disjoint populations. The first
population is obtained by applying $\mathrm{SO}(k)$ to the columns of
$\frac{1}{n}\mathbf{g}$ from the right. The second can be obtained by applying
elements of $\mathrm{O}(k)\setminus\mathrm{SO}(k)$. This means that being a
solution to the synchronization problem implies being a basis of an eigenspace
of the non-zero eigenvalue of the measurement matrix, but the converse does
not hold. We refer to this phenomena as the eigenspace-synchronization gap.
Therefore, in the presence of noise, the rounding procedure performs at least
the following two tasks. It alleviates the disruption to the eigenspace
structure and ensures that the resulting estimate of the absolute group
elements is indeed the absolute group elements up to a multiplication by an
arbitrary element of $G$ from the right. The latter can no longer be taken for
granted.

These issues are exacerbated considerably in $\mathrm{SE}(3)$ synchronization
(Example 3.3), where the group is non-compact. There, even in the absence of
noise, the group $\mathrm{SE}(3)$ is not even a subgroup of the isometries of
the eigenspace. This is the case because the group of isometries is compact,
while $\mathrm{SE}(3)$ is not. In this case, the eigenspace-synchronization
gap is not so much a gap as an abyss. The domain of the rounding procedure is
a compact manifold, matrices formed with four unit eigenvectors as columns.
Its codomain is a non-compact manifold, block matrices with blocks of the form
(10). The rounding procedure maps this compact domain to this non-compact
codomain. Thus, even in the absence of noise, for $\mathrm{SE}(3)$
synchronization it is another large step away from the neat correspondence
exhibited in $\mathrm{SO}(2)$ synchronization (Example 3.1) between
eigenvectors of the measurement matrix and estimates of the absolute group
elements. In the presence of noise, it does a great deal more than handling
the eigenspace disruption.

In closing this subsection, we digress to note an important distinction
between the way we introduced the spectral method and the way it is often
discussed in the literature. In the literature on synchronization, the
relationship between the eigenvectors of the noisy measurement matrix and an
estimate of the absolute group elements is often arrived at using a
optimization terminology. For instance, the initial goal of both [2] and [22]
is an estimate the absolute group elements obtained by solving a certain least
squares problem over $\widehat{\mathbf{g}}\in G^{n}$. Here, $G^{n}$ is the set
of all column block matrices with blocks representing elements of $G$. Since
the domain of the problem is non-convex, this is a challenging optimization
problem to solve in practice. This constraint is therefore changed to all
matrices satisfying
$\widehat{\mathbf{g}}^{*}\widehat{\mathbf{g}}=n\mathbf{I}_{k}$. In the case of
[22], which worked on $\mathrm{SO}(2)$ represented on the unit complex
numbers, this change in the constraint is a relaxation of the constraint of
the original least squares problem. That is, the feasible set of the original
problem is replaced by a larger set. However, this change is not a relaxation
of a constraint in [2], which worked on $\mathrm{SE}(3)$ with the matrix
representation (10). Regardless of that, in both cases, the new least squares
problem turns out to be easily solved by finding the eigenvectors of the
measurement matrix.

We note this here merely to point out that the optimization perspective
provides a useful heuristic for deriving practically useful estimation methods
for synchronization problems. However, it does not offer an immediate way to
prove when and why these methods work. We here treat the noisy measurement
matrix as a disrupted version of a clean, complete measurement matrix, and
seek to approximate the eigenspaces of the latter using the eigenspaces of the
former. In the optimization perspective, the very same eigenproblem is
considered as a relaxed optimization problem, which one hopes approximates the
solution of the non-convex problem. This is a difference without much
consequence to the governing mathematics of the spectral method. Regardless of
the heuristic used to derive the method, considerable effort is required to
come up with and prove theoretical guarantees on the performance of the
spectral method. Indeed, there is a rich literature of formal
characterizations of when and how solutions of the eigenproblem provide good
estimates of the absolute orientations, e.g., [14, 15, 19, 22] with many
mathematical tools, including random matrix theory and perturbation theory,
being brought to bear on these questions.

###  3.3 A Spectral Approach to $\mathrm{SE}(3)$ Synchronization via Dual
Quaternion Representation

In Section 3.2, we discussed the contrast between the rounding step in
$\mathrm{SO}(2)$ and $\mathrm{SE}(3)$ synchronization in Example 3.1 and
Example 3.3. We identified two types of differences between them. First, their
respective representations have different features. For instance, the
representation of $\mathrm{SO}(2)$ agreed with involutive algebraic structure
of the space it was embedded in, whereas the representation of
$\mathrm{SE}(3)$ did not. Second, in a sense, the rounding does more in the
$\mathrm{SE}(3)$ case than in the $\mathrm{SO}(2)$ case. We now utilize the
material we surveyed in Section 2 to develop a spectral synchronization method
for $\mathrm{SE}(3)$, which is more similar to the spectral method for
$\mathrm{SO}(2)$ in both these respects. We note in passing that the
quaternions and the dual quaternions were used in the past to address
synchronization problems [9, 24], but this is the first time an analog of the
spectral method for synchronization was developed using dual quaternions.

All the necessary components of the spectral method are present over the dual
quaternions. Elements of $\mathrm{SE}(3)$ are represented as unit dual
quaternions, as we surveyed in Section 2.4. This representation agrees with
both the multiplication operation of the algebra and its involution, since the
dual quaternion conjugate of unit dual quaternion is its inverse. The
generalized adjacency matrix of the synchronization graph is a matrix of dual
quaternions, rather than a block matrix with real or complex entries. The
resulting matrix is Hermitian, in the dual quaternion sense. By the spectral
theorem for dual quaternion matrices, it has a eigenvector decomposition, as
described in Section 2.5.

Now, given a clean, complete set of measurements, the measurement matrix has
the form $\mathbf{Y}=\mathbf{g}\mathbf{g}^{*}$, where
$\mathbf{g}=\left(g_{1},\dots,g_{n}\right)^{\top}$ is a column vector of unit
dual quaternions and $\mathbf{g}^{*}$ is its conjugate transpose. In the
presence of noise, we consider the dual quaternion eigenvector of the
measurement matrix corresponding to its top eigenvalue as an approximation of
$\mathbf{g}$, the eigenvector of the clean measurement matrix. Here, “top” is
with respect to the order of eigenvalues established in Theorem 2.10. This
eigenvector can be approximated using the power method we surveyed in Section
2.6. The rounding is carried out by applying the map defined in Theorem 2.9 to
each entry this eigenvector. This rounding procedure stems directly from the
close relationship between the algebraic structure and geometry of the dual
quaternion algebra and the unit dual quaternions, as we discussed at the end
of Section 2.4. If the noise is mild enough, all entries of the top
eigenvector are expected to be invertible, in which case the projection
amounts to applying the map $q\mapsto\frac{q}{\left|q\right|}$ entry-wise to
the eigenvector.

Overall, we obtain the following two-step algorithm:

  1. 1.

Find the eigenvector of $\mathbf{Y}$ corresponding to its largest eigenvalue,
in the order established in Theorem 2.11. Use the power iteration we surveyed
in Section 2.6. Denote this eigenvector by
$\widehat{g}=\left(\widehat{g}_{1},\dots,\widehat{g}_{n}\right)^{\top}$.

  2. 2.

Carry out the substitution
$\widehat{g}_{j}\to\frac{\widehat{g}_{j}}{\left|g_{j}\right|}$ on each of its
entries ($j=1,\dots,n$).

As we demonstrate in Section 4, this algorithm yields comparable performance
to the state-of-the-art spectral approach to $\mathrm{SE}(3)$ synchronization
described in [2]. We emphasize the simplicity of the rounding step compared to
the one employed by [2], which we described in Example 3.3. Its simplicity is
owed entirely to the close relationship between $\mathrm{SE}(3)$ and the
algebra of dual quaternions. We also emphasize that here the rounding
procedure does nothing more than handle the disruption the noise causes to the
eigenspaces of the clean measurement matrix. Indeed, as we discussed in
Section 2.7, the isometry group of the eigenspaces of $\mathbf{Y}$ is actually
the unit dual quaternions and as we discussed in Section 2.4, each unit dual
quaternion represents an element of $\mathrm{SE}(3)$. Thus, there is no
eigenspace-synchronization gap, despite the non-compact setting. Our method
enjoys similar performance to the current state-of-the-art in spectral
synchronization for $\mathrm{SE}(3)$, yet reaps the benefits of embedding
$\mathrm{SE}(3)$ in an algebra that is much closer to it in structure.

Taken together, the resulting spectral method is remarkably similar to the
spectral method of $\mathrm{SO}(2)$ we showcased in Example 3.1. This is
evident in two places. First, in the properties of the representing space and
its relationship to the subset which represents the group. Second, in the
underlying tasks performed by the rounding step. This similarity is especially
remarkable when we consider the fact that $\mathrm{SO}(2)$ is a compact,
commutative group, while $\mathrm{SE}(3)$ is a non-compact and non-commutative
group.

Finally, we note that [7] addressed a synchronization problem with selection
noise, though they do not use the word synchronization at all. They proposed
an iterative method, which is distinct from the spectral method we constructed
here, both in its form and its theoretical underpinnings. First, it is not the
spectral method as we conceived it here. At every iteration, the iteration (8)
is used to approximate the eigenvector of some matrix of dual quaternions.
Second, their iterative method was motivated by the need to solve an explicit
optimization problem over the dual quaternions, whereas we relied on the
heuristic picture of the eigenspaces of a matrix being disrupted by noise.

##  4 Numerical Experiments

We run several numerical experiments demonstrating the utility of the dual
quaternions in synchronization problems. We begin in Section 4.1 by describing
how the synthetic synchronization measurement matrices were simulated in our
experiments and describe our experimental procedure. In Section 4.2 and
Section 4.3 we show and discuss the results of the synthetic data experiments.
They demonstrate that using the dual quaternions to represent $\mathrm{SE}(3)$
yields comparable estimates to the current state-of-the-art spectral
synchronization method [2], while enjoying the simpler rounding procedure
obtained by embedding $\mathrm{SE}(3)$ in the algebra of dual quaternions.

###  4.1 Synthetic Experiments Setup

We conducted several experiments on synthetic measurements matrices, modeled
after the synthetic data experiments carried out in [2], the current state-of-
the-art in $\mathrm{SE}(3)$ synchronization. Probability functions on
$\mathrm{SE}(3)$ were defined using the angle-axis-translation representation
discussed in Appendix A. Ground truth elements
$g_{1},\dots,g_{n}\in\mathrm{SE}(3)$ were drawn from i.i.d. random variables.
The angles were independently and uniformly distributed over $[0,2\pi)$. The
axis was independently and uniformly distributed over $S^{2}$. Translations of
the form $\mathbf{t}=\left(t_{1},t_{2},t_{3}\right)^{\top}\in\mathbb{R}^{3}$
were independently distributed with $t_{1}$, $t_{2}$ and $t_{3}$ being i.i.d.
standard Gaussian random variables. The measurement matrix
$\mathbf{Y}\in\mathbb{DH}^{n\times n}$ follows the following model:

$\mathbf{Y}_{ij}=\begin{cases}e_{ij}\left(s_{ij}g_{i}g_{j}^{-1}\varepsilon_{i,j}+\left(1-s_{ij}\right)c_{ij}\right)&1\leq
i<j\leq n,\\\ 1&i=j,\\\ \mathbf{Y}_{ji}^{*}&1\leq j<i\leq n.\end{cases}$ (11)

Here, $\left(e_{ij}\ \middle|\ 1\leq i<j\leq n\right)$ are i.i.d Bernoulli
random variables with parameter $p$ and $\left(s_{ij}\ \middle|\ 1\leq i<j\leq
n\right)$ are i.i.d. are the same with parameter $q$. The former are
indicators of existing measurements and the latter are indicators of entries
which were not corrupted. Denoting by $\circ$ the entry-wise product of two
matrices of elements of $\mathrm{SE}(3)$, the matrices
$\mathbf{E}=\left(e_{ij}\right)$, $\mathbf{S}=\left(s_{ij}\right)$ and
$\mathbf{E}\circ\mathbf{S}=\left(e_{ij}s_{ij}\right)$ are all the adjacency
matrices of random graphs following the Erdős-Rényi model with parameter $p$,
$q$ and $pq$, respectively. The corrupted entries $\left(c_{ij}\ \middle|\
1\leq i<j\leq n\right)$ are i.i.d. with an angle in degrees normally
distributed with zero mean and variance $\sigma_{r}^{2}$, axis distributed
uniformly over $S^{2}$ and translation with $t_{1},t_{2},t_{3}$ being i.i.d.
Gaussian with zero mean and variance $\sigma_{t}^{2}$. All random variables
mentioned above were also independent of each other.

Given a ground truth $\mathbf{g}\in\mathrm{SE}(3)^{n}$ and an estimate
$\widehat{\mathbf{g}}\in\mathrm{SE}(3)^{n}$, we measure the quality of the
estimate as follows. Due to the symmetry in the observations, we have to align
$\mathbf{g}$ and $\widehat{\mathbf{g}}$ in the following sense. We find a
$g\in\mathrm{SE}(3)$ such that a distance metric between $\mathbf{g}$ and
$\widehat{\mathbf{g}}g$ is minimized, where $\widehat{\mathbf{g}}g$ is the
result of multiplying by $g$ from the right every entry of
$\widehat{\mathbf{g}}$. In Appendix B, we discuss the specifics, including the
distance metric we used. Here, we describe the procedure itself. First, we
assume that every element of $\mathrm{SE}(3)$ is represented by
$(q,\mathbf{t})$ with $q\in\mathbb{H}$ being a unit quaternion with non-
negative first coordinate as discussed in Section 2.3 and
$\mathbf{t}\in\mathbb{R}^{3}$. Second, if $g=(q,\mathbf{t})$,
$\mathbf{g}=\left(\left(q_{1},\mathbf{t}_{1}\right),\dots,\left(q_{n},\mathbf{t}_{n}\right)\right)$
and
$\widehat{\mathbf{g}}=\left(\left(\widehat{q}_{1},\widehat{\mathbf{t}}_{1}\right),\dots,\left(\widehat{q}_{n},\widehat{\mathbf{t}}_{n}\right)\right)$,
we have

$q=\frac{s}{\left|s\right|},\qquad s=\sum_{j=1}^{n}\widehat{q}_{j}^{*}q_{j},$
(12)

and

$\mathbf{t}=\frac{1}{n}\sum_{j=1}^{n}\varphi\left(\widehat{q}_{j}^{*}\right)\left(\mathbf{t}_{j}-\widehat{\mathbf{t}}_{j}\right).$
(13)

This alignment procedure was used on the estimate obtained by both methods
employed in our experiments, our dual quaternion spectral synchronization and
the spectral method of [2], which used the matrix representation (10). We note
that our alignment method is considerably simpler to apply than the alignment
method utilized by [2], whose numerical experiments inspired our own.

All experiments were repeated fifty times, each with freshly generated ground
truth and noise realization with the specified experimental parameters. From
each estimate we extracted the entry-wise error, after alignment, for the
rotations and translations, separately. For the rotations, the error was
calculated as $d\left(q_{1},q_{2}\right)=2\arccos\left(2\left\langle
q_{1},q_{2}\right\rangle^{2}-1\right)$, where $\left\langle
q_{1},q_{2}\right\rangle$ is the Euclidean inner product applied to $q_{1}$
and $q_{2}$ considered as elements of $\mathbb{R}^{4}$ with the obvious
embedding. See Remark B.2 at the end of Appendix B for an explanation of this
metric. For the translations, we used the Euclidean distance,
$d\left(\mathbf{t}_{1},\mathbf{t}_{2}\right)=\left\|\mathbf{t}_{1}-\mathbf{t}_{2}\right\|$.
For each, the mean, minimum and maximum error were calculated and each of
these measures was averaged over the fifty repeats. The plotted data for every
quantity is always its mean over the repeats.

We described the approach of [2] in Example 3.3. Both estimation methods were
implemented in Python. [2] originally implemented their approach in MATLAB. We
took care to use equivalent functions to theirs in the Python ecosystem. Code
used to simulate the figures below is available at
https://github.com/idohadi/dqsync-python/.

###  4.2 Response to Missing Entries and Perturbative Noise

In Figure 2(a), we show the results with increasing levels of multiplicative
noise on the rotations and no noise on the translations. In Figure 2(b), we
show the results with increasing levels of multiplicative noise on the
translations and no noise on the rotations. Consistent with the semidirect
product structure of $\mathrm{SE}(3)$, in Figure 2(a) the estimate of the
translational component is also affected by noise, whereas in Figure 2(b) the
quality of the estimate of the rotations is basically flat, unaffected by the
noise. When we vary the level of noise on both the rotational and
translational part in Figure 2(c), the error rises on both components.
Overall, using the dual quaternion representation of $\mathrm{SE}(3)$ yields
marginally better mean entry-wise error, especially in the estimate of the
rotation and when more entries are missing ($p=0.05$ vs. $p=0.3$). It is also
evident that using the dual quaternions yields somewhat stabler estimates, as
indicated by the smoother dual quaternion curves evident in Figure 2. This may
be a feature of our implementation, rather than the method, as these peaks are
not evident in the plots shown in [2]. All trends we discussed above are also
evident in minimum and maximum entry-wise errors. We conclude that the two
methods perform comparably and that the dual quaternions can be used
effectively to represent $\mathrm{SE}(3)$ in applied estimation problems.

(a) $\sigma_{r}=1^{\circ},2^{\circ},\dots,20^{\circ}$ and $\sigma_{t}=0$.

(b) $\sigma_{r}=0^{\circ}$ and $\sigma_{t}=0.01,0.02,\dots,0.2$.

(c)
$\left(\sigma_{r},\sigma_{t}\right)=\left(1^{\circ},0.01\right),\left(2^{\circ},0.02\right),\dots,\left(20^{\circ},0.2\right)$.

Figure 2: Synthetic data experiments with missing entries and perturbative
noise. Throughout experiments, problem size is $n=100$ and there are no
corrupted entries ($q=1$). Every data point is an average over $50$ repeats.
The results using the dual quaternion representation are denoted DQ and using
the matrix representation (10) are denoted MAT.

###  4.3 Response to Corruptive Noise

In Figure 3(a), we used no perturbative noise but there were missing entries.
In Figure 3(b), there are no missing entries but there is perturbative noise.
The same trends are evident in both of them. First, the rotation estimate is
better using the matrix representation (10), while the translation estimate is
better using the dual quaternion representation. Second, the differences in
estimate quality are larger in Figure 3(b) than in Figure 3(a). Overall, these
experiments indicate no clear advantage to either method, but do underscore
the fact the dual quaternions can be used effectively to represent
$\mathrm{SE}(3)$ in applied estimation problems.

(a) $q=0.5,0.55,\dots,0.95$ with $\sigma_{r}=0^{\circ}$ and $\sigma_{t}=0$ and
$p=0.2$.

(b) $q=0.5,0.55,\dots,0.95$ with $\sigma_{r}=5^{\circ}$ and $\sigma_{t}=0.05$
and $p=1$.

Figure 3: Synthetic data experiments with corruptive noise. Throughout
experiments, problem size is $n=100$. Every data point is an average over $50$
repeats. The results using the dual quaternion representation are denoted DQ
and using the matrix representation (10) are denoted MAT.

##  Appendix A Comparison of Representations of $\mathrm{SE}(3)$

We compare the properties of three representations of $\mathrm{SE}(3)$ which
were used in applied mathematics work. Our discussion is skewed towards
properties which we think are central to how notions from linear algebra can
be used to solve applied problems over $\mathrm{SE}(3)$.

The most straightforward way to represent elements of $\mathrm{SE}(3)$ is as
affine transformations, a pair
$\left(R,\mathbf{t}\right)\in\mathrm{SO}(3)\ltimes\mathbb{R}^{3}$. These may
come in several variants, differing in the way the rotation is represented.
Here we survey the axis-angle and rotation matrix representations.

In the axis-angle representation, a rotation $R$ is represented by the axis
$\mathbf{v}\in S^{2}\subset\mathbb{R}^{3}$ of the rotation and the angle
$\theta$ (in radians) by which vectors are rotated around $\mathbf{v}$. Both
can be concisely encapsulated in a rotation vector
$\mathbf{x}=\theta\mathbf{v}\in\mathbb{R}^{3}$, which are elements of
$B_{3}\left(\mathbf{0},2\pi\right)$, where
$B_{3}\left(\mathbf{x},r\right)=\left\\{\mathbf{y}\in\mathbb{R}^{3}\ \middle|\
\left\|\mathbf{x}-\mathbf{y}\right\|_{2}<r\right\\}$. Every pair of a rotation
vector and a translation can represent an element of $\mathrm{SE}(3)$ and one
can easily extend that to pairs of the form
$\mathbb{R}^{3}\times\mathbb{R}^{3}$ by taking the Euclidean norm of the
rotation vector modulo $2\pi$. Thus, we say that representation space, the
space of all elements of the form of the given representation, is
$\mathbb{R}^{3}\times\mathbb{R}^{3}$. The representing subset, the subset of
the representation space into which $\mathrm{SE}(3)$ is embedded, is
$B_{3}\left(\mathbf{0},2\pi\right)\times\mathbb{R}^{3}$. Furthermore, there is
projection from the representation space to the representation subset, mapping
every element of the representation space to the representing subset. We refer
to this representation as the axis-angle-translation representation.

From all this it follows in particular that in this representation the
dimension of the representation space is $6$, which matches the manifold
dimension of $\mathrm{SE}(3)$, which makes it the most parsimonious
representation we will survey. However, there is no direct way to calculate
the product of two elements of $\mathrm{SE}(3)$ in this representation. It is
necessary to convert them into one of the other representations we will
survey. We do not know of any established way to construct something like an
algebra over this representation space and consequently we know of no such way
to construct matrix algebras and investigate their spectral properties.

The other $\mathrm{SO}(3)$ representation we consider are rotation matrices,
real $3\times 3$ orthogonal matrices with a determinant of $1$. This
representation comes with a multiplicative structure of matrix multiplication
and it is embedded in the matrix algebra of all real $3\times 3$ matrices. The
representation space of $\mathrm{SE}(3)$ is then $\mathbb{R}^{3\times
3}\times\mathbb{R}^{3}\cong\mathbb{R}^{12}$. Its multiplicative and vector
space structure can be identified with the set of all affine transformations
of $\mathbb{R}^{3}$, transformations of the form $\mathbf{x}\mapsto
A\mathbf{x}+\mathbf{t}$, where $A$ is a linear transformation and
$\mathbf{t}\in\mathbb{R}^{3}$. This set has both an addition of and
multiplication operations, defined by adding or composing, respectively, two
affine transformations. Despite this, it does not form a ring, because these
two binary operations do not satisfy one of the distributive properties.
Borrowing an example from [4], suppose that
$\left(A_{1},\mathbf{t}_{1}\right)$ and
$\left(\mathbf{0},\mathbf{t}_{2}\right)$ are two affine transformations. Here,
$\mathbf{0}$ is the zero linear transformation and $\mathbf{t}_{2}\neq 0$. We
have

$\left(\mathbf{0},\mathbf{t}_{2}\right)\circ\left(\left(A_{1},\mathbf{t}_{1}\right)+\left(A_{1},\mathbf{t}_{1}\right)\right)=\left(\mathbf{0},\mathbf{t}_{2}\right),$

but

$\left(\mathbf{0},\mathbf{t}_{2}\right)\circ\left(A_{1},\mathbf{t}_{1}\right)+\left(\mathbf{0},\mathbf{t}_{2}\right)\circ\left(A_{1},\mathbf{t}_{1}\right)=2\mathbf{t}_{2}.$

While not being a ring, the affine transformations form a different algebraic
structure, that of a near-ring. As far as we know, matrix spaces and spectral
decompositions were not studied over near-rings in general and over the affine
transformations in particular. Furthermore, to the best of our knowledge, a
projection of affine transformations onto the representing subset has not been
worked out in the literature.

Finally, $\mathrm{SE}(3)$ has a group embedding within the matrix algebra
$\mathbb{R}^{4\times 4}$. An element
$\left(R,\mathbf{t}\right)\in\mathrm{SE}(3)$, where $R$ is represented as
$\mathbf{R}$, real $3\times 3$ orthogonal matrix with determinant of $1$, can
be represented as a block matrix

$\left[\begin{matrix}\mathbf{R}&\mathbf{t}\\\
\mathbf{0}^{\top}&1\end{matrix}\right].$ (14)

Rectangular block matrix where all blocks are of this form obviously belong to
the matrix algebra $\mathbb{R}^{4n\times 4n}$, which definitely has a spectral
decomposition theorem and many other matrix decompositions. Furthermore, an
invertible $\mathbf{A}\in\mathbb{R}^{4\times 4}$ can also be projected onto
the representing subset by a two step procedure. First, finding a invertible
matrix $\mathbf{B}\in\mathbb{R}^{4\times 4}$ such that the matrix
$\mathbf{A}\mathbf{B}$ has $\left(0,0,0,1\right)$ in its bottom row. This
amounts to changing the coordinates of the matrix $\mathbf{A}$ to one which
satisfies this particular constraint on the bottom row. Second, denoting by
$\left(\mathbf{B}\mathbf{A}\right)_{3\times 3}$ the upper left $3\times 3$
submatrix of $\mathbf{B}\mathbf{A}$, one takes its singular value
decomposition $\left(\mathbf{B}\mathbf{A}\right)_{3\times
3}=\mathbf{V}\mathbf{S}\mathbf{U}^{\top}$, where $\mathbf{S}$ is diagonal and
$\mathbf{U}$ and $\mathbf{V}$ are orthogonal. To obtain a matrix of the form
(14), replace $\left(\mathbf{B}\mathbf{A}\right)_{3\times 3}$ with
$\mathbf{V}\mathrm{diag}\left(1,1,\det\left(\mathbf{V}\mathbf{U}\right)\right)\mathbf{V}^{\top}$.

The great advantage of the matrix representation (14) is the fact that its
representation space is a matrix algebra. This allows the use of the familiar
linear algebraic toolkit and in particular allows one to define the projection
we described above. However, this is also the source of the greatest
disadvantage. The group $\mathrm{SE}(3)$ is embedded in the multiplicative
group of $\mathbb{R}^{4\times 4}$, and no more. The other algebraic structures
defined on $\mathbb{R}^{4\times 4}$ are inconsistent with the embedding.
Merely transposing (14) would generally take one out of the representing
subspace, indicating the involution of $\mathbb{R}^{4\times 4}$ plays no role
in representing $\mathrm{SE}(3)$. Furthermore, the relationship between the
projection and group structure is hard to characterize. This last problem
comes to the fore in the situation discussed in Section 3.2, where we describe
the projection onto $\mathrm{SE}(3)$ of an entire column block matrix with
$\mathbb{R}^{4\times 4}$ blocks, which is used in an actual application [2].
Perhaps underscoring the gap between $\mathrm{SE}(3)$ and the representation
space in this case, is the fact $\mathrm{SE}(3)$ is a manifold of dimension
$6$, while the representation space is $16$-dimensional.

Consider the unit dual quaternion representation of $\mathrm{SE}(3)$ we
surveyed in Section 2.4. We argue that the representation space is very close
to the structure of $\mathrm{SE}(3)$, yet similar enough to ordinary vector
spaces to allow some of the same linear-algebraic notions that are so useful
to the applied mathematician to be brought to bear on applied problems. The
representation space is very close to the structure of $\mathrm{SE}(3)$ in two
ways. First, by the fact nearly all dual quaternions are elements of
$\mathrm{SE}(3)$ scaled by dual numbers, as shown by Theorem 2.9 of [7].
Second, the inverse of an element of $\mathrm{SE}(3)$ represented on the unit
dual quaternion is its dual quaternion conjugate, as we saw Section 2.4. In
this way, the involutive algebra structure of the dual quaternions is
intimately tied with the group structure of $\mathrm{SE}(3)$. Most
importantly, despite the non-commutativity of this algebra, it is sufficiently
simple to allow one to establish a spectral theorem as we saw in Section 2.5
and also the derivation of a numerical schemes to approximate eigenvectors,
like we surveyed in Section 2.6. We suggest that other numerical schemes, like
the Arnoldi iteration and other Krylov subspace methods, may also be
generalizable to the dual quaternions.

Taken together, these properties indicate that the dual quaternion algebra
balances well the difficulties incurred by working over non-commutative
algebra with the advantages it offers.

##  Appendix B Alignment of Two Dual Quaternion Vectors

Let $\mathbf{g}=\left(g_{1},\dots,g_{n}\right)^{\top}\in\mathrm{SE}(3)^{n}$
and
$\widehat{\mathbf{g}}=\left(\widehat{g}_{1},\dots,\widehat{g}_{n}\right)^{\top}\in\mathrm{SE}(3)^{n}$.
Assume that elements of $\mathrm{SE}(3)$ are represented as
$g_{j}=\left(q_{j},\mathbf{t}_{j}\right)$ and
$\widehat{g}_{j}=\left(\widehat{q}_{j},\widehat{\mathbf{t}}_{j}\right)$, where
$q_{j}$ and $\widehat{q}_{j}$ are unit quaternions with a non-negative first
coordinate, representing a rotation as we discuss in Section 2.4, and
$\mathbf{t}_{j}$ and $\widehat{\mathbf{t}}_{j}$ are translations represented
as vectors in $\mathbb{R}^{3}$. Recall Proposition 2.7 and the double cover
$\varphi$ defined there. Aligning $\mathbf{g}$ and $\widehat{\mathbf{g}}$
amounts to finding $g=\left(q,\mathbf{t}\right)$ solving

$\min_{g\in\mathrm{SE}(3)}\left\\{\sum_{j=1}^{n}\left\|\widehat{\mathbf{q}_{j}}\mathbf{q}-\mathbf{q}_{j}\right\|_{F}^{2}+\sum_{j=1}^{n}\left\|\varphi(\widehat{q}_{j})(\mathbf{t})+\widehat{\mathbf{t}}_{j}-\mathbf{t}_{j}\right\|_{2}^{2}\right\\}.$
(15)

Here, $\widehat{\mathbf{q}}_{j}$, $\mathbf{q}_{j}$ and $\mathbf{q}$ are real
$3\times 3$ orthogonal matrices with determinant of $1$ representing the same
elements of $\mathrm{SO}(3)$ as $\widehat{q}_{j}$, $q_{j}$ and $q$. These
matrices are constructed by representing $\varphi\left(q\right)$ in the
standard basis of $\mathbb{R}^{3}$. Also, $\left\|\cdot\right\|_{2}$ is the
Euclidean norm and $\left\|\cdot\right\|_{F}$ is the Frobenius norm. Solving
(15) amounts to finding $g$ minimizing the sum of squared distances between
corresponding rotations of $\mathbf{g}$ and $\widehat{\mathbf{g}}$ and a sum
of squared distances between the translations of $\mathbf{g}$ and
$\widehat{\mathbf{g}}$.

The two sums in (15) are two decoupled optimization problems, since the left
one depends only on $q$ and the right one only on $\mathbf{t}$. We consider
these two decoupled problems separately. We begin with the translation sum.
Let $F(\mathbf{t})$ be the right sum in (15). We wish to find the minimum of
$F$ in $\mathbb{R}^{3}$. Because the Euclidean norm is preserved under
orthogonal transformations and $\varphi$ is a homomorphism, $F$ can be written
as

$F(\mathbf{t})=\sum_{j=1}^{n}\left\|\mathbf{t}+\varphi\left(\widehat{q}_{j}^{*}\right)\left(\widehat{\mathbf{t}}_{j}-\mathbf{t}_{j}\right)\right\|^{2}.$

Fermat’s theorem then yields that its exterema is

$\mathbf{t}=\frac{1}{n}\sum_{j=1}^{n}\varphi\left(\widehat{q}_{j}^{*}\right)\left(\mathbf{t}_{j}-\widehat{\mathbf{t}}_{j}\right),$

exactly as in (13). That it is a minimum follows from the fact $F$ is convex
and defined on $\mathbb{R}^{3}$, and therefore can have no local maxima.

The rotation sum is slightly more involved. First, we note that for
any$\mathbf{R}_{1}$ and $\mathbf{R}_{2}$ two real $3\times 3$ orthogonal
matrices with determinant of $1$ we have

$\left\|\mathbf{R}_{1}-\mathbf{R}_{2}\right\|_{F}^{2}=\left\|\mathbf{R}_{1}\right\|_{F}^{2}+\left\|\mathbf{R}_{2}\right\|_{F}^{2}-2\mathop{\mathrm{tr}}\left(\mathbf{R}_{1}\mathbf{R}_{2}^{\top}\right)=3-2\mathop{\mathrm{tr}}\left(\mathbf{R}_{1}^{\top}\mathbf{R}_{2}\right).$

A minimizer of the left sum in (15) is therefore a maximizer over the unit
quaternions with non-negative first coordinate of

$G_{1}(\mathbf{q})=\sum_{j=1}^{n}\mathop{\mathrm{tr}}\left(\mathbf{q}^{\top}\widehat{\mathbf{q}}_{j}^{\top}\mathbf{q}_{j}\right).$

Finally, let $q_{1}$ and $q_{2}$ are quaternions representing the same
elements of $\mathrm{SO}(3)$ as $\mathbf{R}_{1}$ and $\mathbf{R}_{2}$,
respectively. As we argue below, the following identity holds:

$\mathop{\mathrm{tr}}\left(\mathbf{R}_{1}^{\top}\mathbf{R}_{2}\right)=4\left\langle
q_{1},q_{2}\right\rangle^{2}-1,$ (16)

where $\left\langle\cdot,\cdot\right\rangle$ is the Euclidean inner product on
$\mathbb{R}^{4}$ applied to quaternions via their obvious identification with
$\mathbb{R}^{4}$. Therefore, the maximizer of $G_{1}$ over the unit
quaternions with non-negative first coordinate is the maximizer over the same
domain of

$G(q)=\sum_{j=1}^{n}\left\langle\widehat{q}_{j}q,q_{j}\right\rangle.$

We note that

$\left\langle
q_{1},q_{2}\right\rangle=\frac{1}{2}\left(q_{1}^{*}q_{2}+q_{2}^{*}q_{1}\right),$

and so

$\left\langle
q_{1}q,q_{2}\right\rangle=\frac{1}{2}\left(q^{*}q_{1}^{*}q_{2}+q_{2}^{*}q_{1}q\right)=\frac{1}{2}\left(q^{*}\left(q_{1}^{*}q_{2}\right)+\left(q_{1}^{*}q_{2}\right)^{*}q\right)=\left\langle
q,q_{1}^{*}q_{2}\right\rangle.$

Therefore, for any unit quaternion with non-negative first coordinate $q$ we
have:

$G(q)=\sum_{j=1}^{n}\left\langle
q,\widehat{q}_{j}^{*}q_{j}\right\rangle=\left\langle
q,\sum_{j=1}^{n}\widehat{q}_{j}^{*}q_{j}\right\rangle\leq\left\|q\right\|_{2}\left\|\sum_{j=1}^{n}\widehat{q}_{j}^{*}q_{j}\right\|_{2}=\left\|\sum_{j=1}^{n}\widehat{q}_{j}^{*}q_{j}\right\|_{2}.$

In the above we used the Cauchy-Schwartz inequality applied to the
quaternions, again identified as elements of $\mathbb{R}^{4}$. Simple
substitution into $G$ shows that the $q$ defined in (12) is a unit quaternion
with non-negative first coordinate which achieves this bound.

It remains to prove (16). It follows from the following lemma:

######  Lemma B.1.

Let $q$ be a unit quaternion. Let $\mathbf{R}$ be the real $3\times 3$
orthogonal matrix with determinant of $1$ formed by representing $\varphi(q)$
using the standard basis of $\mathbb{R}^{3}$. If
$q=a+b\mathbf{i}+c\mathbf{j}+d\mathbf{k}$, then

$\mathop{\mathrm{tr}}\left(\mathbf{R}\right)=4a^{2}-1.$

$\square$

We obtain (16) as a corollary of Lemma B.1 due to a combination of two facts.
First, $\mathbf{R}_{1}^{\top}\mathbf{R}$ in (16) expressed in quaternions is
$q_{1}^{*}q_{2}$. Second, as can be worked out from (4), the first coordinate
of the product $q_{1}^{*}q_{2}$ is $\left\langle q_{1},q_{2}\right\rangle$.

######  Proof.

Using the axis-angle representation of $\mathbf{R}$, we consider it a rotation
around axis $\mathbf{r}\in S^{2}$ by angle $\theta$. From [11, Appendix A],
$\mathop{\mathrm{tr}}\left(\mathbf{R}\right)=2\cos\theta+1$, while [11, eq.
(6)] yields $a=\cos\frac{\theta}{2}$. Therefore, using the trigonometric
identity $\cos\theta=2\cos^{2}\frac{\theta}{2}-1$, we obtain

$4a^{2}-1=4\cos^{2}\frac{\theta}{2}-1=2\left(2\cos^{2}\frac{\theta}{2}-1\right)+1=2\cos\theta+1,$

as required. $\blacksquare$

######  Remark B.2.

From the identities used in the proof of Lemma B.1, it follows that the metric
we defined on the unit quaternions in in Section 4.1 satisfies
$d(q_{1},q_{2})=2\arccos\left(\cos\theta\right)=2\theta_{12}$, where
$\theta_{12}\in[0,\pi)$ and $\theta$ is the rotation angle in the angle-axis
representation of the rotation $q_{1}^{*}q_{2}$.  $\square$

## Data availability

The data underlying this article are available in the GitHub repository
dqsync-python at https://github.com/idohadi/dqsync-python/.

## Funding

This work was supported by the Binational Science Foundation [2019752];
Binational Science Foundation [2020159] to T.B.; the Israeli Science
Foundation [1924/21] to T.B.; and the Deutsche Forschungsgemeinschaft
[514588180] to N.S.

## References

  * [1] Federica Arrigoni, Beatrice Rossi, Pasqualina Fragneto and Andrea Fusiello  “Robust synchronization in SO (3) and SE (3) via low-rank and sparse matrix decomposition”  In _Computer Vision and Image Understanding_ 174 Elsevier, 2018, pp. 95–113
  * [2] Federica Arrigoni, Beatrice Rossi and Andrea Fusiello  “Spectral Synchronization of Multiple Views in SE(3)”  In _SIAM Journal on Imaging Sciences_ 9.4, 2016, pp. 1963–1990  DOI: 10.1137/16M1060248
  * [3] Tamir Bendory, Alberto Bartesaghi and Amit Singer  “Single-Particle Cryo-Electron Microscopy: Mathematical Theory, Computational Challenges, and Opportunities”  In _IEEE Signal Processing Magazine_ 37.2 Institute of ElectricalElectronics Engineers (IEEE), 2020, pp. 58–76  DOI: 10.1109/msp.2019.2957822
  * [4] D. W. Blackett  “The near-ring of affine transformations”  In _Proceedings of the American Mathematical Society_ 7.3 American Mathematical Society (AMS), 1956, pp. 517–519  DOI: 10.1090/s0002-9939-1956-0078651-x
  * [5] Nicolas Boumal  “Nonconvex Phase Synchronization”  In _SIAM Journal on Optimization_ 26.4 Society for Industrial & Applied Mathematics (SIAM), 2016, pp. 2355–2377  DOI: 10.1137/16m105808x
  * [6] Nicolas Boumal, Amit Singer, P.-A. Absil and Vincent D. Blondel  “Cramér–Rao bounds for synchronization of rotations”  In _Information and Inference: A Journal of the IMA_ 3.1, 2014, pp. 1–39  DOI: 10.1093/imaiai/iat006
  * [7] Chunfeng Cui and Liqun Qi  “A Power Method for Computing the Dominant Eigenvalue of a Dual Quaternion Hermitian Matrix”, 2023  arXiv:2304.04355 [math.OC]
  * [8] David JH Garling  “Clifford Algebras: An Introduction”  Cambridge University Press, 2011
  * [9] V.M. Govindu  “Combining two-view constraints for motion estimation”  In _Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001_ 2, 2001, pp. II–II  DOI: 10.1109/CVPR.2001.990963
  * [10] Michiel Hazewinkel, Nadiya Gubareni and Vladimir V Kirichenko  “Algebras, Rings and Modules”  Springer Science & Business Media, 2004
  * [11] Du Q. Huynh  “Metrics for 3D Rotations: Comparison and Analysis”  In _Journal of Mathematical Imaging and Vision_ 35.2 Springer ScienceBusiness Media LLC, 2009, pp. 155–164  DOI: 10.1007/s10851-009-0161-2
  * [12] Noam Janco and Tamir Bendory  “Unrolled algorithms for group synchronization”, 2022  arXiv:2207.09418 [eess.SP]
  * [13] Gilad Lerman and Yunpeng Shi  “Robust group synchronization via cycle-edge message passing”  In _Foundations of Computational Mathematics_ Springer, 2021, pp. 1–77
  * [14] Shuyang Ling  “Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method”  In _SIAM Journal on Optimization_ 32.2, 2022, pp. 1018–1048  DOI: 10.1137/20M1389571
  * [15] Shuyang Ling  “Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods”  In _Applied and Computational Harmonic Analysis_ 60 Elsevier BV, 2022, pp. 20–52  DOI: 10.1016/j.acha.2022.02.003
  * [16] Amelia Perry, Alexander S. Wein, Afonso S. Bandeira and Ankur Moitra  “Message-Passing Algorithms for Synchronization Problems over Compact Groups”  In _Communications on Pure and Applied Mathematics_ 71.11 Wiley, 2018, pp. 2275–2322  DOI: 10.1002/cpa.21750
  * [17] Liqun Qi, Chen Ling and Hong Yan  “Dual Quaternions and Dual Quaternion Vectors”  In _Communications on Applied Mathematics and Computation_ 4.4, 2022, pp. 1494–1508  DOI: 10.1007/s42967-022-00189-y
  * [18] Liqun Qi and Ziyan Luo  “Eigenvalues and Singular Values of Dual Quaternion Matrices”  arXiv, 2021  DOI: 10.48550/ARXIV.2111.12211
  * [19] Elad Romanov and Matan Gavish  “The Noise-sensitivity phase transition in spectral group synchronization over compact groups”  In _Applied and Computational Harmonic Analysis_ 49.3 Elsevier BV, 2020, pp. 935–970  DOI: 10.1016/j.acha.2019.05.002
  * [20] Jon M Selig  “Geometric Fundamentals Of Robotics”  Springer, 2005
  * [21] Yoel Shkolnisky and Amit Singer  “Viewing Direction Estimation in Cryo-EM Using Synchronization”  In _SIAM Journal on Imaging Sciences_ 5.3 Society for Industrial & Applied Mathematics (SIAM), 2012, pp. 1088–1110  DOI: 10.1137/120863642
  * [22] Amit Singer  “Angular synchronization by eigenvectors and semidefinite programming”  In _Applied and computational harmonic analysis_ 30.1 Elsevier, 2011, pp. 20–36
  * [23] Sebastian Thrun, Wolfram Burgard and Dieter Fox  “Probabilistic Robotics”, Intelligent Robotics and Autonomous Agents series  London, England: MIT Press, 2005
  * [24] Andrea Torsello, Emanuele Rodolà and Andrea Albarelli  “Multiview registration via graph diffusion of dual quaternions”  In _CVPR 2011_ , 2011, pp. 2441–2448  DOI: 10.1109/CVPR.2011.5995565
  * [25] Lloyd N. Trefethen and David Bau  “Numerical Linear Algebra”  Siam, 1997
  * [26] L. Wang and A. Singer  “Exact and stable recovery of rotations for robust synchronization”  In _Information and Inference_ 2.2 Oxford University Press (OUP), 2013, pp. 145–193  DOI: 10.1093/imaiai/iat005
  * [27] Onur Özyeşil, Vladislav Voroninski, Ronen Basri and Amit Singer  “A survey of structure from motion.”  In _Acta Numerica_ 26 Cambridge University Press, 2017, pp. 305–364  DOI: 10.1017/S096249291700006X