Phase Transitions in Semidefinite Relaxations

Introduction

Many information processing tasks can be formulated as optimization problems. This idea has been central to data analysis and statistics at least since Gauss and Legendre’s invention of the least-squares method in the early 19th century [Gau09].

Modern datasets pose new challenges to this centuries’ old framework. On the one hand, high-dimensional applications require to estimate simultaneously millions of parameters. Examples span genomics [BDSY99], imaging [P+09], web-services [KBV09], and so on. On the other hand, the unknown object to be estimated has often a combinatorial structure: In clustering we aim at estimating a partition of the data points [VL07]. Network analysis tasks usually require to identify a discrete subset of nodes in a graph [GN02, KMM+13]. Parsimonious data explanations are sought by imposing combinatorial sparsity constraints [Was00].

There is an obvious tension between the above requirements. While efficient algorithms are needed to estimate a large number of parameters, the maximum likelihood method often requires to solve NP-hard combinatorial optimizations. A flourishing line of work addresses this conundrum by designing effective convex relaxations of these combinatorial problems [Tib96, CDS98, CT10].

Unfortunately, the statistical properties of such convex relaxations are well understood only in a few cases (compressed sensing being the most important success story [DT05, CT07, DMM09, ALMT14]). In this paper we use tools from statistical mechanics to develop a precise picture of the behavior of a class of semidefinite programming relaxations. Relaxations of this type appear to be surprisingly effective in a variety of problems ranging from clustering to graph synchronization. For the sake of concreteness we will focus on three specific problems:

(Note that entries on the diagonal carry no information.) Here $\bm{x_{0}}\in\{+1,-1\}^{n}$, $\bm{x_{0}}^{*}$ denote the transpose of $\bm{x_{0}}$, and $\bm{W}=(W_{ij})_{i,j\leq n}$ is a random matrix from the Gaussian Orthogonal Ensemble (GOE), i.e. a symmetric matrix with independent entries (up to symmetry) $(W_{ij})_{1\leq i<j\leq n}\sim_{i.i.d.}{\sf N}(0,1/n)$ and $(W_{ii})_{1\leq i\leq n}\sim_{i.i.d.}{\sf N}(0,2/n)$.

Here $a>b>0$ are model parameters that will be kept of order one as $n\to\infty$. This corresponds to a random graph with bounded average degree $d=(a+b)/2$, and a cluster (a.k.a. ‘block’ or ‘community’) structure corresponding to the partition $V_{+}\cup V_{-}$. Given a realization of such a graph, we are interested in estimating the underlying partition.

A generalization of this problem to the case of more than two blocks has been studied since the eighties as a model for social network structure [HLL83], under the name of ‘stochastic block model.’ For the sake of simplicity, we will focus here on the two-blocks case.

Illustrations

Classical statistical theory suggests two natural reference estimators: the Bayes-optimal and the maximum likelihood estimators. We will discuss these methods first, in order to set the stage for SDP relaxations.

Bayes-optimal estimator (a.k.a. minimum MSE). This provides a lower bound on the performance of any other approach. It takes the conditional expectation of the unknown signal given the observations:

Explicit formulas are given in Supplementary Information (SI). We note that $\bm{\hat{x}}^{\mbox{\tiny{Bayes}}}(\bm{Y})$ assumes knowledge of the prior distribution. The red-dashed curve in Fig. 1 presents our analytical prediction for the asymptotic MSE for $\bm{\hat{x}}^{\mbox{\tiny{Bayes}}}(\,\cdot\,)$. Notice that ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{Bayes}}})=1$ for all $\lambda\leq 1$ and ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{Bayes}}})<1$ strictly for all $\lambda>1$, with ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{Bayes}}})\to 0$ quickly as $\lambda\to\infty$. The point $\lambda_{c}^{\mbox{\tiny{Bayes}}}=1$ corresponds to a phase transition for optimal estimation, and no method can have non-trivial ${\rm MSE}$ for $\lambda\leq\lambda_{c}^{\mbox{\tiny{Bayes}}}$.

Maximum likelihood (MLE). The estimator $\bm{\hat{x}}^{\mbox{\tiny{ML}}}(Y)$ is given by the solution of

Here $c(\lambda)$ is a scaling factorIn practical applications, $\lambda$ might not be known. We are not concerned by this at the moment, since maximum likelihood is used as a idealized benchmark here. Note that, strictly speaking, this is a ‘scaled’ maximum likelihood estimator. We prefer to scale $\bm{\hat{x}}^{\mbox{\tiny{ML}}}(\bm{Y})$ in order to keep ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{ML}}})\in$. that is chosen according to the asymptotic theory as to minimize the MSE. As for the Bayes-optimal curve, we obtain ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{ML}}})=1$ for $\lambda\leq\lambda_{c}^{\mbox{\tiny{ML}}}=1$ and ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{ML}}})<1$ (and rapidly decaying to 0) for $\lambda>\lambda_{c}^{\mbox{\tiny{ML}}}$ . (We refer to the SI for this result.)

We use $\langle\,\cdot\,,\cdot\,\rangle$ to denote the scalar product between matrices, namely $\langle\bm{A},\bm{B}\rangle\equiv{\sf Tr}(\bm{A}^{*}\bm{B})$, and $\bm{A}\succeq 0$ to indicate that $\bm{A}$ is positive semidefiniteRecall that a symmetric matrix $\bm{A}$ is said to be PSD if all of its eigenvalues are non-negative. (PSD). If we assume $\bm{X}={\bm{x}}{\bm{x}}^{*}$, the SDP (288) reduces to the maximum-likelihood problem (5). By dropping this condition, we obtain a convex optimization problem that is solvable in polynomial time. Given an optimizer $\bm{X}_{\mbox{\tiny{opt}}}=\bm{X}_{\mbox{\tiny{opt}}}(\bm{Y})$ of this convex problem, we need to produce a vector estimate. We follow a different strategy from standard ‘rounding’ methods in computer science, which is motivated by our analysis below. We compute the eigenvalue decomposition $\bm{X}_{\mbox{\tiny{opt}}}=\sum_{i=1}^{n}\xi_{i}\,{\bm{v}}_{i}{\bm{v}}_{i}^{*}$, with eigenvalues $\xi_{1}\geq\xi_{2}\geq\dots\geq\xi_{n}\geq 0$, and eigenvectors ${\bm{v}}_{i}={\bm{v}}_{i}(\bm{X}_{\mbox{\tiny{opt}}}(\bm{Y}))$, with $\|{\bm{v}}_{i}\|_{2}=1$. We then return the estimate

with $c^{\mbox{\tiny{SDP}}}(\lambda)$ a certain scaling factor, see SI.

Our analytical prediction for ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{SDP}}})$ is plotted as blue solid line in Fig. 1. Dots report the results of numerical simulations with this relaxation for increasing problem dimensions. The asymptotic theory appears to capture very well these data already for $n=200$. For further comparison, alongside the above estimators, we report the asymptotic prediction for ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{PCA}}})$, the mean square error of principal component analysis. This method simply returns the principal eigenvector of $\bm{Y}$, suitably rescaled (see SI).

