Group Synchronization on Grids

arXiv:1706.08561v1 [] 26 Jun 2017

Emmanuel Abbe∗, Laurent Massoulie†,

Andrea Montanari‡,

Allan Sly§,

Nikhil Srivastava¶

June 28, 2017

Abstract
Group synchronization requires to estimate unknown elements (θ v )v∈V of a compact group
G associated to the vertices of a graph G = (V, E), using noisy observations of the group
differences associated to the edges. This model is relevant to a variety of applications ranging
from structure from motion in computer vision to graph localization and positioning, to certain
families of community detection problems.
We focus on the case in which the graph G is the d-dimensional grid. Since the unknowns θv
are only determined up to a global action of the group, we consider the following weak recovery
question. Can we determine the group difference θ−1
u θ v between far apart vertices u, v better
than by random guessing? We prove that weak recovery is possible (provided the noise is small
enough) for d ≥ 3 and, for certain finite groups, for d ≥ 2. Viceversa, for some continuous
groups, we prove that weak recovery is impossible for d = 2. Finally, for strong enough noise,
weak recovery is always impossible.

1

Introduction

In the group synchronization problem, we are given a (countable) graph G = (V, E), a group G
and, for each edge (u, v) ∈ E, a noisy observation Y u,v . The objective is to estimate group elements
(θ v )v∈V associated to the vertices v ∈ V , under the assumption that the Y u,v are noisy observations
of the group difference between the adjacent vertices. Roughly speaking (see below for a precise
definition):
Y uv = θ −1
u θ v + noise .

(1.1)

In order for the above to be unambiguous, we will assume that an orientation (u, v) is fixed arbitrarily for each edge.
It is useful to introduce two concrete examples.
Example 1.1. The simplest example is G = Z2 = {(+1, −1), · }, the group with elements (+1, −1)
and operation given by ordinary multiplication (equivalently, the group of integers modulo 2). For
∗

Program in Applied and Computational Mathematics, and EE Department, Princeton University
Inria, MSR-Inria Joint Centre
‡
Department of Electrical Engineering and Department of Sttistics, Stanford University
§
Department of Mathematics, Princeton University
¶
Department of Mathematics, University of California, Berkeley
†

1

