# DVMNet: Computing Relative Pose for Unseen Objects Beyond Hypotheses

Chen Zhao1 Tong Zhang1 Zheng Dang1 Mathieu Salzmann12
1EPFL 2ClearSpace SA
{chen.zhao, tong.zhang, zheng.dang<EMAIL_ADDRESS>Corresponding
author.

###### Abstract

Determining the relative pose of an object between two images is pivotal to
the success of generalizable object pose estimation. Existing approaches
typically approximate the continuous pose representation with a large number
of discrete pose hypotheses, which incurs a computationally expensive process
of scoring each hypothesis at test time. By contrast, we present a Deep Voxel
Matching Network (DVMNet) that eliminates the need for pose hypotheses and
computes the relative object pose in a single pass. To this end, we map the
two input RGB images, reference and query, to their respective voxelized 3D
representations. We then pass the resulting voxels through a pose estimation
module, where the voxels are aligned and the pose is computed in an end-to-end
fashion by solving a least-squares problem. To enhance robustness, we
introduce a weighted closest voxel algorithm capable of mitigating the impact
of noisy voxels. We conduct extensive experiments on the CO3D, LINEMOD, and
Objaverse datasets, demonstrating that our method delivers more accurate
relative pose estimates for novel objects at a lower computational cost
compared to state-of-the-art methods. Our code is released at:
https://github.com/sailor-z/DVMNet/.

##  1 Introduction

Object pose estimation plays a crucial role in 3D computer vision and robotics
tasks [2, 11, 23, 33], aiming to estimate the 3D rotation and 3D translation
of an object depicted in an RGB image. The vast majority of existing methods
work under the assumption that the training and testing data include the same
object instances, thereby limiting their applicability to scenarios that
involve previously unseen objects. Recently, generalizable object pose
estimation [21, 29, 32] has received growing attention, showcasing the
potential to generalize to unseen objects from new categories without
retraining the network. In pursuit of this generalization capability, existing
methods leverage densely sampled images depicting unseen objects in diverse
poses, serving as references. Object pose estimation is then carried out
through template matching [21, 29] or by establishing 2D-3D correspondences
[32, 14]. Unfortunately, the effectiveness of these methods strongly depends
on the references densely covering the viewpoints of unseen objects, making
them inapplicable to practical scenarios where only sparse reference views are
available.

Figure 1: Advantages of our DVMNet compared to hypothesis-based methods.
Hypothesis-based techniques approximate the relative object pose by scoring
numerous pose hypotheses, leading to a high computational cost. By contrast,
our DVMNet computes the pose in a hypothesis-free fashion by robustly matching
voxelized 3D representations of the reference and query images via a Weighted
Closest Voxel (WCV) algorithm. Our method strikes a favorable balance between
computational cost and accuracy in relative object pose estimation, as
measured by multiply-accumulate operations (MACs) and angular error.

In this context, a few methods [47, 18, 52] highlight the importance of
relative object pose estimation. Unlike previous approaches in generalizable
object pose estimation, these methods focus on estimating the relative pose of
an unseen object between two images, i.e., a single reference image of the
object and the query image. In this paper, we also work in this setting,
motivated by the practical ease of obtaining a single reference image for a
new object. One plausible solution is to compute the relative pose based on
2D-2D correspondences [13]. However, the single-reference scenario tends to
yield a significant viewpoint gap between the reference and the query.
Existing studies [18, 52] have shown that image-matching techniques [26, 31]
are sensitive to such pose differences. To handle this issue, the prior
methods [47, 18, 52] follow an alternative strategy of scoring multiple pose
hypotheses for the input reference-query pair, and predicting the pose as the
hypothesis with the highest score. However, this strategy comes with the
drawback of requiring numerous pose hypotheses to achieve reasonable accuracy,
e.g., 500,000 in [18], which thus induces a computational burden. Moreover, we
empirically found that these approaches occasionally produce unnaturally large
errors. One plausible explanation is their failure to model the continuous
nature of the object pose space, as they primarily concentrate on learning to
score discrete hypotheses.

To overcome these drawbacks, we present a novel Deep Voxel Matching Network
(DVMNet) that computes the relative pose of unseen objects in a _hypothesis-
free_ and end-to-end manner. Our approach starts by voxelizing the query and
reference images in a dedicated autoencoder. The encoder network lifts 2D
image features to 3D voxels, leveraging cross-view 3D information. The decoder
network reconstructs a masked object image from the voxels, encouraging the
learned voxels to account for the object. Subsequently, we align the query and
reference voxels based on a score matrix that measures the voxel similarities.
To handle unreliable voxels due to background, varying illumination, and other
potential nuisances, we present a Weighted Closest Voxel (WCV) algorithm to
facilitate robust pose estimation. In this algorithm, each voxel-voxel
correspondence is assigned a confidence score computed by utilizing both the
3D voxel objectness map and the 2D object mask learned by the autoencoder. The
relative object pose is then computed by solving a weighted least-squares
problem. Such an end-to-end learning mechanism eliminates the necessity for
voxel-wise annotations and allows the network to directly learn pose-aware
features from RGB images. As illustrated in Fig. 1, our DVMNet requires
significantly fewer multiply-accumulate operations (MACs) while achieving
smaller angular errors than its hypothesis-based competitors.

We perform comprehensive experiments on the CO3D [25], LINEMOD [15], and
Objaverse [9] datasets. Our method yields more accurate and robust relative
pose estimates for previously unseen objects than both image-matching and
hypothesis-based competitors. We also conduct ablation studies where the
results demonstrate the effectiveness of the key components in our framework.
In short, our contributions are twofolds: First, we tackle the problem of
relative pose estimation for unseen objects in a _hypothesis-free_ manner by
introducing a deep voxel matching network. Second, we present a weighted
closest voxel algorithm that robustly and end-to-end computes the object pose
from voxel-voxel correspondences.

##  2 Related Work

Instance-Level Object Pose Estimation. The majority of previous deep learning
approaches to object pose estimation [43, 24, 35, 30, 34] tackle the problem
at an instance level, holding an assumption that the training and testing data
depict the same object instances. Since the appearance of an object instance
in different poses typically exhibits limited variations, these methods
provide highly accurate object pose estimates. Nevertheless, they struggle to
generalize to previously unseen objects during testing without retraining the
network, as has been observed in the literature [21, 29, 32]. This limitation
constrains their applicability in real-world scenarios that often involve
diverse object instances. This has been remedied to a degree by category-level
object pose estimation methods [36, 7, 19]. In this scenario, the testing
images comprise new object instances from specific categories already included
in the training data. Although these methods have achieved promising
generalization ability within the predefined object categories, they become
ineffective when facing objects from entirely new categories.

Generalizable Object Pose Estimation. To tackle the scenario of unseen objects
from new categories, there has been growing interest in generalizable object
pose estimation. When a textured 3D mesh is available for an unseen object,
some approaches [42, 51, 29] suggest generating synthetic images as references
by rendering the 3D mesh from various viewpoints. Given a query image that
depicts this object, a template matching paradigm is utilized to identify the
most similar reference and approximate the object pose in the query as that of
the selected reference. Some methods bypass the need for 3D meshes by assuming
the availability of multiple real reference images. Object pose estimation is
then carried out by employing either a template matching strategy [21] or a 3D
object reconstruction technique [32, 14]. Nevertheless, all of these methods
rely on having access to dense-view reference images, which limits their
applicability in scenarios where only sparse views of references are
available.

Relative Object Pose Estimation. Recently, several studies [47, 18, 52, 37]
have highlighted the importance of relative object pose estimation. These
methods stand out in generalizable object pose estimation due to their key
advantage of requiring only a single reference image. The objective of these
methods is to estimate the relative object pose between the input query image
and the reference. Since the single-reference assumption tends to result in a
large object pose difference between the query and the reference, unseen
object pose estimation becomes more challenging. Intuitively, one could
establish pixel-pixel correspondences between the two images and compute the
relative object pose based on multi-view geometry [13]. However, as reported
in the literature [18, 52] and also in our experiments, even the state-of-the-
art image-matching techniques [26, 31, 12] cannot deliver accurate pose
estimates when confronted with large object pose differences. To address this,
existing methods [47, 18, 52] suggest approximating the relative object pose
via a discrete set of pose hypotheses, and learning to maximize scores of the
positive hypotheses. Since object pose lies in a continuous space [53],
accurately approximating the pose necessitates a vast number of pose
hypotheses, which makes the hypothesis-based approaches computationally
expensive. Moreover, scoring discrete samples lacks an understanding of the
continuous pose distribution, leading to failure cases with unnaturally high
pose estimation errors. By contrast, we present a hypothesis-free technique
that is capable of computing the relative object pose in a single pass via
deep voxel matching.

##  3 Method

Figure 2: Network architecture of our autoencoder. The encoder takes two RGB
images, query and reference, as input and lifts their 2D feature embeddings to
3D voxels by leveraging cross-view 3D information. $\mathbf{O}_{q}$ and
$\mathbf{O}_{r}$ represent the learned 3D objectness maps account for robust
object pose estimation. The decoder then reconstructs the masked object images
from the voxels, allowing the voxels to encode the object patterns.

###  3.1 Problem Formulation

We tackle the problem of estimating the relative pose $\Delta{\mathbf{P}}$ of
a previously-unseen object between a query image $\mathbf{I}_{q}$ and a
reference image $\mathbf{I}_{r}$. In this scenario, the objects present in the
testing set $\Omega_{\text{test}}$ differ from those in the training set
$\Omega_{\text{train}}$, and the goal is to handle the unseen objects without
retraining the network. This requires addressing the challenges of
generalization to unseen objects in $\Omega_{\text{test}}$ and robustness to
the large object pose difference between $\mathbf{I}_{q}$ and
$\mathbf{I}_{r}$.

Since the relative object translation estimation can be facilitated by using
zero-shot object detectors [50, 39, 17], our focus is on predicting the
relative object rotation, i.e., $\Delta{\mathbf{R}}\in{SO(3)}$, which is more
challenging. This choice aligns with existing literature [42, 44, 51, 52].
Previous hypothesis-based approaches [47, 18, 52] approximate
$\Delta{\mathbf{R}}$ by sampling discrete pose hypotheses and maximizing the
scores of positive samples. The problem is formulated as

$\displaystyle\Delta{\hat{\mathbf{R}}}=\underset{{\Delta{\mathbf{R}_{i}}\in\mathcal{R}}}{\arg\max}\
f(\mathbf{I}_{q},\mathbf{I}_{r},\Delta{\mathbf{R}}_{i}),$ (1)

where $\mathcal{R}$ denotes the set of discrete pose hypotheses. Achieving a
decent approximation accuracy requires a large number of hypotheses, e.g.,
500,000 in [18]. By contrast, we present a hypothesis-free technique that
computes $\Delta{\mathbf{R}}$ in a single pass as
$\Delta{\hat{\mathbf{R}}}=g(\mathbf{I}_{q},\mathbf{I}_{r})$.

###  3.2 Motivation

Drawing inspiration from the success of pixel-pixel correspondences in image
matching [45, 49, 26] a natural approach to avoiding the use of pose
hypotheses would be to compute the relative object pose based on 2D
correspondences. However, recent studies [18, 52] have observed that such an
image-matching strategy is unreliable in the scenario of object pose
estimation. We trace this limitation back to the fact that image-matching
methods are not fully differentiable w.r.t. the pose. Specifically, some
approaches [45, 48, 46] encode a notion of consistency among the pixel-pixel
correspondences utilizing the essential matrix. However, computing the pose
from the essential matrix leads to multiple solutions [13]. The pose
estimation is thus detached from the learning process as a post-processing
step. Notably, in the context of object pose estimation, the pre-generated
correspondences tend to be unreliable in the presence of challenges such as
large object pose differences and textureless objects. Therefore, the isolated
pose estimation step in the two-stage design becomes less effective.

To address this issue, we propose to lift the input images to voxelized 3D
representations [40] and perform the matching process in 3D space. Therefore,
the computation of the relative object pose from the resulting voxel-voxel
matches becomes a differentiable operation. This characteristic enables us to
directly supervise the entire framework with the actual quantity we aim to
predict, i.e., the relative object pose. Subsequently, we elaborate on the
steps involved in the presented hypothesis-free mechanism.

###  3.3 Image Voxelization

To achieve the pose estimation from voxel-voxel correspondences with only RGB
images as input, we first need to lift each RGB image to a set of 3D voxels.
To enable such a voxelization, we introduce an autoencoder network depicted in
Fig. 2, which includes a 2D-3D encoder and a 3D-2D decoder. Specifically, we
employ a pretrained vision transformer [41] to convert the query and reference
images to 2D feature embeddings denoted as $\mathbf{F}_{q}$ and
$\mathbf{F}_{r}$, respectively. Considering the difficulty of lifting 2D
images to 3D representations, we incorporate a cross-attention module to
capture cross-view 3D information. We take the feature embedding
$\mathbf{F}_{q}$ as an example (a symmetric process is carried out for
$\mathbf{F}_{r}$). The cross-attention module [41] is defined as

$\displaystyle\tilde{\mathbf{F}}_{q}^{l}=\text{MHSA}(\text{LN}(\mathbf{F}_{q}^{l-1}))+\mathbf{F}_{q}^{l-1},$
(2)
$\displaystyle\hat{\mathbf{F}}_{q}^{l}=\text{MHCA}(\text{LN}(\tilde{\mathbf{F}}_{q}^{l}),\text{LN}(\mathbf{F}_{r}^{l-1}))+\tilde{\mathbf{F}}_{q}^{l},$
(3)
$\displaystyle\mathbf{F}_{q}^{l}=\text{FFN}(\text{LN}(\hat{\mathbf{F}}_{q}^{l}))+\hat{\mathbf{F}}_{q}^{l},$
(4)

where MHSA stands for a multi-head self-attention layer, MHCA represents a
multi-head cross-attention layer that takes $\tilde{\mathbf{F}}_{q}^{l}$ as
_query_ and $\mathbf{F}_{r}^{l-1}$ as _key_ and _value_ , LN denotes layer
normalization [3], and FFN is a feed-forward network that includes MLPs. The
resulting $\hat{\mathbf{F}}_{q}^{l}$ then serves as the input to the next
cross-attention module. Consequently, the output of the last cross-attention
module contains object features depicted from two different viewpoints, thus
incorporating 3D information.

Benefiting from such a 3D-aware encoding process, we voxelize the image
feature embeddings via a simple reshaping process. Note that, to facilitate
the robust pose estimation that will be introduced in Sec. 3.5, we predict an
objectness score for each voxel, which reflects the significance of the voxel
to the relative object pose estimation. Therefore, the actual reshaping
process is conducted as $\mathbb{R}^{C\times H\times
W}\rightarrow\mathbb{R}^{(C^{{}^{\prime}}+1)\times D\times H\times W}$, where
$C=(C^{{}^{\prime}}+1)\times D$. As shown in Fig. 2, we denote the resulting
3D objectness maps and 3D volumes as
$\mathbf{O}_{q},\mathbf{O}_{r}\in\mathbb{R}^{1\times D\times H\times W}$ and
$\mathbf{V}_{q},\mathbf{V}_{r}\in\mathbb{R}^{C^{{}^{\prime}}\times D\times
H\times W}$, respectively.

As our approach does not rely on object segmentation, the learned voxel
representations might be affected by the background of the query and reference
images. To alleviate this issue, we introduce an object-aware decoding process
over $\mathbf{V}_{q}$ and $\mathbf{V}_{r}$. Concretely, $\mathbf{V}_{q}$ and
$\mathbf{V}_{r}$ are projected to 2D space by aggregating the voxels along the
depth direction as $\mathbb{R}^{C^{{}^{\prime}}\times D\times H\times
W}\rightarrow\mathbb{R}^{C^{*}\times H\times W}$, where
$C^{*}=C^{{}^{\prime}}\times D$. The resulting 2D feature embeddings are then
fed into a decoder that contains several self-attention modules [10] from
which the object images $\hat{\mathbf{I}}_{q}$ and $\hat{\mathbf{I}}_{r}$
without background are produced. The object masks $\hat{\mathbf{M}}_{q}$ and
$\hat{\mathbf{M}}_{r}$ are additionally predicted to provide auxiliary
information that benefits the following robust object pose estimation.

We supervise the training of the autoencoder with an image-level loss function
defined as

$\displaystyle L_{ae}=L_{img}+L_{mask},$ (5) $\displaystyle
L_{img}=L_{mse}(\hat{\mathbf{I}}_{q},\hat{\mathbf{I}}_{q}^{gt})+L_{mse}(\hat{\mathbf{I}}_{r},\hat{\mathbf{I}}_{r}^{gt}),$
(6) $\displaystyle
L_{mask}=L_{bce}(\hat{\mathbf{M}}_{q},\hat{\mathbf{M}}_{q}^{gt})+L_{bce}(\hat{\mathbf{M}}_{r},\hat{\mathbf{M}}_{r}^{gt}),$
(7)

where $L_{mse}$ is the mean squared error loss, $L_{bce}$ indicates the binary
cross entropy loss, $(\hat{\mathbf{I}}_{q}^{gt},\hat{\mathbf{I}}_{r}^{gt})$
denote the ground-truth foreground images, and
$(\hat{\mathbf{M}}_{q}^{gt},\hat{\mathbf{M}}_{r}^{gt})$ represent the ground-
truth object masks.

###  3.4 Object Pose from Deep Voxel Matching

Figure 3: Computing relative object pose from 3D voxels. The feature
similarities of $\mathbf{V}_{q}$ and $\mathbf{V}_{r}$ are computed by our deep
voxel matching module, resulting in a score matrix $\mathbf{S}$. A soft
assignment is performed based on $\mathbf{S}$ over the query object mask
$\hat{\mathbf{M}}_{q}$, the 3D objectness map $\mathbf{O}_{q}$, and the 3D
coordinates $\mathbf{X}_{q}$. The aligned query and reference voxels are then
fed into a Weighted Closest Voxel (WCV) algorithm that estimates the relative
object pose in a robust and end-to-end manner.

According to multi-view geometry [4, 13, 38], the relative object pose can be
computed by solving a least-squares problem expressed in terms of voxel-voxel
correspondences. Specifically, as we focus on 3D rotation estimation, the
least-squares problem is formulated as

$\displaystyle
E(\Delta{\mathbf{R}})=\frac{1}{N}\sum_{i=1}^{N}{||\Delta{\mathbf{R}}\mathbf{x}_{r}^{i}-\mathbf{x}_{q}^{i}||}_{2},$
(8)

where $\mathbf{x}_{r}^{i}\in\mathbf{X}_{r}$ and
$\mathbf{x}_{q}^{i}\in\mathbf{X}_{r}$ stand for the 3D coordinates of the
$i$-th reference and query voxels, respectively. The optimal
$\Delta{\hat{\mathbf{R}}}$ is then determined as

$\displaystyle\Delta{\hat{\mathbf{R}}}=\underset{{\Delta{\mathbf{R}_{i}}\in
SO(3)}}{\arg\min}-2\sum_{i=1}^{N}{\mathbf{x}_{q}^{i}}^{T}\Delta{\mathbf{R}_{i}}\mathbf{x}_{r}^{i},$
(9)

As suggested in [4], this problem can be solved by performing a singular value
decomposition (SVD) of a covariance matrix as

$\displaystyle\mathbf{H}=\sum_{i=1}^{N}\mathbf{x}_{r}^{i}{\mathbf{x}_{q}^{i}}^{T},$
(10) $\displaystyle\mathbf{H}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T},$ (11)