Figure 1 reveals several interesting features:

Phase transition for optimal estimation. Bayes-optimal estimation achieves non-trivial accuracy as soon as $\lambda>\lambda_{c}^{\mbox{\tiny{Bayes}}}=1$. The same is achieved by a method as simple as PCA (blue-dashed curve). On the other hand, for $\lambda<1$ no method can achieve a mean square error that is asymptotically smaller than one (the latter can be achieved trivially by returning $\bm{\hat{x}}=0$.)

Suboptimality of PCA at large signal strength. PCA can be implemented efficiently, but does not exploit the information $x_{0,i}\in\{+1,-1\}$. As a consequence, its estimation error is significantly sub-optimal at large $\lambda$ (see SI).

Near-optimality of SDP relaxations. The tractable estimator $\bm{\hat{x}}^{\mbox{\tiny{SDP}}}(\bm{Y})$ achieves the best of both worlds. Its phase transition coincides with the Bayes-optimal one $\lambda_{c}^{\mbox{\tiny{Bayes}}}=1$, and ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{SDP}}})$ decays exponentially at large $\lambda$, staying close to ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{Bayes}}})$ and strictly smaller than ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{PCA}}})$, for $\lambda\geq 1$.

We believe that the above features are generic: as shown in the SI, $U(1)$ synchronization confirms this expectation.

Figures 2 illustrates our results for the community detection problem under the hidden partition model of Eq. (287). Recall that we encode the ground truth by a vector $\bm{x_{0}}\in\{+1,-1\}^{n}$. In the present context, an estimator is required to return a partition of the vertices of the graph. Formally, it is a function on the space of graphs with $n$ vertices ${\mathcal{G}}_{n}$, namely $\bm{\hat{x}}:{\mathcal{G}}_{n}\to\{+1,-1\}^{n}$, $G\mapsto\bm{\hat{x}}(G)$. We will measure the performances of such an estimator through the overlap:

where ${\mathbf{1}}=(1,1,\dots,1)$ is the all-ones vector. Once more, this problem is hard to approximate [Kho06], which motivates the following SDP relaxation:

Let us emphasize a few features of Figure 2:

Superiority of SDP to PCA. A sequence of recent papers (see [KMM+13] and references therein) demonstrate that classical spectral methods –such as PCA– fail to detect the hidden partition in graphs with bounded average degree. In contrast, Figure 2 shows that a standard SDP relaxation does not break down in the sparse regime. See [MS15] for rigorous evidence towards the same conclusion.

Near optimality of SDP. As proven in [MNS12], no estimator can achieve ${\rm Overlap}_{n}(\bm{\hat{x}})\geq\delta>0$ as $n\to\infty$, if $\lambda=(a-b)/\sqrt{2(a+b)}<1$.

Figure 2 (and the theory developed in the next section) suggests that SDP has a phase transition threshold. Namely, there exists $\lambda_{c}^{\mbox{\tiny{SDP}}}=\lambda_{c}^{\mbox{\tiny{SDP}}}(d)$ such that, if

then SDP achieves overlap bounded away from zero: ${\rm Overlap}(\bm{\hat{x}}^{\mbox{\tiny{SDP}}})>0$. The figure also suggests $\lambda_{c}^{\mbox{\tiny{SDP}}}(5)\approx\lambda_{c}^{\mbox{\tiny{Bayes}}}=1$, i.e. SDP is nearly optimal.

Below we will derive an accurate approximation for the critical point $\lambda_{c}^{\mbox{\tiny{SDP}}}(d)$. The factor $\lambda_{c}^{\mbox{\tiny{SDP}}}(d)$ measures the sub-optimality of SDP for graphs of average degree $d$.

Figure 3 plots our prediction for the function $\lambda_{c}^{\mbox{\tiny{SDP}}}(d)$, together with empirically determined values for this threshold, obtained through Monte Carlo experiments for $d\in\{2,5,10\}$ (red circles). These were obtained by running the SDP estimator on randomly generated graphs with size up to $n=64,000$ (total CPU time was about $10$ years). In particular, we obtain $\lambda_{c}^{\mbox{\tiny{SDP}}}(d)>1$ strictly, but the gap $\lambda_{c}^{\mbox{\tiny{SDP}}}(d)-1$ is very small (at most of the order of $2\%$) for all $d$. This confirms in a precise quantitative way the conclusion that SDP is nearly optimal for the hidden partition problem.

Simulations results are in broad agreement with our predictions, but present small discrepancies (below $0.5\%$). These discrepancies might be due to the extrapolation form finite-$n$ simulations to $n\to\infty$, or to the inaccuracy of our analytical calculation.

Analytical results

Our analysis is based on a connection with statistical mechanics. The models arising from this connection are spin models in the so-called ‘large-$N$’ limit, a topic of intense study across statistical mechanics and quantum field theory [BW93]. Here we exploit this connection to apply non-rigorous but sophisticated tools from the theory of mean field spin glasses [MM09, MPV87]. The paper [MS15] provides partial rigorous evidence towards the predictions developed here.

A crucial question is how the solution of (49) depends on the spin dimensionality $m$, for $m\ll n$. Denote by ${\rm OPT}(\bm{Y};m)$ the optimum value when the dimension is $m$ (in particular ${\rm OPT}(\bm{Y};m)$ is also the value of (288) for $m\geq n$). It was proven in [MS15] that there exists a constant $C$ independent of $m$ and $n$ such that

with probability converging to one as $n\to\infty$ (whereby $\bm{Y}$ is chosen with any of the distributions studied in the present paper). The upper bound in Eq. (14) follows immediately from the definition. The lower bound is a generalization of the celebrated Grothendieck inequality from functional analysis [KN12].

The above inequalities imply that we can obtain information about the SDP (288) in the $n\to\infty$ limit, by taking $m\to\infty$ after $n\to\infty$. This is the asymptotic regime usually studied in physics under the term ‘large-$N$ limit.’

Finally, we can associate to the problem (49) a finite-temperature Gibbs measure as follows:

where $p_{0}({\rm d}{\bm{\sigma}}_{i})$ is the uniform measure over the $m$-dimensional sphere $S^{m-1}$, and $\Re(z)$ denotes the real part of $z$. This allows to treat in a unified framework all of the estimators introduced above. The optimization problem (49) is recovered by taking the limit $\beta\to\infty$ (with maximum likelihood for $m=1$ and SDP for $m\to\infty$). The Bayes-optimal estimator is recovered by setting $m=1$ and $\beta=\lambda/2$ (in the real case) or $\beta=\lambda$ (in the complex case).

The cavity method from spin-glass theory can be used to analyze the asymptotic structure of the Gibbs measure (42) as $n\to\infty$. Below we will state the predictions of our approach for the SDP estimator $\bm{\hat{x}}^{\mbox{\tiny{SDP}}}$.

Here we list the main steps of our analysis for the expert reader, deferring a complete derivation to the SI:

We use the cavity method to derive the ‘replica symmetric’ predictions for the model (42) in the limit $n\to\infty$.