each edge (u, v) ∈ E we are given Yuv a noisy observation of θ u θ v = θ −1
u θ v . For instance we can
assume that, for some p ∈ [0, 1/2),
(
θu θv
with probability 1 − p,
(1.2)
Y uv =
−θ u θ v
with probability p.
with the (Y uv )(u,v)∈E conditionally independent given (θ v )v∈V . In other words Y uv is the output
of a binary symmetric channel with flip probability p and input θ u θ v .
We will refer to this case as Z2 synchronization.
Example 1.2. Consider G = O(m): the group of m × m orthogonal matrices, with the following
noise model. Let (Z uv )(u,v)∈E be an i.i.d. collection of matrices with i.i.d. standard normal entries,
and define
Y uv = PO(m) (θ −1
u θ v + σZ uv ) .

(1.3)

Here PO(m) is the projector for the Frobenius norm k · kF onto the orthogonal group, namely for a
matrix M with singular value decomposition M = U ΣV T , we set PO(m) (M ) = U V T .
Group synchronization plays an important role in a variety of applications.
Structure from motion is a central problem in computer vision: given multiple images of an object
taken from different points of view (and in presence of noise or occlusions) we want to reconstruct the
3-dimensional structure of the object [MMM13, CMG13, OS15, WBS16]. A possible intermediate
step towards this goal consists in estimating the relative orientation of the object with respect
to the camera in each image. This can be formulated as a group synchronization problem over
G = SO(3), whereby θ u describes the orientation of image u, and pairwise image registration is
used to construct the relative rotations Y uv .
Graph localization and positioning. Consider a set of nodes with positions x1 , . . . , xn ∈ Rd . We
want to reconstruct the nodes positions from noisy measurements of the pairwise distances kxu −
xv k2 . This question arises in sensor network positioning [HB01, OMK10], imaging [CSC12, SS11],
manifold learning [TDSL00], to name only a few applications. It is often the case that measurements
are only available for pairs u, v ∈ [n] that are close enough, e.g. only if kxu − xv k2 ≤ ρ for ρ a
certain communication range [Sin08, JM13].
Graph localization can be interpreted as a group synchronization problem in multiple ways.
First, we can interpret the unknown position xv as a translation and hence view it as a synchronization problem over the group of translations in d dimensions. Alternatively we can adopt a
divide-and-conquer approach following [CSC12]. First, we consider cliques in the graph and find
their relative positions. Then we reconstruct the relative orientations of various cliques, which can
be formulated as an SO(d) synchronization problem.
Community detection and the symmetric stochastic block model. The k-groups symmetric stochastic
block model is a random graph over n vertices generated as follows [Moo17, Abb17]. First, partition
the vertex set into k subsets of size n/k, uniformly at random. Then connect vertices independently,
conditional on the partition. Two vertices are connected with probability p if they belong to the
same subset, and with a smaller probability q < p otherwise. Given a realization of this graph, we
would like to identify the partition. This problem is in fact closely related to synchronizations over
Zk (the group of integers modulo k). Extensions of the stochastic block model where edges are

2

endowed with labels have also been considered [LMX15]. In particular the so-called censored block
model considered in [SLKZ15] corresponds precisely to Example 1.1 on an Erdős-Rényi graph.
The literature on group synchronization is fairly recent and rapidly growing. The articles
[Sin11, WS13] discuss it in a variety of applications and propose several synchronization algorithms,
mostly based on spectral methods or semidefinite programming (SDP) relaxations. Theoretical
analysis — mostly in the case of random (or complete) graphs G — is developed in [ABBS14,
BSAB14, JMRT16, PWBM16]. Most of these studies use perturbation theoretic arguments which
crucially rely on the fact that the Laplacian (or connection Laplacian, [BSS13]) of the underlying
graph has a spectral gap. This paper shows that nontrivial recovery is possible even in the absence of
a spectral gap, as in the case of grids with d ≥ 3, whose Laplacian pseudoinverses have appropriately
bounded trace rather than norm.
In the present paper we are interested in G being the d-dimensional grid1 , d ≥ 2. Namely,
V = Zd , and –to be definite– we orient edges in the positive direction:

E ≡ (x, y) : y − x ∈ {e1 , . . . , ed } ,
(1.4)
where ei = (0, · · · , 0, 1, 0, . . . , 0) is the i-th element of the canonical basis in Rd . We expect other
d-dimensional graphs (e.g. random geometric graphs) to present a qualitatively similar behavior.
By construction, we can hope to determine the unknowns (θ x )x∈Zd only up to a global action
by a group element. In other words, we cannot distinguish between (θ x )x∈Zd and (gθ x )x∈Zd for
some g ∈ G. We thus ask the following weak recovery question:
Is it possible to estimate θ −1
x θ y better than random guessing, as kx − yk2 → ∞?
Note that, in absence of noise (i.e. if Y uv = θ −1
u θ v exactly), the answer is always positive: we can
multiply the observations Y uv ’s along any path connecting x to y to reconstruct exactly θ −1
x θy .
However for any arbitrarily small noise level, errors add up along the path and this simple procedure
is equivalent to random guessing for kx − yk2 → ∞. The weak recovery question hence amounts to
asking whether we can avoid error propagation.
Focusing on the case of compact matrix groups, we will present the following main results:
Low noise, d ≥ 3. For sufficiently low noise, we prove that weak recovery is possible for d ≥ 3
and any group.
High noise. Vice-versa, weak recovery is impossible in any dimension at sufficiently high noise
(or for d = 1 at any positive noise).
Discrete groups. For the special case of Z2 -synchronization, we prove that weak recovery is
possible (at low enough noise) for all d ≥ 2. We expect the same to hold generally for other
discrete groups.
Continuous groups, d = 2. Vice-versa, for the simplest continuous group, SO(2), we prove that
weak recovery is impossible for d = 2.
The above pattern is completely analogous to the one of phase transitions in spin models within
statistical physics [Geo11]. We refer to Section 3 for a discussion of the connection with statistical
physics.
1

The case d = 1 is somewhat trivial.

3

The rest of the paper is organized as follows. Section 2 presents formal definitions and statements
of our main results. In order to achieve optimal synchronization, it is natural to consider the
Bayes posterior of the unknowns (θ v )v∈V , cf. Section 3. While this does not lead directly to
efficient algorithms, it clarifies the connection with statistical physics. Some useful intuition can
be developed by considering the case2 in which θv ∈ R and Yuv = θv − θu + Zuv with (Zuv )(u,v)∈E
i.i.d. noise. This can be treated by elementary methods, cf. Section 4. Finally, Section 5 and 6
prove our positive results (reconstruction is possible) with other proofs deferred to the appendices.
Notations. Throughout the paper we use boldface symbols (e.g. θ x , Y xy ) to denote elements of
the group G, and normal symbols for other quantities (including vectors and matrices).

2

Main results

As mentioned above, G = (V, E) will be the infinite d-dimensional grid, and G a compact matrix
group. Without loss of generality, we will assume G ⊆ O(m) (the group of m × m orthogonal
matrices). We attach to each vertex x ∈ V an element θ x ∈ G which may be deterministic or
random chosen independently from some distribution.
We are given observations Y = (Y xy )(x,y)∈E , Y xy ∈ G, that are conditionally independent
given θ. We assume that observations are unbiased in the following sense:
E{Y xy |θ} = λ θ −1
x θy ,

(2.1)

where the parameter λ ∈ [0, 1] is a natural measure of the signal-to-noise ratio. In particular, λ = 1
corresponds to noiseless observations. The two examples given in the introduction fit this general
definition:
• For Z2 synchronization (cf. Example 1.1) we have E{Y xy |θ} = (1 − 2p) θ −1
x θ y , and therefore
λ = (1 − 2p).
2
• For O(m) synchronization (cf. Example 1.2) we have E{Y xy |θ} = λ(σ 2 ) θ −1
x θ y where σ 7→
λ(σ 2 ) is a continuous function on [0, ∞) with λ(σ 2 ) → 1 as σ 2 → 0 and λ(σ 2 ) → 1 as σ 2 → ∞
(see Appendix A).

A simple mechanism to produce the noisy observations Y xy consists in introducing a probability
kernel Q on G and stipulate that, for each edge (x, y),
−1
P(Y x,y ∈ · |θ) = P(Y x,y ∈ · |θ −1
x θ y ) = Q( · |θ x θ y ) .

(2.2)

In other words, all observations are obtained by passing θ −1
x θ y through the same noisy channel.
While our results do not necessarily assume this structure, both of the examples given above are
of this type.
An estimator is a collection of measurable functions Tuv : Y 7→ Tu,v (Y ) ∈ G indexed by all
vertex pairs u, v ∈ V (here Y = (Y xy )(x,y)∈E denotes the set of all observations).
2
Strictly speaking, this is not a special case of the problem studied in the rest of the paper, because G = R is not
a compact group.

4

Definition 2.1. We say that the weak recovery problem is solvable for the probability distribution
P over (θ, Y ) defined above if there exists an estimator T , and ε > 0, such that


≥ ε > 0.
(2.3)
lim inf P θ x Txy (Y )θ −1
y ∈ · − PHaar ·
kx−yk→∞

TV

Our first result establishes that the problem is solvable if noise is small enough in d ≥ 3
dimensions.
Theorem 1. If d ≥ 3, then there exists λUB ∈ (0, 1) such that, if λ > λUB then the weak recovery
problem is solvable.
If noise is strong enough, the problem becomes unsolvable.
Theorem 2. Assume that:
1. P(Y x,y ∈ · |θ) = P(Y x,y ∈ · |θ −1
x θ y ).
2. P(Y x,y ∈ · |θ −1
x θ y ) has density q(y|θ 0 ), θ 0 ∈ G with respect to the Haar probability measure.
Let pc (d) ∈ (0, 1] the critical threshold for percolation on the d-dimensional grid. If
inf q(y|θ 0 ) > 1 − pc (d) ,

y,θ0

(2.4)

then the weak recovery problem is not solvable.
In particular, for d = 1, the recovery is not solvable as soon as the noise is strictly positive
inf y,θ q(y|θ) > 0 (since pc (d = 1) = 1).
In d = 2 the situation is more complicated. For certain discrete groups the problem is solvable
at low enough noise: we consider here the case G = Z2 , but we expect the same conclusion to
hold more generally. A result related to the next one was established in [HM82] using a Peierls
argument (Section 3 outlines the connection with the statistical physics formulation). We present
here an independent proof that also provides an efficient recovery algorithm.
Theorem 3. Consider d = 2, and G = Z2 , with uniform flip probability p. Then there exists
p∗ ∈ (0, 1) such that, if p ≤ p∗ then the weak recovery problem is solvable.
On the contrary, we expect that weak recovery is not possible in d = 2 dimensions, for continuous
groups even for very weak noise. This is analogous to the celebrated Mermin-Wagner theorem in
statistical mechanics [MW66, Mer67]. For the sake of simplicity, we focus on the case of G =
SO(2) which is isomorphic to U(1), the group of complex variables of unit modulus, with ordinary
multiplication. Let Z a U(1)-valued random variable with density g satisfying
g ∈ C 2,

inf

s∈[0,2π]

g(eis ) > 0 .

(2.5)

We consider observation on the edges corrupted by multiplicative noise
Y xy = θ −1
x θ y Zxy ,

(2.6)

where (Zxy )(x,y)∈E ∼iid g.
Theorem 4. If d = 2 and G = SO(2) with noise model satisfying (2.5) and (2.6), then the weak
recovery problem is not solvable.
5

3

Bayesian posterior and connection to statistical physics

In this section it is convenient to assume a more general model in which the observations Y xy ∈
Rm×m are not necessarily elements of the matrix group G. We assume that the conditional distribution of the observations Y xy given the unknowns θ x is absolutely continuous with respect to
a reference measure P# (independent of θ). In practice, we will take P# to be either the Haar
measure on G, or the Lebesgue measure on Rm×m . We denote the corresponding density by

1
dP
(Y x,y |θ) =
exp − u(θ −1
x θ y ; Y xy ) .
dP#
Z0

(3.1)

where u : G × Rm×m → R ∪ {+∞} is a measurable function bounded below. Applying Bayes
formula, we can write the posterior µY (B) = P(θ ∈ B|Y ) as
n
o
X
1
exp −
u(θ −1
(3.2)
µY (dθ) =
x θ y ; Y xy ) µ0 (dθ) ,
Z(Y )
(x,y)∈E

where µ0 (dθ) = µ0 (dθ1 ) · · · µ0 (dθ n ) is the product Haar measure over the unknowns and Z(Y ) is
a normalization constant. The joint distribution (3.2) takes the form of a Gibbs measure on the
graph G.
Remark 3.1. For Eq. (3.2) to make sense, the graph G needs to be finite. However, the Bayesian
interpretation implies immediately that quantities of interest have a well defined limit over increasing sequences of graphs. In particular, we can take G to be the finite grid with vertex set
V = {−L, . . . , L}d , and edges E = {(x, y) ∈ V × V : y − x ∈ {e1 , . . . , ed }}. Then the quantity
sup
Txy ( · )


P θ x Txy (Y )θ −1
y ∈ · − PHaar

·



(3.3)
TV

is obviously non-decreasing in L (because larger L corresponds to a larger class of estimators) and
hence admits a well defined limit. We will refer succinctly to this L → ∞ limit as the model on
‘the d-dimensional grid’.
In the rest of this section, it will be useful to distinguish between the arguments of the posterior
density (that we will keep denoting by (θ x )x∈V ), and the true unknowns that we will denote by
(θ 0,x )x∈V . We further assume that the function u satisfies
u(θτ ; Y ) = u(τ ; θ −1 Y ) = u(θ; Y τ −1 ).

(3.4)

for any θ, τ ∈ G and any Y ∈ Rm×m . This condition is verified by all of our examples. Thanks
to this symmetry, for any {τ x }x∈V and any Y , the distribution µY ( · ) of θ in (3.2) coincides with
−1
that of {θ x τ −1
x }x∈V where θ is distributed according to µỸ (·), and Ỹ xy = τ x Y xy τ y . By taking
τ x = θ 0,x for all x, we can assume that θ 0,x = I m for all x, which then leads to the (Y xy )(xy)∈E
being i.i.d. with common distribution
Y xy ∼


1
exp − u(I m ; Y xy ) P# (dY xy ) .
Z1

(3.5)

In the jargon of statistical physics, Gibbs measures of the form (3.2) with associated parameters
distribution (3.5) are known as spin-glasses on the ‘Nishimori line.’ These were first introduced
6

for the case θ x ∈ {+1, −1} [Nis81] and subsequently generalized to other groups in [GHLDB85].
Several results about spin glasses on the Nishimori line were derived in [ON93, Nis01] and the
connection with Bayesian statistics was emphasized in [Iba99, Mon08]. The weak recovery phase
transition corresponds to a paramagnetic-ferromagnetic phase transition in physics language.
Example 3.2. The simplest example is the so-called random bond Ising model which is obtained
by taking θ x ∈ {+1, −1} and
o
n X
1
(3.6)
exp β
Y xy θ x θ y ,
µY (θ) =
Z(Y )
(x,y)∈E

where Y xy = +1 with probability 1 − p and Y xy = −1 with probability p. The Nishimori line is
given by the condition β = (1/2) log((1 − p)/p). It is easy to see that this is equivalent to the Bayes
posterior for the Z2 synchronization model of Example 1.1, if we take θ 0,x = +1.
This model has attracted considerable interest within statistical physics. In particular, highprecision numerical estimates of the phase transition location yield pc ≈ 0.1092 (in d = 2) and
pc ≈ 0.233 (in d = 3) [PTPV09, HTPV07].
Example 3.3. Take G = O(m) (the group of orthogonal matrices), and assume
Y xy = θ −1
0,x θ 0,y + σ Z xy

(3.7)

where Z xy is a noise matrix with i.i.d. entries (Z xy )ij ∼ N(0, 1). This model is analogous to the
one of Example 1.2, although we do not project observations onto the orthogonal group.
After a simple calculation, the Gibbs measure (3.2) takes the form
n X
o
1
T
exp β
Tr θ x Y xy θ y
µ0 (dθ) ,
(3.8)
µY (dθ) =
Z(Y )
(x,y)∈E

where β = 1/σ 2 . By the symmetry under O(m) rotations, for the purpose of analysis we can assume
Y xy = I m + σ Z xy which is the usual setting in physics.
Example 3.4. In the case G = SO(2) we can identify θ x with an angle in [0, 2π), and let
Y xy = θ 0,y − θ 0,x + Z xy ,

mod 2π ,

(3.9)

where Z xy is noise with density proportional to exp(−u(z)) for u(z) a periodic function bounded
below.
The Gibbs measure (3.2) takes the form
n
X
o
1
(3.10)
µY (dθ) =
exp −
u Y xy − θ y + θ x µ0 (dθ) .
Z(Y )
(x,y)∈E

For the purpose of analysis we can assume Y xy = Z xy . This is known as the ‘XY model’ in physics.
Our results have direct implications on these models that we summarize in the following statement.
Corollary 3.1. Consider the Gibbs measure (3.2) on the d-dimensional grid, with parameters
Y xy ∈ G distributed according to Eq. (3.5) and satisfying Eq. (2.1). Then, the following hold:
7

1. For d ≥ 3, and G ⊆ O(m) is any compact matrix group, then there exists λUB < 1 such that
the model is in a ferromagnetic phase for any λ > λUB .
2. For the case of Example 3.2 (i.e. G = Z2 ) and d ≥ 2, there exists p∗ ∈ (0, 1) such that the
model is in a ferromagnetic phase for any p ≤ p∗ .
3. For the case of Example 3.4 (i.e. G = SO(2)) and d = 2 the model is not in a ferromagnetic
phase provided z 7→ u(z) is bounded.
4. For any group G, d ≥ 2, there exists a constant c(d) such that, if kuk∞ ≤ c(d) then the model
is not in a ferromagnetic phase.
Furthermore point 1 applies to Example 3.3 as well.
Proof. These statements are merely a translation of Theorems 1, 2, 3, 4 for the case in which channel
observations take values in G. For the case in Example 3.3, note that we can always project Y xy
onto the group O(m), hence recovering the setting of Example 1.2. Since weak recovery is possible
in the latter, it is also possible in the former.
As already pointed out in Section 2, the existence of a ferromagnetic phase for Example 3.2
(i.e. G = Z2 ) was already obtain in [HM82]. Note however that [HM82] estabilish existence
of a spontaneous magnetization, while here we prove the existence of long range point-to-point
correlation, which is equivalent to weak recovery.

4

A toy example

It is instructive to consider a simple example in which G = R is the group of translations on the
real line. This case does not fit the framework of the rest of this paper, but presents the same
dichotomy between d = 2 and d ≥ 3 and can be solved by elementary methods.
Throughout this section, we adopt additive notation, and hence the observation on edge (x, y)
takes the form
Yx,y = θy − θx + Zx,y .

(4.1)

where {Zxy }(x,y)∈E are i.i.d. random variables with mean 0 and variance σ 2 .
To simplify our treatment, we assume the graph to be the discrete torus, with vertex set
V = {1, 2, . . . , L}d and edges E = {(x, x + ej ) : x ∈ V, j ∈ {1, . . . , d}} (where we identify L + 1
with 1). Denoting by D the difference operator on G, the observation can be written as
Y = Dθ + Z .

(4.2)

As usual, θ can be determined only up to a global shift. To resolve this ambiguity, it is convenient
to assume that θ is centered: hθ, 1i = 0. Consider the least square estimator θ̂(Y ) = D † Y = DL† Y
where † denotes the pseudoinverse. A standard calculation [Was13, Theorem 13.13] yields the
following formula for the mean square error
1
E{kθ(Y ) − θk22 }
Ld
 σ2

σ2
= d Tr0 (D T D)† = d Tr0 L† .
L
L

MSE(L, σ 2 ) ≡

8

(4.3)
(4.4)

Here we denoted by L = D T D the Laplacian of G and by Tr0 the trace on the subspace orthogonal
to the all-ones vector. The eigenpairs of the Laplacian are [Moh97]:
v(p)x =

Hence

1

eihp,xi ,

λ(p) =

d
X
[2 − 2 cos(p)] ,

Ld/2
i=1
o
n 2π
(n1 , . . . , nd ) : ni ∈ {0, . . . , L − 1} .
p ∈ BL ≡
L
MSE(L, σ 2 ) =

σ2
Ld

X

p∈BL \{0}

1
.
λ(p)

(4.5)
(4.6)

(4.7)

For large L, the sum can be estimated by approximating it via Riemann integrals to yield the
following fact.
Fact 4.1. The mean square error of least-square estimation within the translation synchronization
model of Eq. (4.1) is

L

for d = 1,
 12 + OL (1)
1
2
1
MSE(L, σ ) = 2π log L + OL (1) for d = 2,
(4.8)

σ2

C(d) + oL (1)
for d ≥ 3.
where C(d) is a dimension dependent constant.

We observe that this qualitative behavior is the same that we obtain for continuous compact
groups, cf. Theorem 1 and Theorem 4: the weak recovery problem is solvable only for d ≥ 3.

5

Proof of Theorem 1

Throughout this section we assume a probability distribution P over θ, Y satisfying the unbiasedness condition Eq. (2.1). For most of our analysis, we consider general estimators Tuv : Y 7→
Tuv (Y ) ∈ Rm×m whose output is not necessarily in G, and let T uv = Tuv (Y ) (as projecting them
into G at the end can only increase their accuracy). Also, we set u(n) = (n, . . . , n) ∈ Zd , and
denote by P+ the set of infinite increasing paths in the grid, that start at 0.
Throughout the proof, we will use repeatedly the following two elementary facts. First, for any
two matrices A, B,kABkF ≤ kAkF kBkF . Second, if B is an orthogonal matrix, then kABkF =
kAkF .
We start by defining the estimator Tx,y (Y ) for x = 0, y = u(n), and will then generalize it to
other pairs x, y.
Lemma 5.1. Consider d ≥ 3. Then there exists an estimator T = (Tu,v ), and absolute constants
λ0 < 1, C0 such that, for all λ > λ0 and all even n,

E θ 0 T 0,u(n) θ −1
(5.1)
u(n) = I m ,
n
o
2
E θ 0 T 0,u(n) θ −1
(5.2)
u(n) − I m F ≤ C0 m(1 − λ) .
9

Proof. Benjamini, Pemantle and Peres [BPP+ 98] construct a probability measure µ over paths in
P+ satisfying the so called exponential intersection property (EIT). Namely, there exist absolute
constants β∗ < 1, C∗ such that
(µ × µ){(γ1 , γ2 ) ∈ P+ × P+ : |γ1 ∩ γ2 | ≥ k} ≤ C∗ β∗k .

(5.3)

Let P+ (v) be the set of increasing paths starting at 0 and ending at v ∈ Zd . For n even, we construct
a probability measure µn over P+ (u(n)) as follows. Define the hyperplane H(n) = {(x1 , x2 , x3 ) ∈
R3 : x1 + x2 + x3 = 3n/2}, and let Rn (x1 , x2 , x3 ) = (n − x1 , n − x2 , n − x3 ) denote the reflection
with respect to this hyperplane. For γ ∼ µ, let γ (1,n) denote the path obtained by stopping γ when
it hits H(n), and denote by γ (n) its extension obtained by reflecting the with respect to H(n).
We let µn be the probability distribution of γ (n) (note that γ (n) ends at u(n) by construction). It
follows immediately from Eq. (5.3) that µn satisfies the EIT for some new absolute constants C, β,
that are independent of n:
µn × µn {(γ1 , γ2 ) ∈ P+ (u(n)) × P+ (u(n)) : |γ1 ∩ γ2 | ≥ k} ≤ Cβ k .

(5.4)

For a path γ ∈ P+ (u(n)), denote the ordered sequence of directed edges in γ by I1 (γ), . . . , I3n (γ),
where Ij (γ) ∈ E, j ∈ [3n], and define
Y γ := Y I1 (γ) Y I2 (γ) · · · Y I3n (γ) ,
1
T 0,u := 3n Eγ (Y γ ) ,
λ

(5.5)
(5.6)

where Eγ denotes expectation with respect to µn . Note that by the assumption (2.1) we have
EY γ = λ3n θ −1
0 θ u(n) for any γ ∈ P+ (u(n)) and therefore
ET 0,u(n) = θ −1
0 θ u(n) .

(5.7)

Observe that if two paths γ1 , γ2 in P+ (u(n)) intersect in an edge e then they must intersect in the
same position since the paths are increasing, i.e. we must have e = Ik (γ1 ) = Ik (γ2 ) for some k.
Writing for simplicity u = u(n), and denoting by Eγ1 ,γ2 expectation with respect to γ1 , γ2 ∼iid µn

1
T
E T 0,u T T
0,u = 6n Eγ1 ,γ2 EY γ1 (Y γ2 )
λ
1
T
T
= 6n Eγ1 ,γ2 EY I1 (γ1 ) . . . (EY I3n (γ1 ) Y T
I3n (γ2 ) )Y I3n−1 (γ2 ) . . . Y I1 (γ2 )
λ
(a) 1
= 6n Eγ1 ,γ2 λ|γ1 |+|γ2 |−2|γ1 ∩γ2 | I m
λ
= Eγ1 ,γ2 λ−2|γ1 ∩γ2 | I m .
where (a) follows by repeatedly applying the identity Y e Y T
e = Im for any edge e, each time an
intersection appears, and taking expectation
with
respect
to
Y e1 , Y e2 fornot repeated edges. By

this last expression, the trace τ of E T 0,u T T
reads
τ
=
m E λ−2X where X is a random
0,u
variable counting the number of intersections in two paths γ1 , γ2 independently drawn from µn .

10

Thus for λ2 > β,
m−1 τ =

X

λ−2x [P(X ≥ x) − P(X ≥ x + 1)]

(5.8)

X

(5.9)

x≥0

=1+

x>0



P(X ≥ x) λ−2x − λ−2x+2

≤ 1 + (1 − λ2 )

X

C β/λ2

x>0

2

= 1 + (1 − λ )

Cβ
,
λ2 − β

x

where the inequality follows from Eq. (5.4). Thus
o
n
o
n

2
−1
T
E θ 0 T 0,u θ −1
+m
= Tr E θ 0 T 0,u T T
u − Im F
0,u θ 0 − 2Tr E θ 0 T 0,u θ u
=τ −m

≤ (1 − λ2 )m

Cβ
,
λ2 − β

(5.10)
(5.11)

(5.12)
(5.13)
(5.14)

where we used Eq. (5.7) together with our previous bound on τ . The second statement of the
Lemma follows.
Lemma 5.2. Consider any d ≥ 3 and fix ε > 0. For n ∈ N, j ∈ {1, . . . , d}, let v(j, n) ≡ n ej Then
there exists an estimator T = (Tu,v )u,v∈V , and a constant λ(ε) < 1, such that, for all λ > λ(ǫ) and
all n,
n
o
P θ 0 T 0,v(j,n) θ −1
−
I
≥
ε
≤ ε.
(5.15)
m
v(j,n)
F

Proof. Without loss of generality, assume j = 1, and set for simplicity v(n) = v(j, n). Consider
(∗)
first the case of n even and let w(n) ≡ (n/2, n/2, n/2, 0, . . . , 0). Let (T x,y )x,y∈V be the estimator
of Lemma 5.1 (where we use only the observations on the subgraph induced by the hyperplane
{x ∈ Zd : x4 = · · · = xd = 0}). Define
(∗)

(∗)

T 0,v(n) = T 0,w(n) T w(n),v(n) .

(5.16)

1 + kX 1 X 2 − IkF ≤ (1 + kX 1 − IkF )(1 + kX 2 − IkF ),

(5.17)

From the inequality

we get



(∗)
(∗)
−1
−1
−
Ik
θ
1
+
kθ
T
−
Ik
θ
−
Ik
≤
1
+
kθ
T
kθ 0 T 0,v(n) θ −1
F − 1.
F
F
0 0,w(n) w(n)
w(n) w(n),v(n) v(n)
v(n)

By Lemma 5.1 and Markov’s inequality, the probability that one of the Frobenius norms in the righthand side exceeds δ > 0 is at most C0 m(1−λ)/δ2 . Thus with probability at least 1−2C0 m(1−λ)/δ2 ,
one has
2
kθ 0 T 0,v(n) θ −1
v(n) − IkF ≤ (1 + δ) − 1.
The right-hand side is at most 3δ for δ ≤ 1. The announced result follows for the choice λ(ε) =
1 − ε3 /(18mC0 ).
11

We can now prove our main result, that is a strengthening of Theorem 1.
Theorem 5. Consider any d ≥ 3 and fix ε > 0. Then there exists an estimator T = (Tu,v )u,v∈V ,
and a constant λd (ε) < 1, such that, for all λ > λd and all n,
n
o
P θ x T x,y θ −1
−
I
≥
ε
≤ ε.
(5.18)
m F
y

Proof. Without loss of generality, assume x = 0. Further, for j ∈ {0, . . . , d} define w(j) ≡
(#)
(y1 , . . . , yj , 0, . . . , 0). In particular, w(0) = 0 and w(d) = y. Let (T x,y ) be the estimator of
Lemma 5.2, and define
(#)

(#)

(#)

T 0,y = T w(0),w(1) T w(1),w(2) · · · T w(d−1),w(d) .
By Lemma 5.2, for all λ > λ(ε0 ) we have

(#)
P max θ w(j−1) T w(j−1),w(j)θ −1
w(j) − I m
1≤j≤d

F


≥ ε0 ≤ d ε0 .

(5.19)

(5.20)

By repeated application of Inequality (5.17), on the complement of the event in the right-hand side,
one has
kθ 0 T 0,y θ −1
y

d 

Y
(#)
−
I
k
+
1
− 1 ≤ ε0 2d .
kθ w(j−1) T w(j−1),w(j)θ −1
− I mk ≤
m
w(j)
j=1

The claim follows by taking ε0 = ε/(2d ) and by setting λd (ε) = λ(ε/2d ).

6

Proof of Theorem 3

We give a multi-scale scheme to reconstruct the unknowns θ = (θ x )x∈Z2 . Without loss of generality
we will consider pairs of vertices u, v in the positive quadrant. For k ≥ 0 let ℓk = 210k(k+1) . We
partition the lattice Z2 into blocks of side-length ℓk as follows,
Bu(k) = {(x1 , x2 ) ∈ Z2 : ui = ⌈xi /ℓk ⌉}

(6.1)

Let B (k) be the set of blocks at level k and let Du,k denote the unique block in B (k) containing u.
(k)
For each block B ∈ B (k) we will define synchronization random variables WB ∈ {−1, 1} that are
Q
(k)
(k)
measurable with respect to {Y xy }x,y∈B . Our estimate for θ u θ −1
v is
k≥0 WDu,k WDv,k . For some
(k)

(k)

large enough k⋆ we have that Du,k⋆ = Dv,k⋆ and so WDu,k WDv,k = 1 for all k ≥ k⋆ . The product of
synchronization variables at u up to level k will be denoted as
W̃u(k) =

k
Y

(ℓ)

WDu,ℓ .

(6.2)

ℓ=1

We say that two blocks B, B ′ ∈ B (k) are adjacent (denoted B ∼ B ′ ) if there exist x ∈ B, x ∈ B ′
such that (x, x′ ) ∈ E. In this case there are exactly ℓk such pairs. We say that B ∼ B ′ is an honest
edge if the following event holds

 X
9
(k)
′
ℓk .
(6.3)
Y xx′ θ x θ x′ ≥
A (B, B ) =
10
′
′
x∈B,x ∈B

12

This condition will mean that edges between vertices along the cut will be informative as we try to
synchronize them.
Next we recursively define the set of good level k blocks G (k) . A block B ∈ B (k) is good if
• There is at most one bad (k − 1)-level sub-block of B, that is
o
n
(k−1)
(k−1)
≤ 1.
Bi ∈ B
: Bi ⊂ B, Bi 6∈ G

(6.4)

• All level k − 1 sub-block edges are honest,
\

(6.5)

A(k−1) (B1 , B2 ) .

B1 ,B2 ∈B(k−1)
B1 ,B2 ⊂B, B1 ∼B2

Claim 6.1. There exists p⋆ > 0 such that, if 0 < p < p⋆ then for all B ∈ B (k)
P(B ∈ G (k) ) ≥ 1 − 2−200k−200 .

(6.6)

Proof. We will establish (6.6) inductively. Note that blocks at level 0 are good. First we estimate
1
the probability that the honest edge condition holds. Assuming that p⋆ ≤ 40
,




9
P A(k−1) (B1 , B2 ) = P Bin(ℓk−1 , 1 − p) ≥ ℓk−1
10




9
39
≥ P Bin(ℓk−1 , ) ≥ ℓk−1 ≥ 1 − exp −κ210k(k−1)
40
10
for some κ > 0. Thus



P A(k−1) (B1 , B2 ) ≥ 1 − 2−400k−800

(6.7)

for all sufficiently large k. By taking p⋆ small enough equation (6.7) holds for small k as well and
thus for all k. Hence, since there are 240k level k − 1 sub-blocks in each level k block we have that,



P


\

∈B(k−1)

B1 ,B2
B1 ,B2 ⊂B


40k+1
· 2−400(k−1)−800 ≥ 1 − 2−200k−201 .
A(k) (B1 , B2 )
 ≥1−2

(6.8)

Since there are no bad sub-blocks at level 0 this implies (6.6) for k = 1. For some k ≥ 2, assume
inductively that equation (6.6) holds up to k − 1. Then, since the event that blocks are good are
independent, for B ∈ B (k) ,
o



n
P
B ′ ∈ B (k−1) : B ′ ⊂ B, B ′ ∈
/ G (k−1) ≥ 2 = P Bin(240k , 2−200(k−1)−200 ) ≥ 2
 40k 
2
(2−200k )2 ≤ 2−320k ≤ 2−200k−240 .
≤
2
Combining with equation (6.8) we have that
P(B ∈ G (k) ) ≥ 1 − 2−200k−200 ,
as required.
13

(k)

Next we describe how to inductively construct the synchronization variables WB
block B ∗ . For B1 ∼ B2 k-level sub-blocks of B ∗ we let


X
Y B1 ,B2 = sign 
W̃x(k) W̃y(k) Y xy 

in a k + 1

B1 ∋x∼y∈B2

(k)

We assign the WB as follows:
1. A quartet is a collection of 4 sub-blocks B1 ∼ B2 ∼ B3 ∼ B4 ∼ B1 that form a square of side
Q
(k)
length 2ℓk . A quartet is incoherent if 4i=1 Y Bi ,Bi+1 = −1 where we take B5 = B1 . Let IB ∗
(k)

be the set of sub-blocks of B ∗ that appear in no incoherent quartets. It is possible for IB ∗ to
(k)
be disconnected, in that case take IB ∗ to be the largest component.
(k)

(k)

(k)

2. If possible, assign WB for all B ∈ IB ∗ such that for all adjacent sub-blocks B1 , B2 ∈ IB ∗ we
have that
(k)
(k)
WB1 WB2 = Y B1 ,B2
(6.9)
(k+1)

Denote the event that such an assignment is possible as HB ∗ . If such an assignment is not
(k)
(k)
(k)
possible set all the WB = 1. Set WB = 1 for all B ∈ (IB ∗ )c .
(k)

In the following we will write I = I (k) = IB ∗ omitting arguments when clear from the context. Note
(k)
(k+1)
that on the event HB ∗ , the WB can be found efficiently by assigning the variables iteratively to
satisfy equation (6.9).
Claim 6.2. For k ≥ 1, if B ∈ G (k) is good then the following hold:
(k)

1. HB holds.
(k)

2. There exists a random variable SB ∈ {−1, 1} such that if x ∈ B and on the event
k−1
\n
j=0

o
{Dx,j ∈ G (j) } ∩ {Dx,j ∈ I (j) }

we have that

(k)

θ x = SB W̃x(k) .
3. Furthermore, for any B ′ ∈ G (k) with B ′ ∼ B,
X
(k)
SB W̃x(k) θ x ≥ (1 − 2−8 + 2−10k )ℓk .

(6.10)

(6.11)

(6.12)

x∈B∩∂B ′

(Here ∂B ′ ≡ {x ∈ Z2 : dist(x, B ′ ) = 1}.)
(k)

Note that we do not (and cannot) construct SB and observe that it is used in the analysis
but not the construction. It accounts for the fact that we can only hope to recover the θ u up to a
global multiplicative shift.
14

Proof of Claim 6.2. We proceed inductively. In the base case when k = 0 for x = B ∈ G (0) we may
(0)
(0)
set Sx = θ x . With the convention that an empty product is 1 we have that W̃x = 1 and so
θ x = Sx(0) W̃x(0) .
Now we assume the claim holds for all k′ < k and consider a good block B ∈ G (k) .
1. For any good (k − 1)-level sub-blocks, B1 ∼ B2 in B


X
Y B1 ,B2 = sign 
W̃x(k−1) W̃y(k−1) Y xy 
B1 ∋x∼y∈B2



(k−1) (k−1)
SB2

= sign SB1

(k−1)

X

SB1

(k−1)

W̃x(k−1) SB2

B1 ∋x∼y∈B2



W̃y(k−1) Y xy 

(6.13)

Our inductive hypothesis implies that there are at most 2−8 ℓk−1 vertices x in this sum with
(k−1)
(k−1)
SB
W̃x
6= θ x , thus
X
X
(k−1)
(k−1)
SB1 W̃x(k−1) SB2 W̃y(k−1) Y xy ≥
θ x θ y Y xy − 4 · 2−8 ℓk−1 ,
(6.14)
B1 ∋x∼y∈B2

B1 ∋x∼y∈B2

and so since A(k−1) (B1 , B2 ) holds,
X

(k−1)
(k−1)
SB1 W̃x(k−1) SB2 W̃y(k−1) Y xy

≥

B1 ∋x∼y∈B2




9
−8
−4·2
ℓk−1 > 0 .
10

(6.15)

Combining with equation (6.13) we have that


(k−1) (k−1)
.
Y B1 ,B2 = sign SB1 SB2

(6.16)

It follows that every quartet of good sub-blocks is coherent. If all of the (k − 1)-level quartets
(k−1)
(related by a
of sub-blocks of B are coherent then there are exactly two assignments of WBi
(k−1)

(k−1)

multiplicative factor of −1) satisfying WB1 WB2
= Y B1 ,B2 . If there is one or more incoherent
quartet, this must include the single bad sub-block. The sub-blocks in I are good and there exist
(k)
(k)
two assignments satisfying WB1 WB2 = Y B1 ,B2 for all B1 , B2 ∈ I which are,
(k−1)

WBi

(k−1)

≡ SBi

or

(k−1)

WBi

(k−1)

≡ −SBi

.

(6.17)
(k)

(k)

(k)

In either case the procedure will construct WBi satisfying (6.17) on I and HB holds. We set SB
so that
(k−1)
(k−1)
(k)
≡ SBi .
SB WBi
2. To verify condition (6.11) we see that for x ∈ Bi ,
(k)

(k)

(k)

(k−1)

SB W̃x(k) = SB WBi W̃x(k−1) = SBi
where the last equality used the inductive hypothesis.
15

W̃x(k−1) = θ x ,

3. It remains to check the condition on the boundary of B adjacent to some good block B ′ . Since
any sub-block in I c must be in a quartet with a bad sub-block, there are at most 3 on any side of
B. Thus, summing over sub-blocks Bi of B we have that
X
X
X
(k)
(k)
SB W̃x(k) θ x =
SB W̃x(k) θ x
x∈B∩∂B ′

Bi :Bi ∼B ′ x∈Bi ∩∂B ′

≥

X

(k)

X

SB W̃x(k) θ x − 3ℓk−1

Bi ∈I:Bi ∼B ′ Bi ∋x∼y∈B ′

≥ (1 − 2−8 + 2−10(k−1) )ℓk−1 (220k − 3) − 3ℓk−1
≥ (1 − 2−8 + 2−10k )ℓk
which establishes (6.12).
By the proceeding claim, if u and v are in the same k-level block on the event
(k)
Juv
=

k−1
\n
j=0

o
{Du,j , Dv,j ∈ G (k) } ∩ {Du,j , Dv,j ∈ I}

we have that

(k)

(k)

W̃u(k−1) W̃v(k−1) = θ u SB θ v SB = θ u θ v .
(k−1)

(6.18)

(k−1)

so W̃u
W̃v
correctly recovers θ u θ v . A sufficient condition for Du,k ∈ G (k) ∩ I is that Du,k
and the 8 sub-blocks surrounding it are all good. Thus
(k)
)≥1−
P(Juv

X

18 P(Du,k ∈ G (k) ) ≥ 1 − 18

k ′ ≥1

X

2−200k−200 ≥

k ′ ≥1

Thus
P(W̃u(k−1) W̃v(k−1) = θ u θ v ) ≥
and so the success probability of recovery is at least
and v which completes the proof of Theorem 3.

8
10

>

1
2

9
.
10

8
10

independent of the distance between u

Acknowledgements
This work was partially supported by the following grants: NSF CAREERAward CCF-1552131,
NSF CSOI CCF-0939370 (E.A.); NSF CCF-1319979, NSF DMS-1613091 (A.M); NSF CCF-1553751
and a Sloan Research Fellowship (N.S). We thank the American Institute of Mathematics (San Jose,
CA) where part of this work was carried out.

A

Proof of Eq. (2.1) for O(m) synchronization

Here we prove the remark that –under the model of Example 1.2– E{Y xy |θ} = λ(σ 2 ) θ −1
x θ y . Fixing
for simplicity x = 1, y = 2 and dropping the indices x, y unless necessary, we have Y = Ũ Ṽ
T
X̃ = θ −1
1 θ 2 + σZ has singular value decomposition X̃ = Ũ ΣṼ .
16

T

where

T
T
2
Let X = θ 1 X̃θ −1
2 = U ΣV . Our claim is equivalent to E{U V |θ} = λ(σ )I. By rotational
invariance of the Gaussian distribution, we have X = I + σ G̃ for (Gij )1≤i,j≤m ∼iid N(0, 1) or
–equivalently– X = QT (I + σ G)Q for any Q in O(m). Using the last representation, E =
E{U V T |θ} = E{QT U V T Q|θ} for I + σ G = U ΣV T . This implies that QT EQ = E for any
orthogonal matrix Q, which can hold only if E = λI for some scalar λ.
Continuity and the limit values of λ(σ 2 ) are straightforward.

B

Proof of Theorem 2

Let p ≡ 1 − inf y,θ0 q(y|θ 0 ). We can write the conditional probability density q(y|θ 0 ) as
q(y|θ 0 ) = (1 − p) + p q∗ (y|θ) .

(B.1)

Hence observations (Y xy )(x,y)∈E can be generated as follows. First draw independent random
variables (Uxy )(x,y)∈E ∼iid Bernoulli(p). Then, for each (x, y) ∈ E such that Uxy = 1, draw
an independent observation Y xy ∼ q∗ ( · |θ −1
x θ y ). For (x, y) ∈ E such that Uxy = 0, draw Y xy
according to the Haar measure.
To upper bound the total variation distance in Eq (2.3) we consider the easier problem in which
instead of Y , we are given all the Bernoulli variables U = (Uxy )(x,y)∈E and, for each (x, y) ∈ E such
that Uxy = 1 we are given the group difference Dxy = θ −1
x θ y . Denoting by D = {D xy }(x,y)∈E,Uxy =1 ,
we then have




P θ x Txy (Y )θ −1
≤ sup P θ x Txy (U ; D)θ −1
. (B.2)
y ∈ · − PHaar ·
y ∈ · − PHaar ·
TV

TV

Texy

Consider the percolation process defined by the variables U (whereby edge (x, y) ∈ E is open if
Uxy = 1), and denote by x ∼U y the event that x and y are in the same percolation cluster. If x and
y are not in the same percolation cluster, then the conditional distribution of θ−1
x θ y conditional on
U ; D is uniformly on G. This implies that


≤ P(x ∼U y) .
(B.3)
P θ x Txy (Y )θ −1
y ∈ · − PHaar ·
TV

For p < pc (d), the right hand side goes to 0 as kx − yk → ∞ [Gri89], which yields the claim.

C

Proof of Theorem 4

For s ∈ R and Z ∼ g( · ), we define
ψ(s) = kP Zeis ∈ · − P Z ∈ · k2L2 (g) =

Z

=

Z





2π
0
2π
0

!2
g(ei(t−s) )
− 1 g(ei(t) ) dt
g(ei(t) )
!2
g(ei(t−s) )
g(ei(t) ) dt − 1 .
i(t)
g(e )

(C.1)

Note that ψ(s) is twice differentiable, nonnegative and that ψ(0) = 0 so ψ ′ (s) = 0 and for some
κ = κ(g) > 0,
|ψ(s)| ≤ κ|s|2 .
17

(C.2)

Let u, v ∈ Z2 with L = ku − vk2 , and define the function h : Z2 → R by

log 1 + min(kx − uk2 ; L)
.
h(x) = 1 −
log(L + 1)

(C.3)

2

Note that h(u) = 1, h(v) = 0 and h(x) = 0 for kx − uk2 ≥ L. Fix θ ∈ U(1)Z , s ∈ [0, 2π) and define
(s)
θ (s) by letting θ x = eis θ x . Denote by Pθ (Y ∈ · ) the conditional distribution of the observations
given hidden variables θ. We then have, for a constant C,


Pθ(s) Y ∈ · − Pθ Y ∈ ·

2
TV

 2

≤ Pθ(s) Y ∈ · − Pθ Y ∈ ·
L2
Y 


=
1 + Pνs Y xy ∈ · − Pν0 Y xy ∈ ·
(x,y)∈E

=

Y

(x,y)∈E

≤

Y

(x,y)∈E

≤

Y

(x,y)∈E
kx−uk≤L

(C.4)
2
L2


1 + ψ s(h(x) − h(y)) − 1

C
(1 + kx − uk2 ) log2 L

−1

(C.5)
(C.6)


1 + κ s2 |h(x) − h(y)|2 ) − 1

1+





(C.7)
−1

= O(1/ log L).

(C.8)

(C.9)

Taking expectation over s uniformly random in [0, 2π) (denoted by Es ), we have, for any measurable
set B,


(s),−1
Es Pθ(s) θ u Tuv (Y )θ v ∈ B = Es Pθ(s) θ (s)
∈ eis B ,
(C.10)
u Tuv (Y )θ v
and therefore



(s),−1
= O(log(1/L)) .
∈ eis B − Pθ θ u Tuv (Y )θ −1
Es Pθ(s) θ (s)
v ∈B
u Tuv (Y )θ v

(C.11)

We next take expectation with respect to (θ x )x∈Z2 i.i.d. uniform in U(1). Note that under this
distribution, also (θ x )x∈Z2 are i.i.d. uniform in U(1). Letting P( · ) = EPθ ( · ), we have


is
−1
= O(log(1/L)) .
Es P θ u Tuv (Y )θ −1
v ∈ e B − P θ u Tuv (Y )θ v ∈ B

(C.12)


Pθ θ u Tuv (Y )θ −1
v ∈ B − PHaar (B) = O(log(1/L)) .

(C.13)

For any fixed B, ξ, Ps (ξ ∈ eis B) = PHaar (B) and hence we get

This proves the impossibility of weak recovery.

References
[Abb17]

Emmanuel Abbe, Community detection and stochastic block models: recent developments, arXiv:1703.10146 (2017).
18

[ABBS14]

Emmanuel Abbe, Afonso S Bandeira, Annina Bracher, and Amit Singer, Decoding
binary node labels from censored edge measurements: Phase transition and efficient
recovery, IEEE Transactions on Network Science and Engineering 1 (2014), no. 1,
10–22.

[BPP+ 98]

Itai Benjamini, Robin Pemantle, Yuval Peres, et al., Unpredictable paths and percolation, The Annals of Probability 26 (1998), no. 3, 1198–1211.

[BSAB14]

Nicolas Boumal, Amit Singer, P-A Absil, and Vincent D Blondel, Cramér–rao bounds
for synchronization of rotations, Information and Inference 3 (2014), no. 1, 1–39.

[BSS13]

Afonso S Bandeira, Amit Singer, and Daniel A Spielman, A cheeger inequality for the
graph connection laplacian, SIAM Journal on Matrix Analysis and Applications 34
(2013), no. 4, 1611–1630.

[CMG13]

Avishek Chatterjee and Venu Madhav Govindu, Efficient and robust large-scale rotation averaging, Proceedings of the IEEE International Conference on Computer Vision,
2013, pp. 521–528.

[CSC12]

Mihai Cucuringu, Amit Singer, and David Cowburn, Eigenvector synchronization,
graph rigidity and the molecule problem, Information and Inference 1 (2012), no. 1,
21–67.

[Geo11]

Hans-Otto Georgii, Gibbs measures and phase transitions, vol. 9, Walter de Gruyter,
2011.

[GHLDB85] Antoine Georges, David Hansel, Pierre Le Doussal, and Jean-Philippe Bouchaud, Exact properties of spin glasses. ii. nishimori’s line: new results and physical implications, Journal de Physique 46 (1985), no. 11, 1827–1836.
[Gri89]

Geoffrey Grimmett, Percolation?, Springer, 1989.

[HB01]

Jeffrey Hightower and Gaetano Borriello, Location systems for ubiquitous computing,
Computer 34 (2001), no. 8, 57–66.

[HM82]

T Horiguchi and T Morita, Existence of the ferromagnetic phase in a random-bond
Ising model on the square lattice, Journal of Physics A: Mathematical and General 15
(1982), no. 2, L75.

[HTPV07]

Martin Hasenbusch, Francesco Parisen Toldin, Andrea Pelissetto, and Ettore Vicari, Critical behavior of the three-dimensional ±J Ising model at the paramagneticferromagnetic transition line, Physical Review B 76 (2007), no. 9, 094402.

[Iba99]

Yukito Iba, The nishimori line and bayesian statistics, Journal of Physics A: Mathematical and General 32 (1999), no. 21, 3875.

[JM13]

Adel Javanmard and Andrea Montanari, Localization from incomplete noisy distance
measurements, Foundations of Computational Mathematics 13 (2013), no. 3, 297–345.

19

[JMRT16]

Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi, Phase transitions
in semidefinite relaxations, Proceedings of the National Academy of Sciences 113
(2016), no. 16, E2218–E2223.

[LMX15]

Marc Lelarge, Laurent Massoulié, and Jiaming Xu, Reconstruction in the labelled
stochastic block model, IEEE Transactions on Network Science and Engineering 2
(2015), no. 4, 152163.

[Mer67]

N David Mermin, Absence of ordering in certain classical systems, Journal of Mathematical Physics 8 (1967), no. 5, 1061–1064.

[MMM13]

Pierre Moulon, Pascal Monasse, and Renaud Marlet, Global fusion of relative motions
for robust, accurate and scalable structure from motion, Proceedings of the IEEE
International Conference on Computer Vision, 2013, pp. 3248–3255.

[Moh97]

Bojan Mohar, Some applications of laplace eigenvalues of graphs, Graph symmetry,
Springer, 1997, pp. 225–275.

[Mon08]

Andrea Montanari, Estimating random variables from random sparse observations,
European Transactions on Telecommunications 19 (2008), no. 4, 385–403.

[Moo17]

Cristopher Moore, The computer science and physics of community detection: landscapes, phase transitions, and hardness, arXiv:1702.00467 (2017).

[MW66]

N David Mermin and Herbert Wagner, Absence of ferromagnetism or antiferromagnetism in one-or two-dimensional isotropic heisenberg models, Physical Review Letters
17 (1966), no. 22, 1133.

[Nis81]

Hidetoshi Nishimori, Internal energy, specific heat and correlation function of the bondrandom Ising model, Progress of Theoretical Physics 66 (1981), no. 4, 1169–1181.

[Nis01]

, Statistical physics of spin glasses and information processing: an introduction,
vol. 111, Clarendon Press, 2001.

[OMK10]

Sewoong Oh, Andrea Montanari, and Amin Karbasi, Sensor network localization from
local connectivity: Performance analysis for the mds-map algorithm, Information Theory (ITW 2010, Cairo), 2010 IEEE Information Theory Workshop on, IEEE, 2010,
pp. 1–5.

[ON93]

Y Ozeki and Hidetoshi Nishimori, Phase diagram of gauge glasses, Journal of Physics
A: Mathematical and General 26 (1993), no. 14, 3399.

[OS15]

Onur Ozyesil and Amit Singer, Robust camera location estimation by convex programming, Proceedings of the IEEE Conference on Computer Vision and Pattern
Recognition, 2015, pp. 2674–2683.

[PTPV09]

Francesco Parisen Toldin, Andrea Pelissetto, and Ettore Vicari, Strong-disorder
paramagnetic-ferromagnetic fixed point in the square-lattice ±J Ising model, Journal
of Statistical Physics 135 (2009), no. 5, 1039–1061.

20

[PWBM16] Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra, Messagepassing algorithms for synchronization problems over compact groups, arXiv:1610.04583
(2016).
[Sin08]

Amit Singer, A remark on global positioning from local distances, Proceedings of the
National Academy of Sciences 105 (2008), no. 28, 9507–9511.

[Sin11]

, Angular synchronization by eigenvectors and semidefinite programming, Applied and computational harmonic analysis 30 (2011), no. 1, 20–36.

[SLKZ15]

Alaa Saade, Marc Lelarge, Florent Krzakala, and Zdeborová, Spectral detection in the
censored block model, IEEE International Symposium on Information Theory (ISIT),
2015, p. 11841188.

[SS11]

Amit Singer and Yoel Shkolnisky, Three-dimensional structure determination from
common lines in cryo-em by eigenvectors and semidefinite programming, SIAM journal
on imaging sciences 4 (2011), no. 2, 543–572.

[TDSL00]

Joshua B Tenenbaum, Vin De Silva, and John C Langford, A global geometric framework for nonlinear dimensionality reduction, science 290 (2000), no. 5500, 2319–2323.

[Was13]

Larry Wasserman, All of statistics: a concise course in statistical inference, Springer
Science & Business Media, 2013.

[WBS16]

Kyle Wilson, David Bindel, and Noah Snavely, When is rotations averaging hard?,
European Conference on Computer Vision, Springer, 2016, pp. 255–270.

[WS13]

Lanhui Wang and Amit Singer, Exact and stable recovery of rotations for robust synchronization, Information and Inference (2013), iat005.

21