where $\mathbf{H}$ indicates the covariance matrix. The closed-form solution
to the least-squares problem is given by
$\Delta{\hat{\mathbf{R}}}=\mathbf{V}\mathbf{U}^{T}$. Consequently, the key
aspect of this problem is to align the 3D voxel coordinates $\mathbf{X}_{q}$
with $\mathbf{X}_{r}$.

Inspired by the studies [38, 16, 19] showing that object pose estimation
benefits from the end-to-end training, we carry out the alignment in a
differentiable fashion. As illustrated in Fig. 3, the alignment is conducted
based on a deep voxel matching module. Specifically, we compute a score matrix
$\mathbf{S}$ whose entry $s_{ij}$ indicates the cosine similarities between
two voxels as

$\displaystyle
s_{ij}=\frac{\mathbf{v}_{q}^{i}\cdot\mathbf{v}_{r}^{j}}{{||\mathbf{v}_{q}^{i}||}_{2}{||\mathbf{v}_{r}^{j}||}_{2}},$
(12)

where $\mathbf{v}_{q}^{i}\in\mathbb{R}^{C^{{}^{\prime}}}$ and
$\mathbf{v}_{r}^{j}\in\mathbb{R}^{C^{{}^{\prime}}}$ denote the $i$-th voxel in
$\mathbf{V}_{q}$ and the $j$-th voxel in $\mathbf{V}_{r}$, respectively. The
alignment is then achieved as

$\displaystyle\mathbf{X}_{q}^{{}^{\prime}}=p(\mathbf{S}/\tau)\mathbf{X}_{q},$
(13)

where $p(\cdot)$ represents the softmax process and $\tau$ is a predefined
temperature.

###  3.5 Weighted Closest Voxel Algorithm

Figure 4: Illustration of the voxel weights. Each colored dot indicates the
voxel position in 3D space. The green dots in the middle and right cubes
represent the voxels with larger weights. The voxel weights in the middle cube
are computed based on the replicated object mask, while the weights in the
right cube are updated by integrating the 3D objectness map with the object
mask.

Note that our task differs from standard point cloud registration [28, 38, 1],
which typically operates on 3D point clouds sampled from 3D object meshes [6]
or captured using specific sensors [8]. Here, by contrast, we work with 3D
volumes lifted from 2D images, and some voxels could thus be outliers since
the corresponding 2D image patches may depict nuisances such as the
background. The presence of these outliers may impact the accuracy of the
relative object pose estimated from the voxel matches. To address this
challenge, we introduce a weighted closest voxel algorithm that enables robust
relative object pose estimation.

Concretely, the objective is to mitigate the effect of unreliable voxel
matches. We thus incorporate a weight vector into the pose estimation process,
modifying Eq. 10 as

$\displaystyle\mathbf{H}=\sum_{i=1}^{N}\omega^{i}\mathbf{x}_{r}^{i}{\mathbf{x}_{q}^{i}}^{T},$
(14)

where $\omega^{i}\in(0,1)$ denotes the weight of the $i$-th voxel pair. This
makes the subsequent relative object pose estimation aware of the reliability
of each voxel pair. We determine the weight vector by utilizing both the
object mask and voxel objectness information produced by the encoder network.
Specifically, we first replicate $\mathbf{\hat{M}}_{q}$ and
$\mathbf{\hat{M}}_{r}$ $D$ times along the depth dimension, which creates
_pseudo_ 3D masks,
$\mathbf{\hat{M}}_{q}^{*},\mathbf{\hat{M}}_{r}^{*}\in\mathbb{R}^{1\times
D\times H\times W}$. These pseudo 3D masks contribute to alleviating the
influence of voxels that depict the background. The weight of each voxel pair
is then determined as

$\displaystyle\mathbf{W}_{m}=h(\frac{p(\mathbf{S}/\tau)\mathbf{\hat{M}}_{q}^{*}+\mathbf{\hat{M}}_{r}^{*}}{2\lambda}),$
(15)

where $h(\cdot)$ indicates the sigmoid function, and $\lambda$ is a manually
defined temperature. Additionally, to mitigate the redundancies naturally
introduced by the replication process over $\mathbf{\hat{M}}_{q}$ and
$\mathbf{\hat{M}}_{r}$, we integrate the resulting pseudo masks with the 3D
objectness maps. The final weight vector of all pairwise voxels is determined
as $\mathbf{W}=\mathbf{W}_{o}\odot\mathbf{W}_{m}$, where $\odot$ indicates the
Hadamard product, and $\mathbf{W}_{o}$ is obtained by carrying out Eq. 15 over
$\mathbf{O}_{q}$ and $\mathbf{O}_{r}$.

Fig. 4 provides an example of the estimated voxel weights. The dots denote the
3D voxel positions and the voxels assigned with larger weights are colored in
green within the middle and right cubes. In the right cube, the green dots
roughly depict a 3D surface that corresponds to the object visible in the 2D
image. Note that our DVMNet is trained without relying on ground-truth 3D
object models. This observation thus demonstrates that the voxels crucial in
determining the relative object pose are aware of the 3D object shape
information. The complete DVMet is trained end-to-end with a loss function
defined as $L=L_{ae}+L_{pose}$ with

$\displaystyle
L_{pose}=||q(\Delta{\hat{\mathbf{R}}})-q(\Delta\mathbf{R}^{gt})||,$ (16)

where $\Delta\mathbf{R}^{gt}$ is the ground-truth relative object pose, and
$q(\cdot)$ is a function that converts a rotation matrix to a 6D continuous
representation [53].

##  4 Experiments

Method | Ball | Book | Couch | Frisbee | Hotdog | Kite | Remote | Sandwich | Skateboard | Suitcase | Mean
---|---|---|---|---|---|---|---|---|---|---|---
SuperGlue [26] | 83.55 | 71.02 | 45.14 | 68.67 | 88.74 | 56.46 | 78.58 | 73.64 | 72.14 | 76.74 | 71.47
LoFTR [31] | 82.51 | 77.33 | 60.57 | 78.39 | 85.05 | 70.03 | 89.74 | 77.77 | 74.33 | 90.73 | 78.64
ZSP [12] | 88.09 | 90.09 | 64.07 | 79.08 | 99.62 | 72.71 | 98.61 | 89.09 | 89.41 | 95.03 | 86.66
Regress [18] | 47.56 | 52.91 | 39.12 | 50.16 | 51.28 | 52.33 | 43.85 | 52.89 | 51.59 | 29.11 | 47.08
RelPose [47] | 56.96 | 55.89 | 40.71 | 54.11 | 64.20 | 69.43 | 42.89 | 59.05 | 42.32 | 32.50 | 51.80
RelPose++ [18] | 36.42 | 35.64 | 20.00 | 36.27 | 33.62 | 33.63 | 34.83 | 36.93 | 40.60 | 20.32 | 32.82
3DAHV [52] | 34.83 | 31.21 | 22.12 | 31.30 | 35.39 | 34.96 | 24.73 | 26.97 | 26.81 | 16.13 | 28.44
DVMNet | 28.31 | 21.98 | 19.01 | 23.23 | 21.45 | 17.50 | 11.39 | 19.63 | 20.14 | 16.85 | 19.95
|  |  |  |  |  |  |  |  |  |  |
Table 1: Experimental results on CO3D [25]. We report the angular errors of
the estimated relative object rotations. All testing object categories were
unseen during training. The best results are shown in bold fonts.

###  4.1 Implementation Details

In the presented autoencoder, we use 3 cross-attention modules in the 2D-3D
encoder and 3 self-attention modules in the 3D-2D decoder. In the relative
object pose estimation module, we normalize the 3D coordinates of the voxels
to an interval of $[-1,1]$ with a mean of $\mathbf{0}$. We set the
temperatures $\tau$ and $\lambda$ in Eq. 13 and Eq. 15 to $0.1$ and $1.0$,
respectively. We train our network in an end-to-end fashion on an A100 GPU,
employing the AdamW [22] optimizer with a batch size of 64 and a learning rate
of $10^{-5}$. Since we focus on predicting the relative object rotation, we
crop the object from the RGB image by utilizing the ground-truth object
bounding box, following the implementation in [42, 51, 47, 18, 52].

###  4.2 Relative Object Pose Estimation on CO3D

We first evaluate our method on the CO3D dataset [25], which has been commonly
utilized in the literature [47, 18, 52]. This dataset contains 18,619 video
sequences that depict 51 object categories. To evaluate the generalization
ability of the network to unseen objects, we follow the setting in [47],
training the network on 41 object categories and testing it on the other 10
categories. The performance is measured by the mean angular error
$e\in[0^{\circ},180^{\circ}]$ of the estimated relative object rotation, which
is defined as

$\displaystyle
e=\text{arccos}\left(\frac{\text{tr}(\Delta{\hat{\mathbf{R}}^{\text{T}}}\Delta{\mathbf{R}^{gt}})-1}{2}\right).$
(17)

We compare our approach with state-of-the-art techniques including image-
matching methods, SuperGlue [26], LoFTR [31], and ZSP [12], hypothesis-based
methods, RelPose [47], RelPose++ [18], and 3DAHV [52], and a direct regression
method implemented in [18].