By setting $m=1$, $\beta=\lambda/2$ (in the real case) or $\beta=\lambda$ (in the complex case) we obtain the Bayes-optimal error ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{Bayes}}})$: on the basis of [DAM15], we expect the replica symmetric assumption to hold, and these predictions to be exact. (See also [LKZ15] for related work.)

By setting $m=1$ and $\beta\to\infty$ we obtain a prediction for the error of maximum likelihood estimation ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{ML}}})$. While this prediction is not expected to be exact (because of replica symmetry breaking), it should be nevertheless rather accurate, especially for large $\lambda$.

By setting $m\to\infty$ and $\beta\to\infty$, we obtain the SDP estimation error ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{SDP}}})$, which is our main object of interest. Notice that the inversion of limits $m\to\infty$ and $n\to\infty$ is justified (at the level of objective value) by Grothendieck inequality. Further, since the $m=\infty$ case is equivalent to a convex program, we expect the replica symmetric prediction to be exact in this case.

These equations can be solved by iteration, after approximating the expectations on the right-hand side numerically. The properties of the SDP estimator can be derived from this solution. Concretely, we have

The corresponding curve is plotted in Figure 2.

For $\nu$ a probability measure on $S^{m-1}$ and $R$ an orthogonal (or unitary) matrix, let $\nu^{R}$ be the measure obtained byFormally, $\nu^{R}({\bm{\sigma}}\in A)\equiv\nu(R^{-1}{\bm{\sigma}}\in A)$. ‘rotating’ $\nu$. Finally, let $p^{(m,\beta)}_{i(1),\dots,i(k)}$ denote the joint distribution of ${\bm{\sigma}}_{i(1)},\cdots,{\bm{\sigma}}_{i(k)}$ under $p_{m,\beta}$. Then, for any fixed $k$, and any sequence of $k$-uples $(i(1),\dots,i(k))_{n}\in[n]$, we have

Here ${\rm d}R$ denotes the uniform (Haar) measure on the orthogonal group, $\Rightarrow$ denotes convergence in distribution (note that $p^{(m,\beta)}_{i(1),\dots,i(k)}$ is a random variable), and ${\bm{\xi}}_{1},\dots,{\bm{\xi}}_{k}\sim_{iid}{\sf N}(\mu\,{\bm{e}}_{1},{\bm{Q}})$ with ${\bm{Q}}={\rm diag}(q,q_{0}\dots,q_{0})$, $q_{0}=(1-q)/(m-1)$.

3 Cavity method: Community detection in sparse graphs

The main change with respect to the dense case is that the phase transition at $\lambda=1$, is slightly shifted, as per Eq. (12). Namely, SDP can detect the hidden partition with high probability if and only if $\lambda\geq\lambda_{c}^{\mbox{\tiny{SDP}}}(d)$, for some $\lambda_{c}^{\mbox{\tiny{SDP}}}(d)>1$.

The quantity ${\sf c}_{*}$ has a beautiful interpretation. Consider a (rooted) Galton-Watson tree with offspring distribution $d$, and imagine each edge to be a conductor with conductance equal to one. Then ${\sf c}_{*}$ is the total conductance between the root, and the boundary of the tree ‘at infinity.’ In particular, ${\sf c}_{*}=0$ almost surely for $d\leq 1$, and ${\sf c}_{*}>0$ with positive probability if $d>1$ (see [LP13] and SI).

Next consider the distributional recursion

This value can be computed numerically, for instance by sampling the recursion (230). The results of such an evaluation are plotted as a continuous line in Figure 3.

Final algorithmic considerations

Let us emphasize that other polynomial-time algorithms can be used for the specific problems studied here. In the synchronization problem, naive PCA achieves the optimal threshold $\lambda=1$. In the community detection problem, several authors recently developed ingenious spectral algorithms that achieve the information theoretically optimal threshold $(a-b)/\sqrt{2(a+b)}=1$, see e.g. [DKMZ11, KMM+13, Mas14, MNS13, SKZ14].

In the SI, we compare the behavior of SDP and the Bethe Hessian algorithm of [SKZ14] for this perturbed model: while SDP appears to be rather insensitive to the perturbation, the performance of Bethe Hessian are severely degraded by it. We expect a similar fragility to arise in other spectral algorithms.

Acknowledgments

A.J. and A.M. were partially supported by NSF grants CCF-1319979 and DMS-1106627 and the AFOSR grant FA9550-13-1-0036.

References

Notations

The standard Gaussian density is denoted by $\phi(x)=e^{-x^{2}/2}/\sqrt{2\pi}$, and the Gaussian distribution by $\Phi(x)=\int_{-\infty}^{x}\phi(t)\,{\rm d}t$.

Given two un-normalized measures $p$ and $q$ on the same space, we write $p(s)\cong q(s)$ if they are equal up to an overall normalization constant. We use $\doteq$ to denote equality up to subexponential factors, i.e. $f(n)\doteq g(n)$ if $\lim_{n\to\infty}n^{-1}\log[f(n)/g(n)]=0$.

2 Estimation metrics

We also define the overlap as follows in the real case

In the complex case, we replace ${\rm sign}(z)$ by $z/|z|$ (defined to be at $z=0$):

This formula applies to the real case as well. (Note that, in the main text, we defined the overlap only for estimators taking values in $\{+1,-1\}^{n}$, in the real case. Throughout these notes, we generalize that definition for the sake of uniformity.)

Preliminary facts

where the expectation is with respect to the independent random variables $Z\sim{\sf N}(0,1)$, and $\sigma\sim p_{0}(\,\cdot\,)$.

Then we have the identity (with $Z\sim{\sf CN}(0,1)$ a complex normal)

Consider, to be definite, the real case, and define the observation model

where $\sigma\sim p_{0}(\,\cdot\,)$ independent of the noise $Z\sim{\sf N}(0,1)$. Then a straightforward calculation shows that

The identity (31) follows by exploiting the symmetry of $p_{0}$, which implies $f(-y;\gamma)=-f(y;\gamma)$.

The proof follows a similar argument in the complex case. ∎

We apply the above lemma to specific cases that will be of interest to us. Below, ${\rm I}_{k}(z)$ denotes the modified Bessel function of the second kind. Explicitly, for $k$ integer, we have the integral representation

For any $\gamma\geq 0$, we have the identities

where the expectation is with respect to $Z\sim{\sf N}(0,1)$ (first line) or $Z\sim{\sf CN}(0,1)$ (second line).

These follows from Lemma 6.1. For the first line we apply the real case (31) with $p_{0}=(1/2)\delta_{+1}+(1/2)\delta_{-1}$, whence

For the second line we apply the complex case (32) with $p_{0}$ the uniform measure over the unit circle. Consider the change of variables $y=|y|e^{j\phi}$ and $\sigma=e^{j(\phi+\theta)}$. Computing the curve integral, we have

where in the second equality we used the fact that $\int_{0}^{2\pi}e^{2\sqrt{\gamma}|y|\cos(\theta)}\sin(\theta){\rm d}\theta=0$. ∎

As explained in the main text, we are interested in the following probability measure over ${\bm{\sigma}}=({\bm{\sigma}}_{1},{\bm{\sigma}}_{2},\dots,{\bm{\sigma}}_{n})$, where ${\bm{\sigma}}_{i}\in S^{m-1}$:

Here $p_{0}({\rm d}{\bm{\sigma}}_{i})$ is the uniform measure over ${\bm{\sigma}}_{i}\in S^{m-1}$.

We define a general $m,\beta$ estimator as follows.

In order to break the ${\mathcal{O}}(m)$ symmetry, we add a term $\beta\sum_{i=1}^{n}\langle\bm{h},{\bm{\sigma}}\rangle$ in the exponent of Eq. (42), for $\bm{h}$ an arbitrary small vector. It is understood throughout that $\|\bm{h}\|_{2}\to 0$ after $n\to\infty$.

As is customary in statistical physics, we will not explicitly carry out calculations with the perturbation $\bm{h}\neq 0$, but only using this device to select the relevant solution at $\bm{h}=0$.

Note that for $\beta\to\infty$ this amounts to maximizing the exponent term in equation (42).

Let ${\bm{\widehat{u}}}$ be its principal eigenvector.

where $c=c(\lambda)$ is the optimal scaling predicted by the asymptotic theory.

The Gibbs measure (42) encodes several estimators of interests. Here we briefly describe this connections.

Bayes-optimal estimators. As mentioned in the main text, this is obtained by setting $m=1$ and $\beta=\lambda/2$ (in the real case) or $\beta=\lambda$ (in the complex case). To see this, recall our observation model (for $i<j$)

As claimed, this coincides with Eq. (42) if we set $\beta=\lambda/2$ (in the real case) or $\beta=\lambda$ (in the complex case).

Maximum-likelihood and SDP estimators. By letting $\beta\to\infty$ in Eq. (42), we obtain that $p_{\beta,m}$ concentrates on the maximizers of the problem

In the case $m\geq n$ we recover the SDP relaxation. In the case $m=1$, this is equivalent to the maximum likelihood problem

In this section we use the cavity method to derive the asymptotic properties of the measure (42).

In the replica-symmetric cavity method, we consider adding a single variable ${\bm{\sigma}}_{0}$ to a problem with $n$ variables ${\bm{\sigma}}_{1},{\bm{\sigma}}_{2},\dots,{\bm{\sigma}}_{n}$. We compute the marginal distribution of ${\bm{\sigma}}_{0}$ in the system with $n+1$ variables, to be denoted by $\nu^{n+1}_{0}({\rm d}{\bm{\sigma}}_{0})$. This is expressed in terms of the marginals of the other variables in the system with $n$ variables $\nu^{n}_{1}({\rm d}{\bm{\sigma}}_{0})$, …$\nu^{n}_{n}({\rm d}{\bm{\sigma}}_{1})$. We will finally impose the consistency condition that $\nu^{n+1}_{0}$ is distributed as any of $\nu^{n}_{1}$, …$\nu^{n}_{n}$ in the $n\to\infty$ limit.

Assuming that ${\bm{\sigma}}_{1}$, …${\bm{\sigma}}_{n}$ are, for this purpose, approximately independent, we get

Next we consider a fixed $k\in[n]$ and estimate the integral by expanding the exponential term. This expansion proceeds slightly different in the real and the complex cases. We give details for the first one, leaving the second to the reader. Write

where ${\rm E}_{k}(\,\cdot\,)\equiv\int(\,\cdot\,)\,\nu_{k}({\rm d}{\bm{\sigma}}_{k})$ denotes expectation with respect to $\nu_{k}$. Here, we used the fact that $Y_{ij}=O(1/\sqrt{n})$, as per equation (46).

Substituting in Eq. (51), and neglecting $O(n^{-1/2})$ terms, we get (both in the real and complex case)

We further have the following equations for ${\bm{\xi}}_{0}$, ${\bm{C}}_{0}$:

Notice that the expectations ${\rm E}_{k}(\,\cdot\,)$ on the right-hand side are in fact functions of ${\bm{\xi}}_{k}$, ${\bm{C}}_{k}$ through Eq. (52).

We next pass to studying the distribution of $\{{\bm{\xi}}_{k}\}$ and $\{{\bm{C}}_{k}\}$. For large $n$, the pairs $\{({\bm{\xi}}_{k},{\bm{C}}_{k})\}$ appearing on the right-hand side of Eqs. (53), (54) can be treated as independent. By the law of large numbers and central limit theorem, we obtain that

for some deterministic quantities ${\bm{\mu}}$, ${\bm{Q}}$, ${\bm{C}}$. Note that the law of ${\bm{\xi}}_{i}$ can be equivalently described by

where ${\bm{g}}=(g_{1},g_{2},\dots,g_{m})\sim{\sf N}(0,{\rm I}_{m})$.

Using these and the consistency condition in Eqs. (53), (54), we obtain the following equations for the unknowns ${\bm{\mu}},{\bm{Q}},{\bm{C}}$:

The prediction of the replica-symmetric cavity methods have been summarized in the main text. We generalize the discussion here. Assume, for simplicity $\bm{x_{0}}=(+1,\dots,+1)$. For $\nu$ a probability measure on $S^{m-1}$ and $R$ an orthogonal (or unitary) matrix, let $\nu^{R}$ be the measure obtained by ‘rotating’ $\nu$, i.e. $\nu^{R}({\bm{\sigma}}\in A)\equiv\nu(R^{-1}{\bm{\sigma}}\in A)$ for any measurable set $A$. Finally, let $p^{(m,\beta)}_{i(1),\dots,i(k)}$ denote the joint distribution of ${\bm{\sigma}}_{i(1)},\cdots,{\bm{\sigma}}_{i(k)}$ under $p_{m,\beta}$. Then, for any fixed $k$, and any sequence of $k$-tuples $(i(1),\dots,i(k))_{n}\in[n]$, we have

While in general this prediction is only a good approximation (because of replica symmetry breaking) we expect to be asymptotically exact for the Bayes-optimal, ML and SDP estimator. In the next sections we will discuss special estimators.

2.2 Bayes-optimal: m=1𝑚1m=1 and β∈{λ/2,λ}𝛽𝜆2𝜆\beta\in\{\lambda/2,\lambda\}

For $m=1$, ${\bm{\sigma}}=\sigma$ is a scalar satisfying $\sigma\sigma^{*}=|\sigma|^{2}=1$. Hence, the term proportional to ${\bm{C}}$ in Eq. (60) is a constant and can be dropped. Also ${\bm{\xi}}=\xi$, ${\bm{\mu}}=\mu$ and ${\bm{Q}}=q$ are scalar in this case.

We will write these equations below in terms of classical functions both in the real and in the complex cases. Before doing that, we derive expressions for the estimation error in the $n\to\infty$ limit. The estimator $\bm{\hat{x}}(\bm{Y})$ is given in this case by $\bm{\hat{x}}(\bm{Y})=\bm{\hat{x}}^{\beta,m=1}(\bm{Y})$, cf. Eq. (43). Therefore, the scaled MSE, cf. Eq. (27), reads

Note that the optimal scaling is $c=\mu/(\lambda q)$, leading to minimal error –for the ideally scaled estimator–

Real case. In this case ${\rm E}_{\xi}(\sigma)=\tanh(2\beta\xi)$ and therefore Eqs. (63), (64) yield

where expectation is with respect to $Z\sim{\sf N}(0,1)$. As discussed in Section 7.1, the Bayes optimal estimator is recovered by setting $\beta=\lambda/2$ above. Using the identity (38) in Corollary 6.2, we obtain the solution

where $\kappa$ satisfies the fixed point equation

We denote by $\kappa_{*}=\kappa_{*}(\lambda)$ the largest non-negative solution of this equation. Using Eqs. (67) and (70) we obtain the following predictions for the asymptotic estimation error

(Note that in this case, the optimal choice of a scaling is $c=1$.)

where, as mentioned above, ${\rm I}_{k}(z)$ denotes the modified Bessel function of the second kind.

The general fixed point equations (63) and (64) yield

As discussed in Section 7.1, the Bayes optimal estimator is recovered by setting $\beta=\lambda$ in these equations. In this case we can use the identity (39) in Corollary 6.2, to obtain the solution

where $\kappa$ satisfies the fixed point equation

where the expectation is taken with respect to $Z\sim{\sf CN}(0,1)$. We denote by $\kappa_{*}=\kappa_{*}(\lambda)$ the largest non-negative solution of these equations.

Using again Eqs. (67) and (70) , we obtain

2.3 Maximum likelihood: m=1𝑚1m=1 and β→∞→𝛽\beta\to\infty

As discussed in Section 7.1, the maximum likelihood estimator is recovered by setting $m=1$ and $\beta\to\infty$. Notice that in this case our results are only approximate because of replica symmetry breaking.

We can take the limit $\beta\to\infty$ in Eqs. (62), (63), (64). In this limit, the measure $\nu_{\xi}(\,\cdot\,)$ concentrates on the single point $\sigma^{*}=\xi/|\xi|\in S^{0}$. We thus obtain

We next specialize our discussion to the real and complex cases.

Real case. Specializing Eq. (84) to the real case, we get the equation

Taylor expanding near $\mu=0$, this yields $\mu=2\phi(0)\lambda\,\mu+O(\mu^{2})$ which yields the critical point (within the replica symmetric approximation)

We denote by $\mu_{*}=\mu_{*}(\lambda)$ the largest non-negative solution of Eq. (86). The asymptotic estimation metrics (for optimally scaled estimator) at level $\lambda$ are given by

It follows immediately from Eq. (86) that, as $\lambda\to\infty$, $\mu_{*}(\lambda)=\lambda[1-2\Phi(-\lambda)+O(\Phi(-\lambda)^{2})]$, whence

Complex case. Specializing Eq. (84), we get

Denoting by $\mu_{*}=\mu_{*}(\lambda)$ the largest non-negative solution of Eq. (92), the estimation metrics are obtained again via Eqs. (88) and (89).

For large $\lambda$, it is easy to get $\mu_{*}(\lambda)/\lambda=1-(4\lambda^{2})^{-1}+O(\lambda^{-3})$ whence

2.4 General m𝑚m and β→∞→𝛽\beta\to\infty

In the limit $\beta\to\infty$, the measure $\nu_{{\bm{\xi}},{\bm{C}}}(\,\cdot\,)$ of Eq. (60) concentrates on the single point ${\bm{\sigma}}_{*}({\bm{\xi}},{\bm{C}})$ that maximizes the exponent. A simple calculation yields

where $\rho$ is a Lagrange multiplier determined by the normalization condition $\|{\bm{\sigma}}_{*}\|_{2}=1$, or

Further $\nu_{{\bm{\xi}},{\bm{C}}}(\,\cdot\,)$ has variance of order $1/\beta$ around ${\bm{\sigma}}_{*}$.

In order to solve Eqs. (57) to (59) we next assume that the ${\mathcal{O}}(m)$ symmetry is –at most– broken vectorially to ${\mathcal{O}}(m-1)$. Without loss of generality, we can assume that it is broken along the direction ${\bm{e}}_{1}=(1,0,\dots,0)$. Further, since $\nu_{{\bm{\xi}},{\bm{C}}}(\,\cdot\,)$ is a measure on the unit sphere $\{{\bm{\sigma}}:\;\|{\bm{\sigma}}\|_{2}=1\}$, the matrix ${\bm{C}}$ is only defined up to a shift ${\bm{C}}-c_{0}{\rm I}$. This leads to the following ansatz for the order parameters.

and ${\bm{\sigma}}_{*}({\bm{\xi}},{\bm{C}})$ reads

Taking the limit $\beta\to\infty$ of Eqs. (57) to (59) we obtain the following four equations for the four parameters $\mu,r,q_{0},q_{1}$:

In the above expressions, expectation is with respect to the Gaussian vector ${\bm{Z}}=(Z_{1},\dots,Z_{m})\sim{\sf N}(0,{\rm I}_{m})$, and $\rho=\rho(Z_{1},\dots,Z_{m})$ is defined as the solution of the equation

The simplest derivation of these equations is obtained by differentiating the ground state energy, for which we defer to Section 7.3.

We can then compute the performance of the estimator $\bm{\hat{x}}^{(\beta,m)}$ defined at the beginning of this section. Note that ${\bm{\widehat{Q}}}\to{\bm{Q}}$ as $n\to\infty$, and therefore its principal vector is ${\bm{\widehat{u}}}\to{\bm{e}}_{1}$ (within the above ansatz), and therefore, for a test function $f$, we have

where $X_{0}\sim{\sf Unif}(S^{0})$ independent of $Z_{1}$.

Applying (107) and after a simple calculation we obtain

where $\mu_{*}(\lambda)$, $q_{1,*}(\lambda)$ denote the solutions of the above equations. Also, invoking (107) the asymptotic overlap is given by

Spin-glass phase. The spin-glass phase is described by the completely symmetric solution with $\mu=0$, $b=0$ and $q_{0}=q_{1}=1/m$. From Eq. (106) we get

Critical signal-to-noise ratio. We next compute the critical value of $\lambda$. We begin by expanding Eq. (106). Define

and let $\rho_{0}$ be the solution of the equation $1=F(\rho_{0})$. Notice that $\rho_{0}$ is unaltered under sign change $Z_{1}\to-Z_{1}$. Further, comparing with the equation for $\rho$, see Eq. (106), we obtain the following perturbative estimate

By the results for the spin glass phase, we have $q_{0},q_{1}\to(1/m)$ and $\rho,(\rho+r)\to\|{\bm{Z}}\|_{2}/\sqrt{m}$ as $\mu\to 0$, whence

Now consider Eq. (101). Retaining only $O(\mu)$ terms we get

where in the last step we used Eq. (113) and $q_{1}=1/m+o(1)$ as $\mu\to 0$. Now recalling that $\rho_{0}$ is even in $Z_{1}$, the second term vanishes and we obtain

We therefore get the critical point $\lambda_{\rm c}(m)$ by setting to $1$ the coefficient of $\mu$ above. In the real case, we get

Summarizing the (replica symmetric) critical point is