As reported in Table 1, DVMNet delivers superior relative pose estimation
performance for unseen objects, outperforming both the image-matching and
hypothesis-based competitors by at least $8.49^{\circ}$ in terms of mean
angular error. To shed more light on the robustness of the evaluated
approaches, we categorize the testing image pairs into different groups
according to the corresponding angular errors observed when applying a
particular relative object pose estimation method. We count the number of
image pairs in each group and show the results in Fig. 5. Our method results
in a higher number of image pairs with smaller angular errors. More
importantly, as highlighted by the red dash box in Fig. 5, both image-matching
and hypothesis-based methods exhibit large angular errors for some image
pairs. By contrast, our DVMNet results in fewer failure instances, thus
demonstrating better robustness.

Figure 5: Histogram depicting the distribution of angular errors. The image
pairs in the testing set are divided into distinct groups based on the angular
errors obtained by a specific pose estimation approach. Each bar in the
histogram represents the count of image pairs within a particular group. Our
DVMNet yields much fewer unnaturally large errors than image-matching and
hypothesis-based methods.

Furthermore, as argued in Sec. 3, our hypothesis-free strategy is more
efficient than the hypothesis-based techniques in relative object pose
estimation. We thus assess their computational cost, utilizing the multiply-
accumulate operations (MACs). For hypothesis-based methods, all sampled
hypotheses are processed in parallel. The results shown in Fig. 1 indicate the
benefits of our hypothesis-free DVMNet, which requires considerably fewer MACs
than the hypothesis-based competitors. To further substantiate this advantage,
we provide detailed results in Fig. 6, where the hypothesis-based methods are
evaluated with the number of pose samples varying from 1,000 to 500,000. Note
that for 3DAHV, the maximum number is 100,000 because of our computational
resource constraints. As shown in Fig. 6, one can enhance the efficiency of
the hypothesis-based methods by reducing the number of samples. However, this
efficiency gain comes at the cost of sacrificing pose estimation accuracy. By
contrast, our method achieves a good trade-off between efficiency and pose
estimation accuracy. We also evaluate the time consumption on an A100 GPU. On
average, DVMNet processes a pair of images in 23ms. Despite benefiting from
parallel estimation, RelPose++ and 3DAHV still cost 29ms and 35ms,
respectively, which are slower than our method.

Figure 6: Comparison with hypothesis-based methods. We measure the computational cost as multiply-accumulate operations (MACs). The results for hypothesis-based methods are shown with varying numbers of pose samples, ranging from 1,000 to 500,000. For 3DAHV, we set the maximum number to be 100,000 due to the computational resource constraints. LINEMOD |  SuperGlue [26] |  LoFTR [31] | ZSP [12] | Regress [18] | RelPose [47] | RelPose++ [18] | 3DAHV [52] | DVMNet
---|---|---|---|---|---|---|---|---
Cat |  67.28 |  88.06 | 79.61 | 54.21 | 53.72 | 47.77 | 50.99 | 31.70
Ben. |  58.52 |  70.80 | 74.07 | 52.03 | 62.32 | 44.67 | 38.16 | 34.00
Cam. |  58.11 |  87.13 | 79.65 | 51.04 | 59.91 | 44.31 | 41.92 | 33.18
Dri. |  65.16 |  78.85 | 76.35 | 52.83 | 57.61 | 47.95 | 32.65 | 46.29
Duck |  74.90 |  97.63 | 83.43 | 55.44 | 55.15 | 48.65 | 44.03 | 38.91
Mean |  64.79 |  84.49 | 78.62 | 53.11 | 57.75 | 46.67 | 41.55 | 36.82
Objaverse |  SuperGlue [26] |  LoFTR [31] | ZSP [12] | Regress [18] | RelPose [47] | RelPose++ [18] | 3DAHV [52] | DVMNet
Mean |  102.40 |  134.05 | 107.20 | 55.90 | 80.39 | 33.49 | 28.11 | 20.19
|  |  |  |  |  |  |  |
Table 2: Experimental results on the GROP benchmark [52]. The methods are
evaluated in terms of angular error on the LINEMOD [15] and Objaverse [9]
datasets. The testing data comprises 5 objects from LINEMOD and 128 objects
from Objaverse. All images containing these objects are omitted from the
training set.

###  4.3 Relative Object Pose Estimation on GROP

Recently, a new benchmark called GROP for relative pose estimation of unseen
objects was introduced in [52]. This benchmark comprises two datasets, i.e.,
Objaverse [9] and LINEMOD [15]. Both synthetic and real images with diverse
object poses are considered. We develop experiments on these two datasets,
following the same setup as described in [52]. More concretely, the synthetic
images are generated by rendering the object models of the Objaverse dataset
from different viewpoints [20]. Several sequences of calibrated real images
that depict 13 texture-less household objects are provided from the LINEMOD
dataset. The testing set encompasses 128 objects from Objaverse and 5 objects
from LINEMOD. The images containing these objects are excluded from the
training data, ensuring that all testing objects are previously unseen. All
evaluated approaches are trained and tested on the same predefined image
pairs, leading to a fair comparison.

Table 2 provides the angular errors of the estimated relative object poses on
the LINEMOD and Objaverse datasets. In the synthetic scenarios of Objaverse,
DVMNet outperforms the previous methods by at least $7.92^{\circ}$ in terms of
mean angular error. In the real scenarios of LINEMOD, DVMNet achieves the
smallest angular error for most of the testing objects and reduces the mean
angular error by at least $4.73^{\circ}$ compared to the other approaches.
Moreover, we visualize the object pose depicted in the query image and show
qualitative results in Fig. 7. The query object pose is determined as
$\mathbf{R}_{q}=\Delta\mathbf{R}\mathbf{R}_{r}$, where $\Delta\mathbf{R}$ is
the relative object pose and $\mathbf{R}_{r}$ denotes the object pose in the
reference image. The ground-truth and predicted query object poses are
represented as green and blue arrows, respectively. It is evident from Fig. 7
that the poses estimated by employing our DVMNet are consistently more similar
to the ground truth than those obtained with the baselines.

Figure 7: Qualitative results on LINEMOD [15]. We compute the object pose in
the query image utilizing the relative object pose. The green and blue arrows
represent the ground-truth object poses and the estimated ones, respectively.

###  4.4 Ablation Studies

WCV | 2D Mask | Voxel Objectness | Angular Error
---|---|---|---
✗ | ✗ | ✗ | 31.78
✓ | ✗ | ✗ | 21.64
✓ | ✓ | ✗ | 20.92
✓ | ✗ | ✓ | 20.07
✓ | ✓ | ✓ | 19.95
|  |  |
Table 3: Effectiveness of the presented WCV algorithm. We report the mean
angular errors on the CO3D dataset. The second row indicates the scenario
where the WCV algorithm is replaced with a pose regression module. The third
row presents a closest voxel algorithm without weights involved.

As a critical component of DVMNet, the presented WCV algorithm plays a pivotal
role in achieving hypothesis-free and end-to-end relative object pose
estimation. To substantiate the effectiveness of the WCV algorithm, we develop
comprehensive ablation studies on the CO3D dataset.

We first replace the WCV algorithm with a pose regression module. More
concretely, we perform global average pooling over $\mathbf{V}_{q}$ and
$\mathbf{V}_{r}$. The resulting feature embeddings are concatenated and passed
through three fully connected layers to predict the 6D continuous
representation of relative object rotation. We maintain all the other
components in our framework unchanged to ensure a fair comparison. This
alternative approach is also able to predict the relative object pose in a
hypothesis-free and end-to-end fashion. However, as shown in Table 3, the mean
angular error on the CO3D dataset increases by more than $10^{\circ}$ when the
regression module is employed, showcasing the importance of the WCV algorithm
in the presented hypothesis-free mechanism. Furthermore, we evaluate three
counterparts of the WCV algorithm, i.e., a closest voxel algorithm without
weights, a WCV algorithm with only replicated 2D object masks, and a WCV
algorithm with only 3D objectness maps. The final weights of the voxel pairs
are determined as $\mathbf{W}_{m}$ and $\mathbf{W}_{o}$ in the last two
counterparts, respectively. The closest voxel algorithm delivers the worst
results among these three variants, revealing that the pose estimation process
is affected by the potential outliers. The optimal performance is achieved by
leveraging both 2D object masks and 3D voxel objectness maps, which thus
demonstrates the effectiveness of these components in DVMNet.

##  5 Conclusion

In this paper, we have introduced DVMNet, a novel deep voxel matching network
for relative pose estimation of unseen objects. Unlike hypothesis-based
approaches that rely on a multitude of discrete pose samples, DVMNet computes
relative object poses in a hypothesis-free and end-to-end manner. We determine
the object pose by solving a weighted least-squares problem based on voxel-
voxel correspondences. The voxels are obtained by lifting the query and
reference images to 3D via a dedicated autoencoder. We then align query voxels
with the reference ones and apply a weighted closest voxel (WCV) algorithm for
robust pose estimation. Comprehensive experiments on the CO3D, Objaverse, and
LINEMOD datasets have demonstrated that our method excels in efficiently
delivering accurate relative poses for unseen objects. In future work, we plan
to explore the integration of DVMNet with zero-shot object detectors for 6D
relative object pose estimation.

Acknowledgment. This work was funded in part by the Swiss National Science
Foundation via the Sinergia grant CRSII5-180359 and the Swiss Innovation
Agency (Innosuisse) via the BRIDGE Discovery grant 40B2-0_194729.

Supplementary Material

## 6D Relative Object Pose Estimation

As introduced in the main paper, we are interested in extending the presented
DVMNet to 6D relative object pose estimation in our future work. Notably, we
followed the setting proposed in RelPose, RelPose++, and 3DAHV, assuming the
availability of known object positions. Such information provides a strong
prior, making the relation translation estimation less challenging. In this
scenario, the primary challenge is the detection of an unseen object present
in the query image. We achieve the zero-shot object detection by utilizing the
detection module presented in Gen6D [21]. Specifically, the detection module
predicts the 2D object center and 2D object scale, from which we compute the
3D object translation, following the implementation of Gen6D. The 3D object
rotation is estimated by employing our DVMNet. It is worth noting that our
goal is to achieve 6D object pose estimation in the single-reference setup,
while Gen6D’s detection module utilizes dense-view references by default.
Therefore, in our experiments, we feed a single reference to the detection
module as the template.

We illustrate some preliminary results in Fig. 8 and Fig. 9, visualizing the
6D object pose in the query image as a 3D object bounding box. As shown in
Fig. 8, the combination of Gen6D’s object detector and our DVMNet achieves
promising results in some cases. However, in some scenarios shown in Fig. 9,
Gen6D’s detector fails to effectively detect the unseen object depicted in the
query image. Notably, the zero-shot object detection becomes more challenging
in the single-reference setting due to the large pose difference between the
query object and the reference. In this context, we plan to investigate the
applicability of other zero-shot object detectors such as SAM [17] in future
work.

Figure 8: Visualization of 6D pose estimation for unseen objects on LINEMOD
[15]. The ground-truth 6D object pose and the predicted pose in the query
image are depicted as green and blue 3D bounding boxes, respectively. Figure
9: Failure cases of 6D pose estimation for unseen objects on LINEMOD [15].

## Extension to Sparse-View References

# References | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---
SuperGlue | 71.47 | 73.08 | 68.72 | 65.90 | 64.54 | 63.24 | 61.74
3DAHV | 28.44 | 29.29 | 28.20 | 27.21 | 26.40 | 24.85 | 24.76
DVMNet | 19.95 | 18.38 | 16.79 | 16.21 | 15.73 | 14.99 | 14.93
|  |  |  |  |  |  |
Table 4: Extension to sparse-view references. The experiment is conducted on
CO3D [25] with the number of reference images varying from 1 to 7. The metric
employed is the angular error between the computed query object pose and the
ground truth.

As introduced in the literature [27, 47, 18], some downstream tasks such as 3D
reconstruction often rely on sparse-view references. Intuitively, our DVMNet
can be seamlessly integrated into these tasks, as it operates effectively with
just a single reference. Therefore, we develop an experiment on the CO3D
dataset, evaluating DVMNet with varying numbers of reference images, ranging
from 1 to 7.

Specifically, given an unseen object during testing, we randomly sample $n$
images. These images are then fed into the presented DVMNet, with one image
designated as the query and the remaining ones as references. The object pose
in the query image is simply derived from the resulting $n-1$ relative object
poses as

$\displaystyle\mathbf{R}_{q}=m(\frac{1}{n-1}\sum_{i=1}^{n-1}q(\Delta\mathbf{R}_{i}\mathbf{R}_{r}^{i})),$
(18)

where $\Delta\mathbf{R}_{i}$ and $\mathbf{R}_{r}^{i}$ denote the $i$-th
relative object pose and reference pose, respectively, $q(\cdot)$ represents a
function that converts a rotation matrix to the 6D continuous representation
[53], and $m(\cdot)$ indicates the conversion from the 6D continuous
representation to a rotation matrix. We also evaluate the representative
image-matching (SuperGlue) and hypothesis-based (3DAHV) approaches in the
sparse-view scenario. We ensure a fair comparison by utilizing the same
strategy of query object pose estimation for these methods.

We report the resulting angular errors in Table 4. It is evident that (i) the
angular error of our DVMNet decreases as more reference images are involved,
and (ii) DVMNet consistently yields the smallest angular error. This
observation demonstrates the promising compatibility of our approach with
sparse-view reference images.

## Robustness to Occlusions

Method | SuperGlue | 3DAHV | DVMNet
---|---|---|---
Angular Error $\downarrow$ | 73.72 | 51.49 | 49.02
|  |  |
Table 5: Experimental results on the LINEMOD-O [5] dataset. The mean angular
errors are reported.

Given that object pose estimation is often challenged by occlusions, we assess
the robustness in scenarios involving occlusions by conducting an experiment
on the LINEMOD-O [5] dataset. The testing data comprises three unseen objects,
i.e., cat, driller, and duck. We report the mean angular errors of the
evaluated methods in Table 5. Our DVMNet outperforms both the image-matching
method, SuperGlue, and the hypothesis-based method, 3DAHV, showcasing better
robustness against occlusions.