In particular, for $m=1$ we recover $\lambda^{\mbox{\tiny RS}}_{\rm c}(1)=\sqrt{\pi/2}$ for the real case, and $\lambda^{\mbox{\tiny RS}}_{\rm c}(1)=2/\sqrt{\pi}$ for the complex case. These are the values derived in Section 7.2.3. For large $m$, we get

with $s_{{\mathfrak{G}}}=1$ (real case), or $s_{{\mathfrak{G}}}=2$ (complex case).

Let us emphasize once more: we do not expect the replica symmetric calculation above to be exact, but only an excellent approximation. In other words, for any bounded $m$, we expect $\lambda_{\rm c}(m)\approx\lambda^{\mbox{\tiny RS}}_{\rm c}(m)$ but $\lambda_{\rm c}(m)\neq\lambda^{\mbox{\tiny RS}}_{\rm c}(m)$. However, as $m\to\infty$ the problem becomes convex, and hence we expect $\lim_{m\to\infty}|\lambda_{\rm c}(m)-\lambda^{\mbox{\tiny RS}}_{\rm c}(m)|=0$. Hence

2.5 SDP: m→∞→𝑚m\to\infty and β→∞→𝛽\beta\to\infty

In the limit $m\to\infty$, Eqs. (101) to (104) simplify somewhat. We set $q_{1}=q$ and eliminate $q_{0}$ using Eq. (105). Applying the law of large numbers, the equation for $\rho$ reads

As a consequence, $\rho$ becomes independent of $Z_{2}$. Hence, Eqs. (101) to (104) reduce to

Denoting by $\mu_{*}(\lambda)$ and $q_{*}(\lambda)$ the solutions to the above equations, we have

We solution of the above equations displays a phase transition at the critical point $\lambda_{c}^{\mbox{\tiny{SDP}}}=1$, which we next characterize.

Spin glass phase and critical point. The spin-glass phase corresponds to a symmetric solution $\mu=q=r=0$.

In order to investigate the critical behavior, we expand the equations (125) to (127) for $\lambda=1+{\varepsilon}$, ${\varepsilon}\ll 1$. To leading order in ${\varepsilon}$, we get the following solution

To check the above perturbative solution, note that expanding the denominator of Eq. (126) and using $\rho=1+O({\varepsilon}^{2})$, we get

Multiplying Eq. (124) by $\rho^{2}$ and expanding the right-hand side, we get

Finally, expanding Eq. (125) we get $r={\varepsilon}+O({\varepsilon}^{3/2})$.

3 Free energy and energy

It is easier to derive the free energy using the replica method. This also give an independent verification of the cavity calculations in the previous section.

In this section, apply the replica method to compute the free energy of model (42). Our aim is to compute asymptotics for the partition function

where we recall that $p_{0}({\rm d}{\bm{\sigma}}_{i})$ is the uniform measure over ${\bm{\sigma}}_{i}\in S^{m-1}$. The $k$-th moment is given by

where we introduced replicas ${\bm{\sigma}}_{i}^{1},\dots,{\bm{\sigma}}_{i}^{k}\in S^{m-1}$, along with the notation $\overline{p}_{0}({\rm d}{\bm{\sigma}})\equiv\prod_{i=1}^{n}\prod_{a=1}^{k}p_{0}({\rm d}{\bm{\sigma}}_{i}^{a})$. Taking the expectation over $Y_{ij}=(\lambda/n)+W_{ij}$, we get

The final formula for the free energy density is obtained by integrating with respect to ${\bm{\sigma}}$ (now the integrand is in product form) and taking the saddle point in ${\bm{Q}}$, ${\bm{\mu}}$, and is reported in the next section, see Eq. (150) below.

3.2 Non-zero temperature (β<∞𝛽\beta<\infty)

The final result of the calculations in the previous section is obtaining the moments

where we used the following identity in its derivation

Replica-symmetric free energy. The replica-symmetric (RS) ansatz is

For computing the third term, we use the following identity. For a fixed arbitrary vector ${\bm{v}}$,

Combining Eqs. (156), (157) and (160) we arrive at

In the complex case, the last line should be interpreted as ${\bm{\xi}}~{}\sim{\sf CN}({\bm{\mu}},{\bm{Q}})$. Differentiating this expression against ${\bm{\mu}},{\bm{C}},{\bm{Q}}$ we recover Eqs. (57) to (59) as saddle point conditions.

3.3 Zero temperature (β→∞→𝛽\beta\to\infty)

As $\beta\to\infty$, the free energy behaves as

where $u({\bm{Q}},{\bm{C}},{\bm{\mu}})$ is the replica-symmetric ground state energy

Let us stress that expectation is with respect to ${\bm{\xi}}$. Denote by ${\bm{\sigma}}_{\rm M}={\bm{\sigma}}_{\rm M}({\bm{\xi}},{\bm{C}})$ the solution of the above maximization problem. It is immediate to see that this is given by

The equations for ${\bm{\mu}}$ and ${\bm{Q}}$ are immediate by taking the $\beta\to\infty$ limit on Eqs. (57), (58). In zero temperature, measure $\nu_{{\bm{\xi}},{\bm{C}}}$ concentrates around ${\bm{\sigma}}_{\rm M}({\bm{\xi}},{\bm{C}})$.

Equivalently, we obtain the above equations by differentiating $u({\bm{Q}},{\bm{C}},{\bm{\mu}})$ with respect to ${\bm{\mu}}$ and ${\bm{C}}$, as follows. We write ${\bm{\sigma}}_{\rm M}={\bm{\sigma}}_{\rm M}({\bm{\xi}},{\bm{C}})$ to lighten the notation. Since $\rho$ is a Lagrange multiplier, we have

where the second equation follows from the constraint $\|{\bm{\sigma}}_{\rm M}\|_{2}=1$.

We next substitute ${\bm{\xi}}={\bm{\mu}}+{\bm{Q}}^{1/2}{\bm{Z}}$. By a similar calculation, we have

Using the ansatz (98), we recover Eqs. (101) to (104). Specifically, Eq (101) follows readily from Eq. (166), restricting to the $(1,1)$ entry and plugging in for ${\bm{\sigma}}_{\rm M}$ from Eq. (100). Also, Eqs. (102) and (103) follow from Eq. (167), restricting to $(1,1)$ and $(2,2)$ entries, respectively. Derivation of Eq. (104) requires more care. Note that since $\nu_{\xi,{\bm{C}}}$, given by (60), is a measure on the unit sphere, the matrix ${\bm{C}}$ is only defined up to a diagonal shift. Let $s_{{\mathfrak{G}}}\eta/2$ denote the slack shift parameter. The ansatz (98) for ${\bm{C}}$ then becomes

We set $\nabla_{{\bm{Q}}^{1/2}}u=0$. Applying Eq. (170), this results in the following two equations for ${\bm{C}}_{11}$ and ${\bm{C}}_{22}$:

Solving for $\eta$ from Eq. (172) and substituting for that in Eq. (171), we obtain Eq. (104).

4 On the maximum likelihood phase transition

It turns out that this is an artifact of the replica symmetric approximation and instead