Method |  Acc @ $30^{\circ}$ (%) $\uparrow$
---|---
RelPose | 64.2
RelPose++ | 77.0
3DAHV | 83.5
PoseDiffusion | 81.8
DVMNet | 84.7
|
Table 6: Additional experimental results on CO3D. Acc @ $30^{\circ}$ is
employed as a metric.

## Additional Results on CO3D

As listed in Tabel 6, we report more results on CO3D, using Acc @ $30^{\circ}$
as a metric. Note that PoseDiffusion [37] takes multiple views ($>2$) as input
by default, while all the other evaluated methods employ two views. For a fair
comparison, we evaluate PoseDiffusion on CO3D using two views. Moreover, The
pose parameters are iteratively updated 100 times during the denoising process
in PoseDiffusion, making the method time-consuming compared with our single
forward pass mechanism.

## References

  * Aoki et al. [2019] Yasuhiro Aoki, Hunter Goforth, Rangaprasad Arun Srivatsan, and Simon Lucey.  Pointnetlk: Robust & efficient point cloud registration using pointnet.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 7163–7172, 2019.
  * Azuma [1997] Ronald T Azuma.  A survey of augmented reality.  _Presence: teleoperators & virtual environments_, 6(4):355–385, 1997.
  * Ba et al. [2016] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  _arXiv preprint arXiv:1607.06450_ , 2016.
  * Besl and McKay [1992] Paul J Besl and Neil D McKay.  Method for registration of 3-d shapes.  In _Sensor fusion IV: control paradigms and data structures_ , pages 586–606. Spie, 1992.
  * Brachmann et al. [2014] Eric Brachmann, Alexander Krull, Frank Michel, Stefan Gumhold, Jamie Shotton, and Carsten Rother.  Learning 6d object pose estimation using 3d object coordinates.  In _Proceedings of the European Conference on Computer Vision_ , pages 536–551. Springer, 2014.
  * Chang et al. [2015] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al.  Shapenet: An information-rich 3d model repository.  _arXiv preprint arXiv:1512.03012_ , 2015.
  * Chen et al. [2020] Dengsheng Chen, Jun Li, Zheng Wang, and Kai Xu.  Learning canonical shape space for category-level 6d object pose and size estimation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11973–11982, 2020.
  * Dai et al. [2017] Angela Dai, Angel X Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5828–5839, 2017.
  * Deitke et al. [2023] Matt Deitke, Dustin Schwenk, Jordi Salvador, Luca Weihs, Oscar Michel, Eli VanderBilt, Ludwig Schmidt, Kiana Ehsani, Aniruddha Kembhavi, and Ali Farhadi.  Objaverse: A universe of annotated 3d objects.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 13142–13153, 2023.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Geiger et al. [2012] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , pages 3354–3361. IEEE, 2012.
  * Goodwin et al. [2022] Walter Goodwin, Sagar Vaze, Ioannis Havoutis, and Ingmar Posner.  Zero-shot category-level object pose estimation.  In _Proceedings of the European Conference on Computer Vision_ , pages 516–532. Springer, 2022.
  * Hartley and Zisserman [2003] Richard Hartley and Andrew Zisserman.  _Multiple view geometry in computer vision_.  Cambridge university press, 2003.
  * He et al. [2022] Xingyi He, Jiaming Sun, Yuang Wang, Di Huang, Hujun Bao, and Xiaowei Zhou.  Onepose++: Keypoint-free one-shot object pose estimation without cad models.  _Advances in Neural Information Processing Systems_ , 35:35103–35115, 2022.
  * Hinterstoisser et al. [2012] Stefan Hinterstoisser, Vincent Lepetit, Slobodan Ilic, Stefan Holzer, Gary Bradski, Kurt Konolige, and Nassir Navab.  Model based training, detection and pose estimation of texture-less 3d objects in heavily cluttered scenes.  In _Asian Conference on Computer Vision_ , pages 548–562. Springer, 2012.
  * Hu et al. [2020] Yinlin Hu, Pascal Fua, Wei Wang, and Mathieu Salzmann.  Single-stage 6d object pose estimation.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , pages 2930–2939, 2020.
  * Kirillov et al. [2023] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al.  Segment anything.  _arXiv preprint arXiv:2304.02643_ , 2023.
  * Lin et al. [2023] Amy Lin, Jason Y Zhang, Deva Ramanan, and Shubham Tulsiani.  Relpose++: Recovering 6d poses from sparse-view observations.  _arXiv preprint arXiv:2305.04926_ , 2023.
  * Lin et al. [2022] Jiehong Lin, Zewei Wei, Changxing Ding, and Kui Jia.  Category-level 6d object pose and size estimation using self-supervised deep prior deformation networks.  In _Proceedings of the European Conference on Computer Vision_ , pages 19–34. Springer, 2022.
  * Liu et al. [2023] Ruoshi Liu, Rundi Wu, Basile Van Hoorick, Pavel Tokmakov, Sergey Zakharov, and Carl Vondrick.  Zero-1-to-3: Zero-shot one image to 3d object.  _arXiv preprint arXiv:2303.11328_ , 2023.
  * Liu et al. [2022] Yuan Liu, Yilin Wen, Sida Peng, Cheng Lin, Xiaoxiao Long, Taku Komura, and Wenping Wang.  Gen6d: Generalizable model-free 6-dof object pose estimation from rgb images.  _Proceedings of the European Conference on Computer Vision_ , 2022.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.
  * Marchand et al. [2015] Eric Marchand, Hideaki Uchiyama, and Fabien Spindler.  Pose estimation for augmented reality: a hands-on survey.  _IEEE Transactions on Visualization and Computer Graphics_ , 22(12):2633–2651, 2015.
  * Peng et al. [2019] Sida Peng, Yuan Liu, Qixing Huang, Xiaowei Zhou, and Hujun Bao.  Pvnet: Pixel-wise voting network for 6dof pose estimation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 4561–4570, 2019.
  * Reizenstein et al. [2021] Jeremy Reizenstein, Roman Shapovalov, Philipp Henzler, Luca Sbordone, Patrick Labatut, and David Novotny.  Common objects in 3d: Large-scale learning and evaluation of real-life 3d category reconstruction.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10901–10911, 2021.
  * Sarlin et al. [2020] Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich.  Superglue: Learning feature matching with graph neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4938–4947, 2020.
  * Schonberger and Frahm [2016] Johannes L Schonberger and Jan-Michael Frahm.  Structure-from-motion revisited.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4104–4113, 2016.
  * Segal et al. [2009] Aleksandr Segal, Dirk Haehnel, and Sebastian Thrun.  Generalized-icp.  In _Robotics: science and systems_ , page 435. Seattle, WA, 2009.
  * Shugurov et al. [2022] Ivan Shugurov, Fu Li, Benjamin Busam, and Slobodan Ilic.  Osop: A multi-stage one shot object pose estimation framework.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6835–6844, 2022.
  * Su et al. [2022] Yongzhi Su, Mahdi Saleh, Torben Fetzer, Jason Rambach, Nassir Navab, Benjamin Busam, Didier Stricker, and Federico Tombari.  Zebrapose: Coarse to fine surface encoding for 6dof object pose estimation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6738–6748, 2022.
  * Sun et al. [2021] Jiaming Sun, Zehong Shen, Yuang Wang, Hujun Bao, and Xiaowei Zhou.  Loftr: Detector-free local feature matching with transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8922–8931, 2021.
  * Sun et al. [2022] Jiaming Sun, Zihao Wang, Siyu Zhang, Xingyi He, Hongcheng Zhao, Guofeng Zhang, and Xiaowei Zhou.  Onepose: One-shot object pose estimation without cad models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6825–6834, 2022.
  * Tremblay et al. [2018] Jonathan Tremblay, Thang To, Balakumar Sundaralingam, Yu Xiang, Dieter Fox, and Stan Birchfield.  Deep object pose estimation for semantic robotic grasping of household objects.  In _Conference on Robot Learning_ , 2018.
  * Wang et al. [2019a] Chen Wang, Danfei Xu, Yuke Zhu, Roberto Martín-Martín, Cewu Lu, Li Fei-Fei, and Silvio Savarese.  Densefusion: 6d object pose estimation by iterative dense fusion.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3343–3352, 2019a.
  * Wang et al. [2021] Gu Wang, Fabian Manhardt, Federico Tombari, and Xiangyang Ji.  Gdr-net: Geometry-guided direct regression network for monocular 6d object pose estimation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 16611–16621, 2021.
  * Wang et al. [2019b] He Wang, Srinath Sridhar, Jingwei Huang, Julien Valentin, Shuran Song, and Leonidas J Guibas.  Normalized object coordinate space for category-level 6d object pose and size estimation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2642–2651, 2019b.
  * Wang et al. [2023a] Jianyuan Wang, Christian Rupprecht, and David Novotny.  Posediffusion: Solving pose estimation via diffusion-aided bundle adjustment.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 9773–9783, 2023a.
  * Wang and Solomon [2019] Yue Wang and Justin M Solomon.  Deep closest point: Learning representations for point cloud registration.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 3523–3532, 2019.
  * Wang et al. [2023b] Zhenyu Wang, Yali Li, Xi Chen, Ser-Nam Lim, Antonio Torralba, Hengshuang Zhao, and Shengjin Wang.  Detecting everything in the open world: Towards universal object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11433–11443, 2023b.
  * Wei et al. [2020] Xingkui Wei, Yinda Zhang, Zhuwen Li, Yanwei Fu, and Xiangyang Xue.  Deepsfm: Structure from motion via deep bundle adjustment.  In _Proceedings of the European Conference on Computer Vision_ , pages 230–247. Springer, 2020.
  * Weinzaepfel et al. [2023] Philippe Weinzaepfel, Thomas Lucas, Vincent Leroy, Yohann Cabon, Vaibhav Arora, Romain Brégier, Gabriela Csurka, Leonid Antsfeld, Boris Chidlovskii, and Jérôme Revaud.  Croco v2: Improved cross-view completion pre-training for stereo matching and optical flow.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 17969–17980, 2023.
  * Wohlhart and Lepetit [2015] Paul Wohlhart and Vincent Lepetit.  Learning descriptors for object recognition and 3d pose estimation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3109–3118, 2015.
  * Xiang et al. [2017] Yu Xiang, Tanner Schmidt, Venkatraman Narayanan, and Dieter Fox.  Posecnn: A convolutional neural network for 6d object pose estimation in cluttered scenes.  _arXiv preprint arXiv:1711.00199_ , 2017.
  * Xiao et al. [2019] Yang Xiao, Xuchong Qiu, Pierre-Alain Langlois, Mathieu Aubry, and Renaud Marlet.  Pose from shape: Deep pose estimation for arbitrary 3D objects.  In _British Machine Vision Conference (BMVC)_ , 2019.
  * Yi et al. [2018] Kwang Moo Yi, Eduard Trulls, Yuki Ono, Vincent Lepetit, Mathieu Salzmann, and Pascal Fua.  Learning to find good correspondences.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2666–2674, 2018.
  * Zhang et al. [2019] Jiahui Zhang, Dawei Sun, Zixin Luo, Anbang Yao, Lei Zhou, Tianwei Shen, Yurong Chen, Long Quan, and Hongen Liao.  Learning two-view correspondences and geometry using order-aware network.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5845–5854, 2019.
  * Zhang et al. [2022] Jason Y Zhang, Deva Ramanan, and Shubham Tulsiani.  Relpose: Predicting probabilistic relative rotation for single objects in the wild.  In _Proceedings of the European Conference on Computer Vision_ , pages 592–611. Springer, 2022.
  * Zhao et al. [2019] Chen Zhao, Zhiguo Cao, Chi Li, Xin Li, and Jiaqi Yang.  Nm-net: Mining reliable neighbors for robust feature correspondences.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 215–224, 2019.
  * Zhao et al. [2021] Chen Zhao, Yixiao Ge, Feng Zhu, Rui Zhao, Hongsheng Li, and Mathieu Salzmann.  Progressive correspondence pruning by consensus learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 6464–6473, 2021.
  * Zhao et al. [2022a] Chen Zhao, Yinlin Hu, and Mathieu Salzmann.  Locposenet: Robust location prior for unseen object pose estimation.  _arXiv preprint arXiv:2211.16290v2_ , 2022a.
  * Zhao et al. [2022b] Chen Zhao, Yinlin Hu, and Mathieu Salzmann.  Fusing local similarities for retrieval-based 3d orientation estimation of unseen objects.  In _Proceedings of the European Conference on Computer Vision_ , pages 106–122. Springer, 2022b.
  * Zhao et al. [2023] Chen Zhao, Tong Zhang, and Mathieu Salzmann.  3d-aware hypothesis & verification for generalizable relative object pose estimation.  _arXiv preprint arXiv:2310.03534_ , 2023.
  * Zhou et al. [2019] Yi Zhou, Connelly Barnes, Jingwan Lu, Jimei Yang, and Hao Li.  On the continuity of rotation representations in neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5745–5753, 2019.


\begin{equation*}
D^j\left(\mu\right) := D\left(\xi^j\left(\mu\right)\right), \qquad
P^j\left(\mu\right) := p\left(\beta,0\right)-\frac{1}{\beta}\left(I + \beta H^\HYL_{\mu,l.s.c.}\right)\left(\xi^j\left(\mu\right)\right),
\end{equation*}

defined on the interval $I^j$. From Proposition <ref> and Theorem <ref> we know that

\begin{equation*}
p^\HYL\left(\beta,\mu\right) = p\left(\beta,0\right) -\frac{1}{\beta}\inf_{\ell_1}\left\{I+\beta H^\HYL_{\mu,l.s.c.}\right\} = \max_{j}P^j\left(\mu\right).
\end{equation*}

Therefore for each $\mu$, there exists a $J$ such that $p^\HYL\left(\beta,\mu\right)=P^J\left(\mu\right)$.

From the continuity of $g^\chi$ we know that all $D^j$ are continuous on their $I^j$. Then Lemma <ref> tells us that each $P^j$ is differentiable on $\mathrm{Int}I^j$, with derivative

\begin{equation*}
\frac{\d P^j}{\d \mu} = D^j + \frac{\left(\mu - a D^j\right)_+}{a-b}.
\end{equation*}

Continuity of this derivative follows from the continuity of $D^j$.