For a given noise realization $\bm{W}$, the maximum likelihood estimator is

We expect $\lim_{n\to\infty}F_{\bm{W},n}(m)\equiv F(m)$ to exist and to be non-random. This implies that the asymptotic overlap is given by

By symmetry we have $F(m)=F(-m)$. Assuming $m\mapsto F(m)$ to be differentiable, this implies $F^{\prime}(0)=0$. Hence $m=0$ is a local maximum for $\lambda<-F^{\prime\prime}(0)$ and a local minimum for $\lambda>-F^{\prime\prime}(0)$. Since at $\lambda=0$ we obviously have ${\rm Overlap}(\bm{\hat{x}}^{\mbox{\tiny{ML}}})=0$, $F^{\prime\prime}(0)<0$. Further, if $m=0$ is a local minimum, we necessarily have ${\rm Overlap}(\bm{\hat{x}}^{\mbox{\tiny{ML}}})>0$. Hence $\lambda_{c}^{\mbox{\tiny{ML}}}\leq-F^{\prime\prime}(0)$.

On the other hand, we know that we cannot estimate $\bm{x_{0}}$ with non-vanishing overlap for $\lambda<1$. This is a consequence –for instance– of [DAM15, Theorem 4.3] or can, in alternative, be proved directly using the technique of [MRZ14]. This implies that $\lambda_{c}^{\mbox{\tiny{ML}}}\geq 1$. Summarizing, we have

We next claim that earlier work on the Sherrington-Kirkpatrick model implies $F^{\prime\prime}(0)=-1$, thus yielding $\lambda_{c}^{\mbox{\tiny{ML}}}=1$. Indeed, alternative expressions can be obtained by studying the modified problem

where $h$ is an added magnetic field. Then, we have $\lim_{n\to\infty}\widehat{F}_{\bm{W},n}(h)=\widehat{F}(h)$, the Legendre transform of $F$, and we get the alternative upper bound

Note that $\widehat{F}(h)$ is the zero-temperature free energy density of the Sherrington-Kirkpatrick model in a magnetic field $h$ [MPV87], whose $n\to\infty$ limit exists by [GT02]. Using well-known thermodynamic identities, we get

where $\chi(\beta,h)$ is the magnetic susceptibility of the Sherrington-Kirkpatrick model at inverse temperature $\beta$, and magnetic field $h$, and $Q$ is the random overlap.

To the best of our knowledge, the above connection between response to a magneric field, and couplings with non-zero mean was first described by Gérard ToulouseIn [Tou80], this argument was put forward within the context of the so-called Parisi-Toulouse (PaT) scaling hypothesis. Let us emphasize that here we are not assuming PaT to hold (and indeed, it has been convincingly shown that PaT is not correct, albeit an excellent approximation, see e.g. [CRT03]). in [Tou80].

Analysis of PCA estimator for synchronization problem

Here, we study the PCA estimator for the synchronization problem. Recall the observation model

Let ${\bm{v}}_{1}(Y)$ denote the leading eigenvector of $\bm{Y}$. The PCA estimator $\bm{\hat{x}}^{\mbox{\tiny{PCA}}}$ is defined as

with $c^{\mbox{\tiny{PCA}}}$ a certain scaling factor discussed below.

In order to characterize the error of $\bm{\hat{x}}^{\mbox{\tiny{PCA}}}$, we use a simplified version of the main theorem in [CDMF09].

Let $\bm{Y}=\lambda{\bm{v}}_{0}{\bm{v}}_{0}^{*}+\bm{W}$ be a rank-one deformation of the Gaussian symmetric matrix $\bm{W}$, with $W_{ij}\sim{\sf N}(0,1/n)$ independent for $i<j$, and $\|{\bm{v}}_{0}\|=1$. Then, we have, almost surely

Further, letting $\lambda_{1}(\bm{Y})$ be the top eigenvalue of $\bm{Y}$, the following holds true almost surely

Applying this lemma, we compute ${\rm MSE}(\bm{\hat{x}}^{\mbox{\tiny{PCA}}};c)$ as follows

which is optimized for $c=c^{\mbox{\tiny{PCA}}}(\lambda)\equiv\sqrt{\max(1-\lambda^{-2},0)}$. Note that this choice can be written in terms of $\lambda_{1}(\bm{Y})$ as well and so knowledge of $\lambda$ is not required. We then obtain

Analytical results for community detection

In this Section we use the cavity method to analyze the semidefinite programming approach to community detection. We refer, for instance, to [MM09] for general background on the cavity method for sparse graphs. Also, see [BSS87, SW87] for early statistical mechanics work on the related graph bisection problem.

Recall (from the main text) that we are interested in the hidden partition model. Namely, consider a random graph $G_{n}=(V_{n},E_{n})$ over vertex set $V_{n}=[n]$, generated according to the following distribution. We let $\bm{x_{0}}\in\{+1,-1\}^{n}$ be uniformly random: this vector contains the vertex labels (equivalently, it encodes a partition of the vertex set $V=V_{+}\cup V_{-}$, in the obvious way). Conditional on $\bm{x_{0}}$, edges are independent with distribution

As explained in the main text, we tackle this problem via the semidefinite relaxation

For our analysis, we use the non-convex formulation

This is equivalent to the above SDP provided $m\geq n$. Note that, throughout this section, the spin variables ${\bm{\sigma}}_{i}$ are real vectors.

We introduce the following Boltzmann-Gibbs distribution

Here $\overline{p}_{0}({\rm d}{\bm{\sigma}}_{i})$ is the uniform measure over ${\bm{\sigma}}=({\bm{\sigma}}_{1},{\bm{\sigma}}_{2},\dots,{\bm{\sigma}}_{n})$ with ${\bm{\sigma}}_{i}\in S^{m-1}$ and $\sum_{i=1}^{n}{\bm{\sigma}}_{i}={\mathbf{0}}$. In order to extract information about the SDP (191), we take the limits $m\to\infty$, $\beta\to\infty$ after $n\to\infty$.

As $n\to\infty$, the graph $G_{n}$ converges locally to a rooted multi-type Galton-Watson tree with vertices of type $+$ (corresponding to $x_{0,i}=+1$) or $-$ (corresponding to $x_{0,i}=-1$). Each vertex has ${\rm Poisson}(a/2)$ offsprings of the same type, and ${\rm Poisson}(b/2)$ offsprings of the other type (see, e.g. [DM10] for background on local weak convergence in statistical mechanics).

We write the sum-product fixed point equations to compute the marginals at different nodes.

where $\nu_{i\to j}$ are the messages associated to the directed edges of the graph. The marginal $\nu_{0}({\rm d}{\bm{\sigma}}_{0})$, for an arbitrary node , is given by