Let us now consider the $\chi=0$ solutions. Since $g^0$ is convex when restricted to $\delta\leq \frac{\mu}{a}$, $\frac{\d g^\chi}{\d \delta}\to+\infty$ as $\delta\uparrow\frac{\mu}{a}$, and $g^0$ is decreasing for $\delta \geq \frac{\mu}{a}$, there exists $\underline{\mu}<\bar{\mu}$ such that this branch has multiple solutions if and only if $\mu\in\left[\underline{\mu},\bar{\mu}\right]$. Let us label these $\xi^0$, $\xi^1$, and $\xi^2$ such that $D^0\geq D^1\geq D^2$. Note that $I^0=\left(-\infty,\bar{\mu}\right]$, $I^1=\left[\underline{\mu},\bar{\mu}\right]$, and $I^2=\left[\underline{\mu},+\infty\right)$. For a visualisation of these solutions, see Figure <ref>.

Since $\xi^0\left(\bar{\mu}\right) = \xi^1\left(\bar{\mu}\right)$ and $\xi^1\left(\underline{\mu}\right) = \xi^2\left(\underline{\mu}\right)$, we have $P^0\left(\bar{\mu}\right) = P^1\left(\bar{\mu}\right)$ and $P^1\left(\underline{\mu}\right) = P^2\left(\underline{\mu}\right)$. Because $D^0\geq \frac{\mu}{a}$ and $D^{1,2}\leq \frac{\mu}{a}$, we have

\begin{equation*}
\frac{\d P^0}{\d \mu} = D^0, \qquad \frac{\d P^{1}}{\d \mu} = \frac{b}{a-b}\left(\frac{\mu}{b} - D^{1}\right) < \frac{b}{a-b}\left(\frac{\mu}{b} - D^{2}\right) = \frac{\d P^{2}}{\d \mu},
\end{equation*}

on $\left(\underline{\mu},\bar{\mu}\right)$. Together these mean that $P^2\left(\bar{\mu}\right) > P^1\left(\bar{\mu}\right) = P^0\left(\bar{\mu}\right)$.

Now extending our attention to all $\xi^j$ defined on some part of $\left(-\infty,\bar{\mu}\right]$, we define

\begin{equation*}
M:= \left\{\mu\leq\bar{\mu}: \exists j \text{ such that } P^j\left(\mu\right) > P^0\left(\mu\right)\right\}.
\end{equation*}

We have just shown that $M\ne\emptyset$, so $\hat{\mu}:=\inf M$ is finite. Since $P^2$ and $P^0$ are continuous, $\hat{\mu}<\bar{\mu}$.

If $\hat{\mu} \in M$, then $\max_{j}P^j\left(\mu\right)$ is discontinuous at $\mu=\hat{\mu}$. In this case we are done.

If $\hat{\mu} \notin M$, then since the $P^j$ are each continuous, $\exists J$ and $\epsilon>0$ such that $P^J\left(\mu\right) > P^0\left(\mu\right)$ for $\mu\in\left(\hat{\mu},\hat{\mu} + \epsilon\right)$.

Now we have to show that the derivatives of $P^0$ and $P^J$ necessarily have different limits as we take $\mu\to\hat{\mu}$ from their respective sides. First note that

\begin{equation*}
\lim_{\mu\uparrow\hat{\mu}}\frac{\d P^0}{\d\mu} = D^0\left(\hat{\mu}\right).
\end{equation*}

Note that $g^\chi\left(\delta\right)\geq g^0\left(\delta\right)$ with equality only if $\chi=0$ or if we have both $\beta = \beta^*$ and $\delta = \frac{\mu}{a}$. Therefore $D^J\ne\frac{\mu}{a}$ and

\begin{align*}
D^J < \frac{\mu}{a} &\implies D^J\in\left[D^2,D^1\right]\\
D^J > \frac{\mu}{a} &\implies D^J > D^0.
\end{align*}

This last inequality is strict because equality could only occur at $\mu = \bar{\mu}$, but $\hat{\mu}<\bar{\mu}$.

If $D^J>\frac{\mu}{a}$, then

\begin{equation*}
\lim_{\mu\downarrow\hat{\mu}}\frac{\d P^J}{\d\mu} = D^J\left(\hat{\mu}\right) > D^0\left(\hat{\mu}\right) = \lim_{\mu\uparrow\hat{\mu}}\frac{\d P^0}{\d\mu}
\end{equation*}

and we are done.

From the symmetry of $g^\chi$ about $\delta = \frac{\mu}{a}$ and from $g^0$ being decreasing for $\delta \geq \frac{\mu}{a}$, we have

\begin{equation}
\label{RelDensity}
D^0 - \frac{\mu}{a} < \frac{b}{a-b}\left(\frac{\mu}{a}-D^1\right)
\end{equation}

for $\mu \in\left[\underline{\mu},\bar{\mu}\right)$. See Figure <ref>. This implies that if $D^J<\frac{\mu}{a}$,

\begin{equation*}
\frac{\d P^J}{\d \mu}  = \frac{b}{a-b}\left(\frac{\mu}{b} - D^J\right) \geq \frac{b}{a-b}\left(\frac{\mu}{b} - D^1\right) > D^0 = \frac{\d P^0}{\d \mu}.
\end{equation*}

Taking the limit to $\hat{\mu}$ gives our result.

[dashed] (2,-0.5) – (2,4);
[thick] (2,4) to [out=270,in=40] (0,0);
[thick] (2,4) to [out=270,in=170] (8,0);
[thick] (0,0.1) – (8,4);
[dashed] (0,0.25) – (8,0.25);
[<->] (0.3,-0.5) – (2,-0.5);
[<->] (2,-0.5) – (6.75,-0.5);
[<->] (2,4) – (3.15,4);
[draw] at (1,-1) $\frac{\mu}{a}-D^1$;
[draw] at (2.5,4.5) $D^0-\frac{\mu}{a}$;
[draw] at (3.5,-1) $\frac{b}{a-b}\left(\frac{\mu}{a}-D^1\right)$;
(0.3,0.25) circle (0.1);
(6.75,0.25) circle (0.1);
(3.15,1.65) circle (0.1);
[dashed] (0.3,-0.5) – (0.3,0.25);
[dashed] (6.75,-0.5) – (6.75,0.25);
[dashed] (3.15,1.65) – (3.15,4);

Sketch of part of (<ref>) to show the inequality (<ref>). Note $\alpha\equiv0$.

Proof of Theorem <ref>
The proof of (<ref>) follows very similarly to the corresponding stage of the proof of Theorem <ref>. Note that the HYL version of (<ref>) follows because $H^\HYL_{\mu,l.s.c.}\geq H^\PMF_{\mu,a-b,l.s.c.}$ almost surely. The proof of (<ref>) uses Lemma <ref>.

§ APPENDICES

§ PROCESSES FOR DIRICHLET AND PERIODIC BOUNDARY CONDITIONS

For Dirichlet boundary condition, one restricts the Brownian bridges to not leaving the set $\L$. Consider the measure

\begin{equation}\label{nnBBMDir}
\mu^{\ssup{{\rm Dir},\beta}}_{x,y}(A)=\frac{\P_x(B\in A;B_\beta\in\d y)}{\d y},\qquad A\subset\Ccal^{\ssup{\rm Dir}}_{1,\L}\mbox{ measurable},
\end{equation}

which has total mass

\begin{equation}
g_\beta^{\ssup{\rm Dir}}(x,y)=\mu_{x,y}^{\ssup{\rm Dir,\beta}}(\Ccal^{\ssup{\rm Dir}}_{1,\L})=\frac{\P_x(B_{[0,\beta]}\subset\L; B_\beta\in\d y)}{\d y}.
\end{equation}

For periodic boundary condition, the marks are Brownian bridges on the  torus $\L=(\R \slash L \Z)^d$. The corresponding path measure is denoted by $\mu_{x,y}^{\ssup{\rm per,\beta}}$; its total mass is equal to

\begin{equation}
g_\beta^{\ssup{\rm per}}(x,y)=\mu_{x,y}^{\ssup{\rm per,\beta}}(\Ccal^{\ssup{\rm per}}_\L)=\sum_{z\in\Z^d}g_{\beta}(x,y+zL)=(4\pi\beta)^{-d/2}\sum_{z\in\Z^d}{\rm e}^{-\frac{|x-y-zL|^2}{4\beta}}.
\end{equation}

For periodic and Dirichlet boundary conditions (<ref>) is replaced by

\begin{equation}\label{qdefbc}
\overline{q}^{\ssup{\rm bc}}=\sum_{k=1}^N q_k^{\ssup{\rm bc}},\qquad\mbox{ with } q_k^{\ssup{\rm bc}}=\frac{1}{k|\L|}\int_\L\d x\,g_{k\beta}^{\ssup{\rm bc}}(x,x).
\end{equation}

Note that this weight depends on $ \L $ and on $N$. We introduce the Poisson point process $\omega_{\rm P} = \sum_{x \in \xi_{ \rm P}} \delta_{(x,B_x)}$ on $\L\times E^{\ssup{\rm bc}}$ with intensity measure $ \nu^{\ssup{\rm bc}} $ whose projections on $ \L\times \Ccal_{k,\L}^{\ssup{\rm bc}} $ with $k\leq N$ are equal to $ \nu_k^{\ssup{\rm bc}}(\d x,\d f)=\frac{1}{k}\Leb_\L(\d x)\otimes\mu_{x,x}^{\ssup{{\rm bc},k\beta}}(\d f)$ and are zero on this set for $k>N$. We do not label $\omega_{\rm P}$ nor $\xi_{ \rm P}$ with the boundary condition nor with $N$; $\xi_{ \rm P}$ is a Poisson process on $\L$ with intensity measure $\overline q^{\ssup{\rm bc}}$ times the restriction $\Leb_\L$ of the Lebesgue measure to $\L$. By ${\tt Q}^{\ssup{\rm bc}}$ and ${\tt E}^{\ssup{\rm bc}}$ we denote probability and expectation with respect to this process. Conditionally on $\xi_{ \rm P}$, the lengths of the cycles $B_x$ with $x\in\xi_{ \rm P}$ are independent and have distribution $(q_k^{\ssup{\rm bc}}/\overline q^{\ssup{\rm bc}})_{k\in\{1,\dots,N\}}$; this process has only marks with lengths $\leq N$. A cycle $B_x$ of length $k$ is distributed according to

\begin{equation}\label{pathprobmeasure}
\P_{x,x}^{\ssup{{\rm bc},k\beta}}(\d f)=\frac{\mu_{x,x}^{\ssup{{\rm bc},k\beta}}(\d f)}{g^{\ssup{\rm bc}}_{k\beta}(x,x)}.
\end{equation}

The above representations allows us to prove the large deviation principles for different boundary conditions. For details we refer to [6] where these arguments are presented in detail for higher level large deviation principles. The independence of the thermodynamic limit of the average finite-volume pressure in Theorem <ref> follows using either the arguments in [6] or in [30, 9, 15].

§ BOSE FUNCTION

The Bose functions are poly-logarithmic functions defined by

\begin{equation}\label{defBosefunctionapa}
g(n,\alpha):=\Li_n(\ex^{-\alpha})=\frac{1}{\Gamma(n)}\int_0^\infty\frac{t^{n-1}}{{\rm e}^{t+\alpha}-1}\,\d t=\sum_{k=1}^\infty k^{-n}{\rm e}^{-\alpha k}\quad\mbox{ for all } n \mbox{ and } \alpha>0,
\end{equation}

and also for $ \alpha=0 $ and $ n>1 $. In the latter case,

\begin{equation}\label{zeta}
g(n,0)=\sum_{k=1}^\infty k^{-n}=\zeta(n),
\end{equation}

which is the zeta function of Riemann. The behaviour of the Bose functions about $ \alpha=0 $ is given by

\begin{equation}\label{boseexp}
\Gamma(1-n)\alpha^{n-1}+\sum_{k=0}^\infty\zeta(n-k)\frac{(-\alpha)^k}{k!} &, n\not= 1,2,3,\ldots, \\[1.5ex]
\frac{(-\alpha)^{n-1}}{(n-1)!}\Big[-\log\alpha +\sum_{m=1}^{n-1}\frac{1}{m}\Big]+\sum_{\heap{k=0}{k\not= n-1}}\zeta(n-k)\frac{(-\alpha)^k}{k!} &, n\in\N.
\end{cases}
\end{equation}

At $ \alpha=0 $, $ g(n,\alpha) $ diverges for $ n\le 1 $, indeed for all $n$ there is some kind of singularity at $ \alpha=0 $, such as a branch point. For further details see [24]. The expansions (<ref>) are in terms of $ \zeta(n) $, which for for $ n\le 1 $ must be found by analytic ally continuing (<ref>). With the asymptotic properties of the zeta function it can be shown that the $k$ series in (<ref>) are convergent for $ |\alpha|<2\pi $. Consequently (<ref>) also represents an analytic continuation of $ g(n,\alpha) $ for $ \alpha<0 $. When $ \alpha\gg 1 $ the series (<ref>) itself is rapidly convergent, and as $ \alpha\to\infty $, $ g(n,\alpha)\sim\ex^{-\alpha} $ for all $n$. Some plots for the Bose functions are given in Figure <ref>.

§ LAMBERT W FUNCTION

The Lambert W function (sometimes called elsewhere the Omega function) is defined as the multi-valued inverse of the $\mathbb{C}\rightarrow\mathbb{C}$ function $w\mapsto w\ex^{w}$. We shall only be concerned with the two branches on $\R$. Figure <ref> shows these two real branches, denoted $W_0$ and $W_{-1}$. The $W_0$ branch is defined on $\left[-\ex^{-1},\infty\right)$, whereas the $W_{-1}$ branch is only defined on $\left[-\ex^{-1},0\right)$. Given a branch $W_l$ with $l\in\left\{0,-1\right\}$, we can find its (real) derivative $W'_l$ by differentiating the equation $W_l\left(x\right)\ex^{W_l\left(x\right)} = x$. This gives us

\begin{equation*}
W'_l\left(x\right) = \frac{1}{x}\frac{W_l\left(x\right)}{1+ W_l\left(x\right)}.
\end{equation*}

Taking further derivatives and applying induction shows that the branches are smooth on the interior of their respective domains, and gives expressions for each order of the derivative. We make use of some asymptotic expansions of $W_0$ and $W_1$:

\begin{equation*}
\begin{alignedat}{2}
W_0\left(x\right) &= x - x^2 + o\left(x^2\right)  & & \quad\text{as }x\to 0,\\
W_0\left(x\right) &= \log x - \log \left(\log x\right) + o\left(1\right) & &\quad\text{as }x\to+\infty,\\
W_{-1}\left(x\right) &= \log\left(-x\right) - \log\left(-\log\left(-x\right)\right) + o\left(1\right) & & \quad\text{as }x\uparrow 0.\\
\end{alignedat}
\end{equation*}

For more details, see [16].

[->] (-1.1,0) – (3.1,0) node[below]$x$;
[<-] (0,1.6) node[left]$W\left(x\right)$ – (0,-4.1);
[very thick] (-0.37,-1) to [out=90,in=225] (0,0) to [out=45,in=190] (3,1.5) node[right]$W_0$;
[very thick, dashed] (-0.37,-1) to [out=270,in=90] (-0.05,-4) node[left]$W_{-1}$;
[dashed] (-0.37,0) node[above]$-1/e$ – (-0.37,-1) – (0,-1) node[right]$-1$;

The two real branches of $W$: $W_0$ and $W_{-1}$.

[1] S. Adams and M. Dickson, Huang-Yang-Luttinger models for Bose gases, in preparation (2018).

[3] S. Adams, Large deviations for empirical measures in cycles of integer partitions and their relation to systems of Bosons,  Analysis and Stochastics of Growth Processes, LMS, Oxford University Press, 148-172, (2008).

[4]
S. Adams and T. Dorlas,
Asymptotic Feynman-Kac formulae for large symmetrised systems of random walks,
Annals de l'Institut Henri Poincaré (B) Probabilités et Statistique 44, 837-875  (2008).

[5]
S. Adams and  W. König,
Large deviations for many Brownian bridges with symmetrised initial-terminal condition,
Probab. Theory Relat. Fields 142: 1-2, 79-124 (2008).

[6] S. Adams, A. Collevecchio and W. König,
The free energy of non-dilute many-particle systems,  Annals of Probability Vol. 39, No. 2, 683–728, (2011).

[7] S. Adams and Q. Vogel, Space-time random walk loop measures, arXiv:1711.02766 (2017).

[9] N. Angelescu and G. Nenciu, On the Independence of the Thermodynamic Limit on the Boundary Conditions in Quantum Statistical Mechanics, Commun. math. Phys. 29, 15–30 (1973).

[10]
G. Benfatto, M. Cassandro, I. Merola and E. Presutti,
Limit theorems for statistics of combinatorial partitions with applications to mean field Bose gas,
Jour. Math. Phys. 46, 033303 (2005).

[11] M. van den Berg, J.T. Lewis and J.V. Pulé, The Large Deviation Principle and Some Models of an Interacting Boson Gas, Commun. Math. Phys. 118, 61–85 (1988).

[15] O. Bratteli and D. W. Robinson,
Operator Algebras and Quantum Statistical Mechanics II,
2nd ed., Springer-Verlag (1997).

[16] R. Corless, G. Gonnet, D. Hare, D. Jeffrey and D. Knuth, On the Lambert W function, Advances in Computational Mathematics, Vol 5, 329 – 359 (1996).

[17] O. Daniel, Bosonic Loop Soups and Their Occupation Fields, PhD thesis. Mathematics Institute: The University of Warwick, (2015).

[18]
T. Dorlas, P. Martin and J.V. Pulé,
Long cycles in a perturbed mean field model of a Boson gas,
Jour. Stat. Phys. 121: 3/4, 433-461 (2005).

[19] A. Dembo and O. Zeitouni,
Large Deviations Techniques and Applications, Springer (2009).

[20]
R.P. Feynman,
Atomic theory of the $ \lambda $ transition in Helium,
Phys. Rev. 91, 1291-1301 (1953).

[21]
K.-H. Fichtner,
On the position distribution of the ideal Bose gas,
Math. Nachr. 151, 59–67 (1991).

[22]
H.-O. Georgii and H. Zessin,
Large deviations and the maximum entropy principle for marked point random fields,
Prob. Theory Relat. Field  96, 177–204 (1993).

[23]
H.-O. Georgii,
Large deviations and the equivalence of ensembles for Gibbsian particle systems with superstable interaction,
Prob. Theory Relat. Fields 99, 171-195 (1994).

[24] J.P. Gram,
Tafeln für die Riemannsche Zetafunktion,
Skrifter København (8) 9, 311-325 (1925).

[25]
J. Ginibre,
Some Applications of Functional Integration in Statistical Mechanics, and Field Theory,
C. de Witt and R. Storaeds, Gordon and Breach, New York   (1970).

[27]
J.T. Lewis,
Why do Bosons Condense?,
In: Statistical Mechanics and Field Theory: Mathematical Aspects, pp.234-256. Springer (1986).

[28]
E.H. Lieb, R. Seiringer, J.P. Solovej  and J. Yngvason,
The mathematics of the Bose gas and its condensation,
volume 34 of Oberwolfach Seminars,
Birkhäuser Verlag, Basel (2005).

[29]
M. Rafler,
Gaussian Loop- and Polya Processes: A Point Process Approach,
PhD Thesis, University of Potsdam (2009).

[30]
D.W. Robinson,
The Thermodynamic pressure in Quantum Statistical Mechanics,
Springer Lecture Notes in Physics, Vol. 9 (1971).

[32] A. Sütő,
Percolation transition in the Bose gas: II,
J. Phys. A: Math. Gen. 35, 6995-7002 (2002).

[36]
D. Ruelle,
Statistical Mechanics: Rigorous Results,
W.A. Benjamin, Inc. (1969).

[37] B.Toth,
Phase Transition in an Interacting Bose System. An Application of the Theory of Ventsel and Freidlin,
J. Stat. Phys., 61, 749-64 (1990).

[39]
A.M. Vershik,
Statistical Mechanics of Combinatorial Partitions, and Their Limit Shapes,
Func. Anal. Appl. 30: 3, 90-105 (1996).


representation of quantum strategies established in Theorem 3.5. ∎

In the next two propositions, we clarify some useful properties of quantum
colourings. The first one is an automatic homomorphism result.

######  Proposition 5.12.

Let $X$ and $A$ be finite sets, $\mathcal{N}$ be a von Neumann algebra and
$\Psi:M_{A}\to\mathcal{D}_{X}\otimes\mathcal{N}$ be a unital completely
positive map with Kraus representation
$\Psi(T)=\sum_{i=1}^{m}M_{i}TM_{i}^{*}$. The following are equivalent:

  * (i)

$\Psi$ is a *-homomorphism;

  * (ii)

condition (46) holds.

###### Proof.

(i)$\Rightarrow$(ii) For each $a,b\in A$, we write
$\Psi(\epsilon_{a,b})=\sum_{x\in X}\epsilon_{x,x}\otimes r_{x,a,b}$. For
$a\neq b$ in $A$ and $1\leq i,j\leq m$, set

(49) $X_{a,b,i,j}=\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{b,b}\in M_{A}.$

We have

$\displaystyle\sum_{j=1}^{m}X_{a,b,i,j}X_{a,b,i,j}^{*}=\sum_{j=1}^{m}\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{b,b}M_{j}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{i}\epsilon_{a,a}$
$\displaystyle=\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})\left(\sum_{y\in X}\epsilon_{y,y}\otimes
r_{y,b,b}\right)(\epsilon_{x,x}\otimes 1_{\mathcal{N}})M_{i}\epsilon_{a,a}$
$\displaystyle=\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
r_{x,b,b})M_{i}\epsilon_{a,a}$ (50)
$\displaystyle=\left(\epsilon_{a,a}M_{i}^{*}\left(\epsilon_{x,x}\otimes
r_{x,b,b}^{1/2}\right)\right)\left(\epsilon_{a,a}M_{i}^{*}\left(e_{x,x}\otimes
r_{x,b,b}^{1/2}\right)\right)^{*},$

where we have used the fact that $e_{x,b,b}$ is positive. Let

(51) $Y_{a,b,i}=\epsilon_{a,a}M_{i}^{*}\left(\epsilon_{x,x}\otimes
r_{x,b,b}^{1/2}\right),\ \ \ x\in X,a,b\in A,i=1,\dots,m.$

By (50), $\sum_{j=1}^{m}X_{a,b,i,j}X_{a,b,i,j}^{*}=Y_{a,b,i}Y_{a,b,i}^{*}$.
Furthermore,

$\displaystyle\sum_{i=1}^{m}Y_{a,b,i}^{*}Y_{a,b,i}$
$\displaystyle=\sum_{i=1}^{m}\left(\epsilon_{x,x}\otimes
r_{x,b,b}^{1/2}\right)M_{i}\epsilon_{a,a}M_{i}^{*}\left(\epsilon_{x,x}\otimes
r_{x,b,b}^{1/2}\right)$ $\displaystyle=\left(\epsilon_{x,x}\otimes
r_{x,b,b}^{1/2}\right)\left(\sum_{y\in X}\epsilon_{y,y}\otimes
r_{y,a,a}\right)\left(\epsilon_{x,x}\otimes r_{x,b,b}^{1/2}\right)$ (52)
$\displaystyle=\epsilon_{x,x}\otimes\left(r_{x,b,b}^{1/2}r_{x,a,a}^{1/2}\right)\left(r_{x,b,b}^{1/2}r_{x,a,a}^{1/2}\right)^{*}.$

Since $\Psi$ is a homomorphism,
$r_{x,b,b}^{1/2}r_{x,a,a}^{1/2}=r_{x,b,b}r_{x,a,a}=0$ if $a\neq b$. By (52),
it follows that $Y_{a,b,i}=0$ for all $i$ and all $a\neq b$. Using (50), we
have $X_{a,b,i,j}=0$ for all $i,j$ and $a\neq b$. By (49), this forces
$M_{i}^{*}(\epsilon_{x,x}\otimes 1_{\mathcal{N}})M_{j}\in\mathcal{D}_{A}$.

Next, we show that $M_{i}^{*}(\epsilon_{x,x}\otimes 1_{\mathcal{N}})M_{j}$
lies in $\mathbb{C}I_{A}$. We set

$\lambda_{a,x,i,j}=\text{Tr}\left(\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{a,a}\right);$

then $M_{i}^{*}(\epsilon_{x,x}\otimes 1_{\mathcal{N}})M_{j}=\sum_{a\in
A}\lambda_{a,x,i,j}\epsilon_{a,a}$. To establish (iii), it suffices to show
that $\lambda_{a,x,i,j}=\lambda_{b,x,i,j}$ for all $a,b\in A$.

Set

(53) $C_{a,b,x,i,j}=\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{a,a}-\epsilon_{a,b}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{b,a}$

and observe that

$C_{a,b,x,i,j}=(\lambda_{a,x,i,j}-\lambda_{b,x,i,j})\epsilon_{a,a}.$

We note that $\epsilon_{a,a}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{b,a}=\epsilon_{a,b}M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{a,a}=0$, since $M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\in\mathcal{D}_{A}$. Therefore,

(54)
$C_{a,b,x,i,j}=(\epsilon_{a,a}-\epsilon_{a,b})M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}(\epsilon_{a,a}+\epsilon_{b,a}).$

Since

$(\epsilon_{a,a}+\epsilon_{b,a})(\epsilon_{a,a}+\epsilon_{a,b})=\epsilon_{a,a}+\epsilon_{a,b}+\epsilon_{b,a}+\epsilon_{b,b},$

by summing over $j$ and setting
$d_{x,a,b}=r_{x,a,a}+r_{x,a,b}+r_{x,b,a}+r_{x,b,b}\geq 0$, we obtain

(55)
$\sum_{j=1}^{m}C_{a,b,x,i,j}C_{a,b,x,i,j}^{*}=(\epsilon_{a,a}-\epsilon_{a,b})M_{i}^{*}(\epsilon_{x,x}\otimes
d_{x,a,b}))M_{i}(\epsilon_{a,a}-\epsilon_{b,a}).$

Let $g_{x,a,b}\in\mathcal{N}$ satisfy $g_{x,a,b}g_{x,a,b}^{*}=d_{x,a,b}$ and
define

(56)
$D_{a,b,x,i}=(\epsilon_{a,a}-\epsilon_{a,b})M_{i}^{*}(\epsilon_{x,x}\otimes
g_{x,a,b}).$

By (55),

$\sum_{j=1}^{m}C_{a,b,x,i,j}C_{a,b,x,i,j}^{*}=D_{a,b,x,i}D_{a,b,x,i}^{*}.$

Set $f_{x,a,b}=r_{x,a,a}-r_{x,a,b}-r_{x,b,a}+r_{x,b,b}$ and note that
$f_{x,a,b}\geq 0$ and

(57) $\displaystyle\sum_{i=1}^{m}D_{a,b,x,i}^{*}D_{a,b,x,i}$
$\displaystyle=(\epsilon_{x,x}\otimes
g_{x,a,b}^{*})M_{i}(\epsilon_{a,a}-\epsilon_{b,a})(\epsilon_{a,a}-\epsilon_{a,b})M_{i}^{*}(\epsilon_{x,x}\otimes
g_{x,a,b})$ $\displaystyle=\epsilon_{x,x}\otimes
g_{x,a,b}^{*}(r_{x,a,a}-r_{x,a,b}-r_{x,b,a}+r_{x,b,b})g_{x,a,b}^{*}$
$\displaystyle=\epsilon_{x,x}\otimes(g_{x,a,b}^{*}f_{x,a,b}g_{x,a,b}).$

Since $\Psi$ is a *-homomorphism, the element $g_{x,a,b}=r_{x,a,a}+r_{x,a,b}$
satisfies the relation $g_{x,a,b}^{*}g_{x,a,b}=d_{x,a,b}$. A calculation then
shows that $g_{x,a,b}^{*}f_{x,a,b}g_{x,a,b}=0$. By (57), $D_{a,b,x,i}=0$, and
by (55), $C_{a,b,x,i,j}=0$. This forces $\lambda_{x,a,i,j}=\lambda_{x,b,i,j}$
for all $a\neq b$. Hence, $M_{i}^{*}(\epsilon_{x,x}\otimes
1_{\mathcal{N}})M_{j}\in\mathbb{C}I_{A}$.