We rewrite the above equations from another perspective. We designate node as the root of the tree and denote its neighbors by $\{1,2,\dotsc,k\}$. Let $T_{i}$ be the subtree rooted at node $i$ and induced by its descendants. We call $\nu_{i}({\rm d}{\bm{\sigma}}_{i})$ the marginal for ${\bm{\sigma}}_{i}$ w.r.t the graphical model in the subtree $T_{i}$. Replica symmetric cavity equations relate the marginal $\nu_{0}({\rm d}{\bm{\sigma}}_{0})$ to the marginals at the descendant subtrees, i.e., $\nu_{i}({\rm d}{\bm{\sigma}}_{i})$. Note that, in the above notation, $\nu_{i}({\rm d}{\bm{\sigma}}_{i})\equiv\nu_{i\to 0}({\rm d}{\bm{\sigma}}_{i})$ and therefore we obtain

(The measures $\nu_{i}({\rm d}{\bm{\sigma}}_{i})$ are probability measures over $S^{m-1}$ and the right-hand side should be interpreted as a density with respect to the uniform measure on $S^{m-1}$.)

We will use the notation of Eq. (196) but both interpretations are useful.

We will carry out our calculations within a simple ‘vectorial’ ansatz, whereby $\nu_{i}({\rm d}{\bm{\sigma}}_{i})$ depends in a log-linear way on a one-dimensional projection of ${\bm{\sigma}}_{i}$. While this ansatz is not exact, it turns out to yield very accurate results. Also, it can be systematically improved upon, a direction that we leave for future work.

For small $(a-b)$, we expect the solution to the cavity equation to be symmetric (in distribution) under rotations in ${\mathcal{O}}(m)$. By this we mean that, for any rotation $R\in{\mathcal{O}}(m)$, $\nu_{i}^{R}(\,\cdot\,)$ is distributed as $\nu_{i}(\,\cdot\,)$. ($\nu_{i}^{R}(\,\cdot\,)$ is defined as the measure induced by action ${\bm{\sigma}}\mapsto R{\bm{\sigma}}$ on $S^{m-1}$, cf. Section 7).

In the symmetric phase, assuming the ‘vectorial’ ansatz, cf. Remark 9.1, we look for an approximate solution of the form

where ${\bm{z}}_{i}\sim{\sf N}(0,{\rm I}_{m})$, and $O_{m}(1)$ represents a term of order one as $m\to\infty$.

Using the Fourier representation of the $\delta$ function (with associated parameter $\rho$), and performing the Gaussian integral over ${\bm{\sigma}}$, we get

Here the indegral over $\rho$ runs along the imaginary axis in the complex plane, from $-i\infty$ and $+i\infty$.

Note, for ${\bm{\sigma}}_{0}$ uniformly random on the unit sphere, the term $(2\beta m/\rho)\langle{\bm{z}}_{i},{\bm{\sigma}}_{0}\rangle$ is of order $\sqrt{m}$, i.e. of lower order with respect to the term including $S(\,\cdot\,)$. Also, the term $(\beta m{\sf c}_{i}/\rho)(\|{\bm{z}}_{i}\|_{2}^{2}-1)$ is of order $\sqrt{m}$ and does not depend on ${\bm{\sigma}}_{0}$. Hence, up to an additional $O_{m}(1)$ term, we can reabsorb this in the normalization constant. We therefore get

We next perform integration over $\rho$ by the saddle point method. Since $\langle{\bm{z}}_{i},{\bm{\sigma}}_{0}\rangle=O(m^{-1/2})$ and $S_{i}(\rho)=O(1)$, the saddle point is given by the stationary equation $S_{i}^{\prime}(\rho)=0$. The saddle point $\rho_{i,*}$ lies on the real axis and is a minimum along the real axis but a maximum with respect to the imaginary direction, i.e.,

By Cauchy’s theorem, we can deform the contour of integral to pass the saddle point along the imaginary direction. This in fact corresponds to the path that descents most steeply from the saddle point. The integral is dominated by $\rho=\rho_{i,*}+O(m^{-1/2})$ and hence,

While this expression for $\widehat{\nu}_{i}({\bm{\sigma}}_{0})$ is accurate when $\langle{\bm{z}}_{i},{\bm{\sigma}}_{0}\rangle$ is small, it breaks down for large $\langle{\bm{z}}_{i},{\bm{\sigma}}_{0}\rangle$. In Section 9.5 we will discuss the regimes of validity of this approximation. Namely, we expect it to be accurate for $d$ large and for $d$ close to one.

Substituting in Eq. (196), we get the recursion

In particular, as $\beta\to\infty$, we get the simple equation

Note that ${\sf c}_{0},{\sf c}_{1},\dots,{\sf c}_{k}$ are random variables, because of the randomness in the underlying limiting tree, which is Galton-Watson tree with Poisson offspring distribution. We get

${\sf c}_{*}\preceq L$, $L\sim{\rm Poisson}(d)$.

For $d\leq 1$, ${\sf c}_{*}={\sf c}_{0}=0$ identically. Hence the distributional equation (210) has a unique solution.

For $d>1$, ${\sf c}_{*}>0$ with positive probability and further equation (210) admits no other solution than ${\sf c}_{0}$, ${\sf c}_{*}$.

Let ${\mathfrak{P}}$ denote the space of probability measures over $[0,\infty]$, and ${\sf T}_{d}:{\mathfrak{P}}\to{\mathfrak{P}}$ the map defined by the right-hand side of Eq. (210). Namely ${\sf T}_{d}(\mu)$ is the probability distribution of the right-hand side of Eq. (210) when ${\sf c}_{i}\sim_{i.i.d.}\mu$. Notice that this is well defined on the extended real line because the summands are non-negative. It is immediate to see that this map is monotone, i.e.

For point 3, note that by Jensen inequality

Point 4 is just Theorem 4.1 in [LPP97]. ∎

The next proposition establishes an appealing interpretation of the random variable ${\sf c}_{*}$. Again, this puts together results of [Lyo90] and [LPP97]. We give here a proof of this connection for the readers’ convenience. We refer to [LP13] for further background on discrete potential theory (electrical networks) and trees.

In particular, if $d>1$, then ${\sf c}_{*}>0$ with positive probability.

Now since the conductance of several resistances in parallel is equal to the sum of the conductances of the components, we get

It follows from Theorem [Lyo90, Theorem 4.3] and [Lyo90, Proposition 6.4] that ${\sf c}_{*}>0$ with positive probability whenever $d>1$. ∎

We will hereafter consider the case $d>1$ and focus on the maximal solution ${\sf c}_{*}$.

where $Z_{1}\sim{\sf N}(0,1)$ is independent of $L\sim{\rm Poisson}(d)$. Note that we used central limit theorem and law of large numbers in obtaining (217).

On the other hand, taking the variance, we obtain

Using equation (221) in equation (219), we get

2 Linear stability of the symmetric phase and critical point

We next study the stability of the symmetric solution (198). We break the ${\mathcal{O}}(m)$ symmetry by letting

where ${\bm{\sigma}}_{i}=(s_{i},{\bm{\tau}}_{i})$ and ${\bm{z}}_{i}\sim{\sf N}(0,{\rm I}_{m-1})$ is $(m-1)$-dimensional. Note that each coordinate of ${\bm{z}}_{i}$ is of order $1$, and is multiplied by a factor $\sqrt{m}$ in the above expression. We will consider $h_{i}\lll 1$, and expand all expressions to linear order in $h_{i}$.