(ii)$\Rightarrow$(i) The assumption implies that
$M_{i}^{*}(\epsilon_{x,x}\otimes 1_{\mathcal{N}})M_{j}\in\mathcal{D}_{A}$, so
equations (49)–(52) show that $r_{x,a,a}^{1/2}r_{x,b,b}^{1/2}=0$, and hence
$r_{x,a,a}r_{x,b,b}=0$, whenever $a\neq b$. Since each $e_{r,a,a}\geq 0$ and
$\sum_{a\in A}r_{x,a,a}=1$, we have that $r_{x,a,a}^{2}=r_{x,a,a}$ for each
$x\in X$ and $a\in A$. As $\Psi(\epsilon_{a,a})=\sum_{x\in
X}\epsilon_{x,x}\otimes r_{x,a,a}$, the diagonal matrix unit $\epsilon_{a,a}$
belongs to the multiplicative domain of $\Psi$ for each $a$. In particular,

$\Psi(\epsilon_{a,a})\Psi(\epsilon_{b,c})=\delta_{a,b}\Psi(\epsilon_{a,c})=\delta_{a,b}\sum_{x\in
X}\epsilon_{x,x}\otimes r_{x,a,c}$

for all $b,c\in A$.

Now, choose $g_{x,a,b}$ with $g_{x,a,b}^{*}g_{a,x,b}=d_{x,a,b}$, and
$h_{x,a,b}$ with $h_{x,a,b}^{*}h_{x,a,b}=f_{x,a,b}$. Our assumption on implies
that $C_{a,b,x,i,j}=0$ for all $a\neq b$, $x\in X$ and all $i$ and $j$. By
(53)–(57), $g_{x,a,b}^{*}f_{x,a,b}g_{x,a,b}=0$, yielding
$g_{x,a,b}h_{x,a,b}^{*}=0$. Multiplying on the left by $g_{x,a,b}^{*}$ and on
the right by $h_{x,a,b}$, we get $d_{x,a,b}f_{x,a,b}=0$. Using the fact that
$\epsilon_{a,a}$ and $\epsilon_{b,b}$ are in the multiplicative domain of
$\Psi$, a calculation shows that

(58)
$0=d_{x,a,b}f_{x,a,b}=r_{x,a,a}+r_{x,b,b}-r_{x,a,b}r_{x,b,a}-r_{x,b,a}r_{x,b,a}.$

Multiplying equation (58) on both sides by $r_{x,a,a}$, we get
$0=r_{x,a,a}-r_{x,a,b}r_{x,b,a}$. Therefore, $r_{x,a,b}r_{x,b,a}=r_{x,a,a}$.
Similarly, $r_{x,b,a}r_{x,a,b}=r_{x,b,b}$, so that $\epsilon_{a,b}$ belongs to
the multiplicative domain of $\Psi$. Since $a,b\in A$ were arbitrary with
$a\neq b$, $\Psi$ must be a homomorphism, completing the proof. ∎

Remark.  We note that an alternative proof of the implications
(iii)$\Rightarrow$(ii) in Theorem 5.11 can be given, using Proposition 5.12.
We have decided to present the given argument instead as it shows that, it
order to conclude that the game $\varphi_{G}^{A}$ has a perfect strategy (of
the corresponding class) one does not need to necessarily resort to the fact
that $\Psi$ has to be a homomorphism.

The next proposition shows the combinatorial meaning of (47).

######  Proposition 5.13.

Let $X$ and $A$ be finite sets, $G$ be a graph with vertex set $X$, and
$\mathcal{N}$ be a von Neumann algebra. Let
$\pi:M_{A}\to\mathcal{D}_{X}\otimes\mathcal{N}$ be a unital *-homomorphism
with Kraus representation $\pi(T)=\sum_{i=1}^{m}M_{i}TM_{i}^{*}$ and write
$\pi(\epsilon_{a,b})=\sum_{x\in X}\epsilon_{x,x}\otimes r_{x,a,b}$, where
$r_{x,a,b}\in\mathcal{N}$, $x\in X$, $a,b\in A$. The following are equivalent:

  * (i)

condition (47) holds;

  * (ii)

if $v\sim w$ in $G$, then $\sum_{a,b\in A}r_{v,a,b}r_{w,b,a}=0$.

###### Proof.

Let $v\sim w$ in $G$, and define

$R_{c,i,j}=\sum_{b\in A}\epsilon_{c,b}M_{i}^{*}(\epsilon_{v,w}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{b,c},\ \ c\in A,i,j\in[m].$

Set

$T_{c,i}=\sum_{a\in A}\epsilon_{c,a}F_{i}(\epsilon_{v,v}\otimes e_{w,a,c}).$

We have

$\displaystyle\sum_{c\in A}\sum_{i,j=1}^{m}R_{c,i,j}R_{c,i,j}^{*}$
$\displaystyle=\sum_{a,b,c\in
A}\sum_{i,j=1}^{m}\epsilon_{c,a}M_{i}^{*}(\epsilon_{v,w}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{a,c}\epsilon_{c,b}M_{j}^{*}(\epsilon_{w,v}\otimes
1_{\mathcal{N}})M_{i}\epsilon_{b,c}$ $\displaystyle=\sum_{a,b,c\in
A}\sum_{i,j=1}^{m}\epsilon_{c,a}M_{i}^{*}(\epsilon_{v,w}\otimes
1_{\mathcal{N}})M_{j}\epsilon_{a,b}M_{j}^{*}(\epsilon_{w,v}\otimes
1_{\mathcal{N}})M_{i}\epsilon_{b,c}$ $\displaystyle=\sum_{a,b,c\in
A}\sum_{i=1}^{m}\epsilon_{c,a}M_{i}^{*}(\epsilon_{v,w}\otimes
1_{\mathcal{N}})\pi(\epsilon_{a,b})(\epsilon_{w,v}\otimes
1_{\mathcal{N}})M_{i}\epsilon_{b,c}$ $\displaystyle=\sum_{a,b,c\in
A}\sum_{i=1}^{m}\epsilon_{c,a}M_{i}^{*}(\epsilon_{v,v}\otimes
r_{w,a,b})M_{i}\epsilon_{b,c}$ $\displaystyle=\sum_{a,b,c\in
A}\sum_{i=1}^{m}\epsilon_{c,a}M_{i}^{*}(\epsilon_{v,v}\otimes
r_{w,a,c})(\epsilon_{v,v}\otimes r_{w,c,b})M_{i}\epsilon_{b,c}$ (59)
$\displaystyle=\sum_{c\in A}\sum_{i=1}^{m}T_{c,i}T_{c,i}^{*},$

On the other hand,

$\displaystyle\sum_{c\in A}\sum_{i=1}^{m}T_{c,i}^{*}T_{c,i}$
$\displaystyle=\sum_{a,b,c\in A}\sum_{i=1}^{m}(\epsilon_{v,v}\otimes
r_{w,c,a})M_{i}\epsilon_{a,c}\epsilon_{c,b}M_{i}^{*}(\epsilon_{v,v}\otimes
r_{w,b,c})$ $\displaystyle=\sum_{a,b,c\in
A}\sum_{i=1}^{m}(\epsilon_{v,v}\otimes
r_{w,c,a})M_{i}\epsilon_{a,b}M_{i}^{*}(\epsilon_{v,v}\otimes r_{w,b,c})$
$\displaystyle=\sum_{a,b,c\in A}(\epsilon_{v,v}\otimes
r_{w,c,a})(\epsilon_{v,v}\otimes r_{v,a,b})(\epsilon_{v,v}\otimes r_{w,b,c})$
(60) $\displaystyle=\epsilon_{v,v}\otimes\sum_{a,b,c\in
A}r_{w,c,a}r_{v,a,b}r_{w,b,c}.$

Since $\pi$ is a *-homomorphism,

(61) $\sum_{a,b,c\in A}r_{w,c,a}r_{v,a,b}r_{w,b,c}=\left(\sum_{a,c\in
A}r_{w,c,a}r_{v,a,c}\right)\left(\sum_{a,c\in
A}r_{w,c,a}r_{v,a,c}\right)^{*}.$

Considering equations (59)-(61), it follows that condition (i) is equivalent
to having $R_{c,i,j}=0$ for all $c\in A$ and all $i,j\in[m]$. The latter
condition is in turn equivalent to the condition $\mathop{\rm
Tr}(M_{i}^{*}(\epsilon_{v,w}\otimes 1_{\mathcal{N}})M_{j})=0$ for all
$i,j\in[m]$. The proof is complete. ∎

###  5.3. Algebraic versions of the orthogonal rank

Recall that the orthogonal rank $\xi(G)$ of $G$ is the smallest
$k\in\mathbb{N}$ for which there exists an _orthogonal representation_ of $G$
in $\mathbb{C}^{k}$, that is, a collection $(\xi_{x})_{x\in X}$ of unit
vectors in $\mathbb{C}^{k}$ such that

$x\sim y\ \Longrightarrow\ \langle\xi_{x},\xi_{y}\rangle=0.$

In this subsection, we discuss algebraic and C*-algebraic versions of the
parameter $\xi(G)$. To place this into context, we define the _relaxed
classical-to-quantum colouring game_ as the game
$\psi_{G}^{A}:\mathcal{P}^{\rm cl}_{XX}\to\mathcal{P}_{AA}$ determined by the
requirements

$\psi_{G}^{A}(\epsilon_{x,x}\otimes\epsilon_{y,y})=\begin{cases}J_{A}^{\perp}&\mbox{if
}x\sim y,\\\ I_{AA}&\mbox{otherwise}.\end{cases}$

Let ${\rm x}\in\\{{\rm loc},{\rm q},{\rm qa},{\rm qc}\\}$. We consider the
following two parameters:

$\xi_{\rm x}(G)=\min\\{|A|:\mbox{there exists a perfect tracial }{\rm
x}\mbox{-strategy for }\psi_{G}^{A}\\},$

which we call the _relaxed orthogonal ${\rm x}$-rank_ of $G$, and

$\xi_{\rm x}^{\prime}(G)=\min\\{|A|:\mbox{there exists a perfect }{\rm
x}\mbox{-strategy for }\varphi_{G}^{A}\\},$

which we call the _orthogonal ${\rm x}$-rank_ of $G$ (we set $\xi_{\rm
x}(G)=\infty$ if there is no perfect strategy for $\varphi_{G}^{A}$ for any
$A$). These parameters were introduced in [30, Subsection 10.1] as quantum
versions of the orthogonal rank. We note the following:

  * (i)

Since $\varphi_{G}^{A}$ is more restrictive than $\psi_{G}^{A}$, we have that
$\xi_{\rm x}(G)\leq\xi^{\prime}_{\rm x}(G)$;

  * (ii)

By [30, Proposition 10.3], we have $\xi_{\rm loc}(G)=\xi(G)$. On the other
hand, if $|A|>1$ then $\xi_{\rm loc}^{\prime}(G)=\infty$;

  * (iii)

By [30, Proposition 10.5], $\xi^{\prime}_{\rm q}(K_{d^{2}})=\xi^{\prime}_{\rm
qc}(K_{d^{2}})=d$, and hence $\xi^{\prime}_{\rm q}(G)\leq[\sqrt{|X|}]+1$. By
Corollary 5.9, $\xi_{q}(K_{d^{2}})=d$.

Taking into account Remark 3.11, we see that the ideal
$\mathfrak{I}(\varphi_{G}^{A})$ of $\mathfrak{B}_{X,A}$ is given by

$\mathfrak{I}(\varphi_{G}^{A})=\left\langle\left\\{\sum_{a,b\in
A}e_{x,a,b}e_{y,b,a}:x\sim y\right\\}\right\rangle,$

that is, $\mathfrak{B}(\varphi_{G}^{A})$ is the universal *-algebra generated
by matrix unit systems $(e_{x,a,a^{\prime}})_{a,a^{\prime}\in A}$, $x\in X$,
subject to the relations $\sum_{a,b\in A}e_{x,a,b}e_{y,b,a}=0$ whenever $x\sim
y$. Similarly, $\mathcal{B}(\varphi_{G}^{A})$ is the universal C*-algebra
generated by such matrix unit systems, subject to these relations.

Corollary 3.12 implies the following characterisations:

######  Corollary 5.14.

Let $G$ be a graph with vertex set $X$. Then

  * (i)

The quantum commuting colourings of $G$ correspond to traces of
$\mathcal{B}(\varphi_{G}^{A})$. In particular,

$\xi_{\rm qc}^{\prime}(G)=\min\\{|A|:\mathcal{B}(\varphi_{G}^{A})\mbox{
possesses a tracial state}\\},$

and

  * (ii)

The quantum colourings of $G$ correspond to finite dimensional traces of
$\mathcal{B}(\varphi_{G}^{A})$. In particular,

$\xi_{\rm q}^{\prime}(G)=\min\\{|A|:\mathcal{B}(\varphi_{G}^{A})\mbox{
possesses a finite dim. *-representation}\\}.$

###### Proof.

Suppose that $\tau$ is a tracial state on $\mathcal{C}_{X,A}$ that annihilates
the generators $A_{x,y}=\sum_{a,b\in A}e_{x,a,b}e_{y,b,a}$, $x\sim y$, of
$\mathfrak{I}(\varphi_{G}^{A})$. Note that

$A_{x,y}^{*}A_{x,y}=\sum_{a,b,c,d\in
A}e_{y,a,b}e_{x,b,a}e_{x,c,d}e_{y,d,c}=\sum_{b,c,d\in
A}e_{y,c,b}e_{x,b,d}e_{y,d,c};$

it follows that

$\tau(A_{x,y}^{*}A_{x,y})=|A|\tau\left(\sum_{b,d\in
A}e_{x,b,d}e_{y,d,b}\right)=0.$

Combining this with the Cauchy-Schwartz inequality we obtain the statements. ∎

######  Definition 5.15.

  * (i)

The _algebraic orthogonal rank_ $\xi_{\rm alg}(G)$ is the smallest cardinality
of a set $A$ for which $\mathfrak{B}(\varphi_{G}^{A})\neq\\{0\\}$; if such $A$
does not exist, set $\xi_{\rm alg}(G)=\infty$;

  * (ii)

The _C*-algebraic orthogonal rank_ $\xi_{C^{*}}(G)$ is the smallest
cardinality of a set $A$ for which $\mathcal{B}(\varphi_{G}^{A})\neq\\{0\\}$;
if such $A$ does not exist, set $\xi_{C^{*}}(G)=\infty$.

######  Proposition 5.16.

Let $G$ be a graph with vertex set $X$. Then
$\xi_{C^{*}}(G)\geq\sqrt{\frac{|X|}{\theta(G)}}$. Moreover,
$\xi_{C^{*}}(K_{d^{2}})=d$.

###### Proof.

If $\xi_{C^{*}}(G)=\infty$ then the inequality is trivial; assume hence that
$\mathcal{B}(\varphi_{G}^{A})\neq\\{0\\}$. Since
$\mathcal{B}(\varphi_{G}^{A})$ is separable, it possesses a faithful state
$s$. Let $\pi$ be the corresponding GNS representation and $\xi$ the
corresponding cyclic vector. Set $E_{x,a,b}=\pi(e_{x,a,b})$ and
$\xi_{x,a,b}=E_{x,a,b}\xi$, $x\in X$, $a,b\in A$. The proof of the inequality
is now concluded in the same way as the proof of [30, Proposition 10.5].

For the equality, realise $A=\mathbb{Z}_{d}=\\{0,1,\ldots,d-1\\}$ and let
$X=A\times A$. Let $\zeta$ be a primitive $|A|$-th root of unity and, for
$x=(a^{\prime},b^{\prime})$ and $y=(a^{\prime\prime},b^{\prime\prime})\in X$,
set

$E_{x,z,z^{\prime}}=\zeta^{(z^{\prime}-z)b^{\prime}}e_{z-a^{\prime}}e_{z^{\prime}-a^{\prime}}^{*}\in
M_{A},\ \ x=(a^{\prime},b^{\prime})\in X,z,z^{\prime}\in A.$

For $x=(a^{\prime},b^{\prime})$ and $y=(a^{\prime\prime},b^{\prime\prime})$
with $x\neq y$, we have

$\displaystyle\sum_{z,z^{\prime}\in A}E_{x,z,z^{\prime}}E_{y,z^{\prime},z}$
$\displaystyle=$ $\displaystyle\sum_{z,z^{\prime}\in
A}\zeta^{(z^{\prime}-z)b^{\prime}}\zeta^{(z-z^{\prime})b^{\prime\prime}}(e_{z-a^{\prime}}e_{z^{\prime}-a^{\prime}}^{*})(e_{z^{\prime}-a^{\prime\prime}}e_{z-a^{\prime\prime}}^{*})$
$\displaystyle=$ $\displaystyle\sum_{z,z^{\prime}\in
A}\delta_{z^{\prime}-a^{\prime},z^{\prime}-a^{\prime\prime}}\delta_{z-a^{\prime},z-a^{\prime\prime}}\zeta^{(z^{\prime}-z)(b^{\prime}-b^{\prime\prime})}I=0.$

In addition,

$\displaystyle E_{x,z,z^{\prime}}E_{x,z^{\prime},z^{\prime\prime}}$
$\displaystyle=$
$\displaystyle\zeta^{(z^{\prime}-z)b^{\prime}}\zeta^{(z^{\prime\prime}-z^{\prime})b^{\prime}}(e_{z-a^{\prime}}e_{z^{\prime}-a^{\prime}}^{*})(e_{z^{\prime}-a^{\prime}}e_{z^{\prime\prime}-a^{\prime}}^{*})$
$\displaystyle=$
$\displaystyle\zeta^{(z^{\prime\prime}-z)b^{\prime}}e_{z-a^{\prime}}e_{z^{\prime\prime}-a^{\prime}}^{*};$

thus, $\mathcal{B}(\varphi_{K_{d^{2}}}^{A})$ is non-trivial. ∎

As the next proposition shows, the algebraic orthogonal rank can be strictly
smaller than the C*-algebraic one.

######  Proposition 5.17.

$\xi_{\rm alg}(K_{d^{2}})=2$ for all $d\geq 2$.

###### Proof.

We first show that $\xi_{\rm alg}(K_{d^{2}})\leq 2$. The case of $d=2$ follows
from Proposition 5.16, so we assume that $d\geq 3$. By Proposition 5.16, the
algebra of the (classical) $4$-colouring game for $K_{d^{2}}$ is non-zero.
Hence, there are self-adjoint idempotents $p_{v,w}$ in a non-zero, unital
*-algebra $\mathcal{A}$, for $1\leq v\leq d^{2}$ and $1\leq w\leq 4$, such
that $\sum_{w=1}^{4}p_{v,w}=1$ for all $v$, $p_{v,w}p_{v,z}=0$ if $w\neq z$,
and

(62) $p_{u,w}p_{v,w}=0,\ \ \ u\neq v.$

By Proposition 5.16, the algebra $\mathcal{B}(\varphi_{K_{4}}^{A})$ is non-
zero when $|A|=2$. Hence, there are elements $e_{x,a,b}$ in a unital
$*$-algebra $\mathcal{B}$, for $1\leq x\leq 4$ and $1\leq a,b\leq 2$, such
that $e_{x,a,b}e_{x,c,d}=\delta_{b,c}e_{x,a,d}$, $e_{x,a,b}^{*}=e_{x,b,a}$,
$\sum_{a=1}^{2}e_{x,a,a}=1$ and

(63) $\sum_{a,b=1}^{2}e_{x,a,b}e_{y,b,a}=0,\ \ \ x\neq y.$

For $1\leq v\leq d^{2}$ and $1\leq a,b\leq 2$, define

$f_{v,a,b}=\sum_{w=1}^{4}p_{v,w}\otimes
e_{w,a,b}\in\mathcal{A}\otimes\mathcal{B}.$

We will show that the elements $f_{v,a,b}$ satisfy the requirements of the
generators for the classical-to-quantum colouring game for $K_{d^{2}}$ with
$|A|=2$. Observe that

$\displaystyle f_{v,a,b}f_{v,c,d}$
$\displaystyle=\sum_{w,z=1}^{4}p_{v,w}p_{v,z}\otimes
e_{w,a,b}e_{z,c,d}=\sum_{w=1}^{4}p_{v,w}\otimes e_{w,a,b}e_{w,c,d}$
$\displaystyle=\delta_{b,c}\sum_{w=1}^{4}p_{v,w}\otimes
e_{w,a,d}=\delta_{b,c}f_{v,a,d}.$

Since $p_{v,w}^{*}=p_{v,w}$ and $e_{w,a,b}^{*}=e_{w,b,a}$, we have
$f_{v,a,b}^{*}=f_{v,b,a}$. In addition,

$\sum_{a=1}^{2}f_{v,a,a}=\sum_{a=1}^{2}\sum_{w=1}^{4}p_{v,w}\otimes
e_{w,a,a}=\sum_{w=1}^{4}p_{v,w}\otimes 1=1\otimes 1.$

Lastly, using (62) and (63), assuming that $u\neq v$, we have

$\displaystyle\sum_{a,b=1}^{2}f_{u,a,b}f_{v,b,a}$
$\displaystyle=\sum_{a,b=1}^{2}\sum_{w,z=1}^{4}p_{u,w}p_{v,z}\otimes
e_{w,a,b}e_{z,b,a}$ $\displaystyle=\sum_{w=1}^{4}p_{u,w}p_{v,w}\otimes 1=0.$

Thus, there is a unital *-homomorphism from
$\mathcal{B}(\varphi_{K_{d^{2}}}^{A})$ to $\mathcal{A}\otimes\mathcal{B}$ with
$|A|=2$, so $\xi_{\rm alg}(K_{d^{2}})\leq 2$.

It remains to show that $\xi_{\rm alg}(K_{d^{2}})\geq 2$. To this end, we show
that $\mathfrak{B}(\varphi_{K_{d^{2}}}^{A})=\\{0\\}$ if $|A|=1$. When $|A|=1$,
the relations defining $\mathfrak{B}(\varphi_{K_{d^{2}}}^{A})$ reduce to
having generators $q_{v,a,a}$, $a\in A$, $1\leq v\leq d^{2}$, such that
$\sum_{a\in A}q_{v,a,a}=1$, $q_{v,a,a}^{*}=q_{v,a,a}$ and
$q_{v,a,a}q_{w,a,a}=0$ for $v\neq w$. Since $|A|=1$, the first relation
implies that $q_{v,a,a}=1$ for all $v,a$. Then since $n\geq 2$, we may choose
$1\leq v,w\leq d^{2}$ with $v\neq w$. Since we must have
$q_{v,a,a}q_{w,a,a}=0$, it follows that $1=1^{2}=0$ in
$\mathfrak{B}(\varphi_{K_{d^{2}}}^{A})$. Hence, $\xi_{\rm alg}(K_{d^{2}})\geq
2$. ∎

## References

  * [1] C. Anantharaman-Delaroche, On ergodic theorems for free group actions on noncommutative spaces, Probab. Theory Rel. Fields 135 (2006), 520-546.
  * [2] A. Bochniak, P. Kasprzak and P. Sołtan, Quantum correlations on quantum spaces, preprint (2021), arXiv:2105.07820.
  * [3] G. Boreland, I. G. Todorov and A. Winter, Sandwich theorems and capacity bounds for non-commutative graphs, J. Combin. Theory Ser. A 177 (2021), 105302, 39 pp.
  * [4] M. Brannan, A. Chirvasitu, K. Eifler, S. Harris, V. I. Paulsen, X. Su and M. Wasilewski, Bigalois extensions and the graph isomorphism game, Comm. Math. Phys. 375 (2020), no. 3, 1777-1809.
  * [5] M. Brannan, P. Ganesan and S. J. Harris, The quantum-to-classical graph homomorphism game, preprint (2020), arXiv:2009.07229.
  * [6] N. P. Brown and N. Ozawa, C*-algebras and finite-dimensional approximations, American Mathematical Society, 2008.
  * [7] T. Cooney, M. Junge, C. Palazuelos and D. Pérez-García, Rank-one quantum games, Comput. Complexity 24 (2015), no. 1, 133-196.
  * [8] G. De las Cuevas, T. Drescher and T. Netzer, Quantum magic squares: dilations and their limitations, J. Math. Phys. 61 (2020), no. 11, 111704, 15 pp.
  * [9] R. Duan, S. Severini and A. Winter, Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovász $\theta$ function, IEEE Trans. Inf. Theory 59 (2013), no. 2, 1164-1174.
  * [10] R. Duan and A. Winter, No-signalling assisted zero-error capacity of quantum channels and an information theoretic interpretation of the Lovász number, IEEE Trans. Inf. Theory 62 (2016), no. 2, 891-914.
  * [11] K. Dykema, V. I. Paulsen and J. Prakash, Non-closure of the set of quantum correlations via graphs, Comm. Math. Phys. 365 (2019), no. 3, 1125-1142.
  * [12] J. W. Helton, K. P. Meyer, V. I. Paulsen and M. Satriano, Algebras, synchronous games, and chromatic numbers of graphs, New York J. Math. 25 (2019), 328-361.
  * [13] Z. Ji, A. Natarajan, T. Vidick, J, Wright and H. Yuen, MIP* = RE, preprint (2020), arXiv:2001.04383.
  * [14] M. Junge, M. Navascues, C. Palazuelos, D. Perez-Garcia, V. Scholz and R. F. Werner, Connes’ emnedding problem and Tsirelson’s problem, J. Math. Phys. 52, 012102 (2011), 12 pages.
  * [15] E. Kirchberg, Discrete groups with Kazhdans property T and factorization property are residually finite, Math. Ann. 299 (1994), 35-63.
  * [16] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory 25 (1979), no. 1, 1-7.
  * [17] M. Lupini, L. Mančinska, V. I. Paulsen, D. E. Roberson, G. Scarpa, S. Severini, I. G. Todorov and A. Winter, Perfect strategies for non-local games, Math. Phys. Anal. Geom. 23 (2020), no. 1, Paper No. 7, 31 pp.
  * [18] L. Mančinska and D. E. Roberson, Graph homomorphisms for quantum players, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography, LIPIcs. Leibniz Int. Proc. Inform. 27 (2014), 212-216.
  * [19] M. Musat and M. Rørdam, Factorizable maps and traces on the universal free product of matrix algebras, preprint (2019), arXiv:1903.10182.
  * [20] M. Musat and M. Rørdam, Non-closure of quantum correlation matrices and factorizable channels that require infinite dimensional ancilla. With an appendix by Narutaka Ozawa, Comm. Math. Phys. 375 (2020), no. 3, 1761-1776.
  * [21] B. Musto, D. Reutter and D. Verdon, A compositional approach to quantum functions, J. Math. Phys. 59 (2018), 081706, 42pp.
  * [22] N. Ozawa, About the Connes embedding conjecture: algebraic approaches, Jpn. J. Math. 8 (2013), no. 1, 147-183.
  * [23] V. I. Paulsen, Entanglement and non-locality, Lecture Notes, University of Waterloo, 2016.
  * [24] V. I. Paulsen, S. Severini, D. Stahlke, I. G. Todorov and A. Winter, Estimating quantum chromatic numbers, J. Funct. Anal. 270 (2016), no. 6, 2188-2222.
  * [25] V. I. Paulsen and M. Rahaman, Bisynchronous games and factorizable maps, preprint (2019), arXiv:1908.03842.
  * [26] V. I. Paulsen, I. G. Todorov and M. Tomforde, Operator system structures on ordered spaces, Proc. London Math. Soc. 102 (2011), 25-49.
  * [27] O. Regev and T. Vidick, Quantum XOR games, ACM Trans. Comput. Theory 7 (2015), no. 4, Art. 15, 43 pp.
  * [28] P. Sołtan Quantum semigroups from synchronous games, J. Math. Phys. 60 (2019), no. 4, 042203, 8pp.
  * [29] D. Stahlke, Quantum zero-error source-channel coding and non-commutative graph theory, IEEE Trans. Inform. Theory 62 (2016), no. 1, 554-577.
  * [30] I. G. Todorov and L. Turowska, Quantum no-signalling correlations and non-local games, preprint (2020), arXiv:2009.07016.
  * [31] L. Trevisan, On Khot’s unique games conjecture, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 1, 91-111.
  * [32] J. Watrous, The theory of quantum information, Cambridge University Press, 2018.
  * [33] N. Weaver, Quantum Graphs as Quantum Relations, Jour. Geom. Anal. (2021), https://doi.org/10.1007/s12220-020-00578-w.