Tightness of the maximum likelihood semidefinite relaxation for angular synchronization

Introduction

Recovery problems in statistics and many other fields are commonly solved under the paradigm of maximum likelihood estimation, partly due to the rich theory it enjoys. Unfortunately, in many important applications, the parameter space is exponentially large and non-convex, often rendering the computation of the maximum likelihood estimator (MLE) intractable. It is then common to settle for heuristics, such as expectation-maximization algorithms to name but one example. However, it is also common for such iterative heuristics to get trapped in local optima. Furthermore, even when these methods do attain a global optimum, there is in general no way to verify this.

A now classic alternative to these heuristics is the use of convex relaxations. The idea is to maximize the likelihood in a larger, convex set that contains the parameter space of interest, as (well-behaved) convex optimization problems are generally well understood and can be solved in polynomial time. The downside is that the solution obtained might not be in the original feasible (acceptable) set. One is then forced to take an extra, potentially suboptimal, rounding step.

This line of thought is the basis for a wealth of modern approximation algorithms . One preeminent example is Goemans and Williamson’s treatment of Max-Cut , an NP-hard combinatorial problem that involves segmenting a graph in two clusters to maximize the number of edges connecting the two clusters. They first show that Max-Cut can be formulated as a semidefinite program (SDP)—a convex optimization problem where the variable is a positive semidefinite matrix—with the additional, non-convex constraint that the sought matrix be of rank one. Then, they propose to solve this SDP while relaxing (removing) the rank constraint. They show that the obtained solution, despite typically being of rank strictly larger than one, can be rounded to a (suboptimal) rank-one solution, and that it provides a guaranteed approximation of the optimal value of the hard problem. Results of the same nature abound in the recent theoretical computer science literature .

In essence, approximation algorithms insist on solving all instances of a given NP-hard problem in polynomial time, which, unless P = NP, must come at the price of accepting some degree of sub-optimality. This worst-case approach hinges on the fact that a problem is NP-hard as soon as every efficient algorithm for it can be hindered by at least one pathological instance.

Alternatively, in a non-adversarial setting where “the data is not an enemy,” one may find that such pathological cases are not prominent. As a result, the applied mathematics community has been more interested in identifying regimes for which the convex relaxations are tight, that is, admit a solution that is also admissible for the hard problem. When this is the case, no rounding is necessary and a truly optimal solution is found in reasonable time, together with a certificate of optimality. This is sometimes achieved by positing a probability distribution on the instances of the problem and asserting tightness with high probability, as for example in compressed sensing , matrix completion , clustering and inverse problems . In this approach, one surrenders the hope to solve all instances of the hard problem, in exchange for true optimality with high probability.

The main contribution of the present paper is a proof that, even though the angular synchronization problem is NP-hard , its MLE in the face of Gaussian noise can often be computed (and certified) in polynomial time. This remains true even for entry-wise noise levels growing to infinity as the size of the problem (the number of phases) grows to infinity. The MLE is obtained as the solution of a semidefinite relaxation described in Section 2. This arguably striking phenomenon has been observed empirically before (see also Figure 2), but not explained.

Computing the MLE for angular synchronization is equivalent to solving a non-bipartite Grothendieck problem. Semidefinite relaxations for Grothendieck problems have been thoroughly studied in theoretical computer science from the point of view of approximation ratios. The name is inspired by its close relation to an inequality of Grothendieck . We direct readers to the survey by Pisier for a discussion.

The proposed result is qualitatively different from most tightness results available in the literature. Typical results establish either exact recovery of a planted signal (mostly in discrete settings), or exact recovery in the absence of noise, joint with stable (but not necessarily optimal) recovery when noise is present . In contrast, this paper shows optimal recovery even though exact recovery is not possible. In particular, Demanet and Jugnon showed stable recovery for angular synchronization via semidefinite programming, under adversarial noise . We complement this by showing tightness in a non-adversarial setting, meaning the actual MLE is computed.

A similar semidefinite relaxation was studied in a digital communications context, where the parameters to estimate are $m$th roots of unity . There, non-asymptotic results show the relaxation approximates the MLE within some factor, with high probability. The present paper is related to the limit $m\to\infty$, although the noise model considered is different, and we focus on exact MLE computation.

Our proof relies on verifying that a certain candidate dual certificate is valid with high probability. The main difficulty comes from the fact that the dual certificate depends on the MLE, which does not coincide with the planted signal, and is a nontrivial function of the noise. We use necessary optimality conditions of the hard problem to both obtain an explicit expression for the candidate dual certificate, and to partly characterize the point whose optimality we aim to establish. This seems to be required since the MLE is not known in closed form.

In the context of sparse recovery, a result with similar flavor is support recovery guarantee , where the support of the estimated signal is shown to be contained in the support of the original signal. Due to the noise, exact recovery is also impossible in this setting. Another example is a recovery guarantee in the context of latent variable selection in graphical models .

Besides the relevance of angular synchronization in and of its own, we are confident this new insight will help uncover similar results in other applications where it has been observed that semidefinite relaxations can be tight even when the ground truth cannot be recovered. Notably, this appears to be the case for the Procrustes and multi-reference alignment problems ).

The crux of our argument concerns the rank of the solutions of an SDP. We mention in passing that there are many other deterministic results in the literature pertaining to the rank of solutions of SDP’s. For example, it has been shown that, in general, an SDP with only equality constraints admits a solution of rank at most (on the order of) the square root of the number of constraints, see . Furthermore, Sagnol shows that under some conditions (that are not fulfilled in our case), certain SDP’s related to packing problems always admit a rank-one solution. Sojoudi and Lavaei study a class of SDP’s on graphs which is related to ours and for which, under certain strong conditions on the topology of the graphs, the SDP’s admit rank-one solutions—see also applications to power flow optimization .

2 Notation

The Angular Synchronization problem

Further letting the noise $\varepsilon_{ij}$ be i.i.d. (complex) Gaussian variables for $i<j$, it follows that an MLE for $z$ is any vector of phases $x$ minimizing $\sum_{i,j}|C_{ij}x_{j}-x_{i}|^{2}$. Equivalently, an MLE is a solution of the following quadratically constrained quadratic program (sometimes called the complex constant-modulus QP [41, Table 2] in the optimization literature, and non-bipartite Grothendieck problem in theoretical computer science):

where $x^{*}$ denotes the conjugate transpose of $x$. This problem can only be solved up to a global phase, since only relative information is available. Indeed, given any solution $x$, all vectors of the form $xe^{i\theta}$ are equivalent solutions, for arbitrary phase $\theta$.

Such relaxations lift the problem to higher dimensional spaces. Indeed, the search space of (QP) has dimension $n$ (or $n-1$, discounting the global phase) whereas the search space of (SDP) has real dimension $n(n-1)$. In general, increasing the dimension of an optimization problem may not be advisable. But in this case, the relaxed problem is a semidefinite program. Such optimization problems can be solved to global optimality up to arbitrary precision in polynomial time .

It is known that the solution of (SDP) can be rounded to an approximate solution of (QP), with a guaranteed approximation ratio [54, § 4]. But even better, when (SDP) admits an optimal solution $X$ of rank one, then no rounding is necessary: the leading eigenvector $x$ of $X=xx^{*}$ is a global optimum of (QP), meaning we have solved the original problem exactly. Elucidating when the semidefinite program admits a solution of rank one, i.e., when the relaxation is tight, is the focus of the present paper.

Problem (QP) is posed over the complex numbers. As a result, the individual variables $x_{i}$ in (QP) live on a continuous search space (the unit circle). One effect of this is that even small noise on the data precludes exact recovery of the signal $z$ (in general). This is the root of most of the complications that will arise in the developments hereafter. In order to first illustrate some of the ideas of the proof in a simpler context, this section proposes to take a detour through the real case. Besides this expository rationale, the real case is interesting in and of itself. It notably relates to correlation clustering and the stochastic block model . The analysis proposed here also appears in .

Let $z\in\{\pm 1\}^{n}$ be the signal to estimate and let $C=zz^{\!\top}+\sigma W$ contain the measurements, with $W=W^{\!\top}$ a Wigner matrix: its above-diagonal entries are i.i.d. (real) standard normal random variables, and its diagonal entries are zero. Each entry $C_{ij}$ is a noisy measurement of the relative sign $z_{i}z_{j}$. For example, $z_{i}$ could represent political preference of an agent (left or right wing) and $C_{ij}$ could be a measurement of agreement between two agents’ views . Consider this MLE problem:

Thus, $x_{i}\in\{\pm 1\}$ for each $i$. The corresponding relaxation reads:

Strong duality holds, which implies that a given feasible $X$ is optimal if and only if there exists a dual feasible matrix $S$ such that $\operatorname{Tr}\left(CX\right)=\operatorname{Tr}\left(S+C\right)$, or, in other words, such that $\operatorname{Tr}\left(SX\right)=0$.Indeed, $S+C$ is diagonal and $X_{ii}=1$, hence $\operatorname{Tr}\left(S+C\right)=\operatorname{Tr}\left((S+C)X\right)=\operatorname{Tr}\left(SX\right)+\operatorname{Tr}\left(CX\right)$. Since both $S$ and $X$ are positive semidefinite, this is equivalent to requiring $SX=0$ (a condition known as complementary slackness), and hence requiring $Sz=0$.

For ease of exposition, we now assume (without loss of generality) that $z=\mathds{1}$. Tentatively, let $S=nI+\sigma\operatorname{diag}(W\mathds{1})-C$—for the complex case, we will see how to obtain this candidate without guessing. Then, by construction, $S+C$ is diagonal and $S\mathds{1}=0$.Using $C=\mathds{1}\mathds{1}^{\!\top}+\sigma W$, we get $S\mathds{1}=n\mathds{1}+\sigma W\mathds{1}-n\mathds{1}-\sigma W\mathds{1}=0$. It remains to determine under what conditions $S$ is positive semidefinite.

Define the diagonal matrix $D_{W}=\operatorname{diag}(W\mathds{1})$ and the (Laplacian-like) matrix $L_{W}=D_{W}-W$. The candidate dual certificate is a sum of two Laplacian-like matrices:

This is indeed compatible with the empirical observation of Figure 1.

2 Back to synchronization over SO(2)

We now return to the complex case, which is the focus of this paper. As was mentioned earlier, in the presence of even the slightest noise, one can no longer reasonably expect the true signal $z$ to be an optimal solution of (QP) (this can be further quantified using Cramér-Rao bounds ). Nevertheless, we set out to show that (under some assumptions on the noise) solutions of (QP) are close to $z$ and they can be computed via (SDP).

The proof follows that of the real case in spirit, but requires more sophisticated arguments because the solution is no longer known explicitly. This is important because the candidate dual certificate $S$ itself depends on that solution. With this in mind, the proof of the upcoming main lemma (Lemma 3.2) follows this reasoning:

For small enough noise levels $\sigma$, any optimal solution $x$ of (QP) is close to the sought signal $z$ (Lemmas 4.1 and 4.2).

Solutions $x$, a fortiori, satisfy necessary optimality conditions for (QP). First-order conditions take up the form $Sx=0$, where $S=\Re\{\operatorname{ddiag}(Cxx^{*})\}-C$ depends smoothly on $x$ (see (4.9)). Second-order conditions will also be used.

Remarkably, this $S$ can be used as a dual certificate for solutions of (SDP). Indeed, $X=xx^{*}$ is optimal if and only if $S$ is positive semidefinite (Lemma 4.4). The solution is unique if $\operatorname{rank}(S)=n-1$ (Lemma 4.3). Thus, it only remains to study the eigenvalues of $S$.

In the absence of noise, $S$ is a Laplacian for a complete graph with unit weights (up to a unitary transformation), so that its eigenvalues are with multiplicity $1$, and $n$ with multiplicity $n-1$. Then, $X=zz^{*}$ is always the unique solution.

Adding small noise, because of the first point, the solution $x$ will move only by a small amount, and hence so will $S$. Thus, the large eigenvalues should be controllable into remaining positive (Section 4.4).

The crucial fact follows: because of the way $S$ is constructed (using first-order optimality conditions), the zero eigenvalue is “pinned down” (as long as $x$ is a local optimum of (QP)). Indeed, both $x$ and $S$ change as a result of adding noise, but the property $Sx=0$ remains valid. Thus, there is no risk that the zero eigenvalue from the noiseless scenario would become negative when noise is added.

Following this road map, most of the work in the proof below consists in bounding how far away $x$ can be from $z$, and in using that to control the large eigenvalues of $S$. This constructive way of identifying the dual certificate (third point in the roadmap) already appears explicitly in work by Journée et al. , who considered a different family of real, semidefinite programs which also admit a smooth geometry when the rank is constrained. This points to smoothness of (QP) (and non-degeneracy of (SDP) ) as a principal ingredient in our analysis: the KKT conditions of (QP) are a subset of the KKT conditions of its relaxation. It is because the former are explicit (rather than existential as in Lemma 4.3) that they help in identifying $S$.

Our main theorem follows. In a nutshell, it guarantees that: under (complex) Wigner noise $W$, with high probability, solutions of (QP) are close to $z$, and, assuming the noise level $\sigma$ is smaller than (on the order of) $n^{1/4}$, (SDP) admits a unique solution, it is of rank one and identifies the solution of (QP) (unique, up to a global phase shift).

then the semidefinite program (SDP), given by

has, as its unique solution, the rank-one matrix $X=xx^{\ast}$.

The numerical experiments (Figure 2) suggest it should be possible to allow $\sigma$ to grow at a rate of $\frac{n^{1/2}}{\operatorname{polylog}(n)}$ (as in the real case), but we were not able to establish that (see Remark 4.6). Nevertheless, we do show that $\sigma$ can grow unbounded with $n$. To the best of our knowledge, this is the first result of this kind. We hope it might inspire similar results in other problems where the same phenomenon has been observed .

Main result

In this section we present our main technical result and show how it can be used to prove Theorem 2.1. We begin with a central definition in this paper. Intuitively, this definition characterizes non-adversarial noise matrices $W$.A similar but different definition appeared in a previous version of this paper.

The next lemma is the main technical contribution of this paper. It is a deterministic, non-asymptotic statement.

Furthermore, if $\sigma\leq\frac{1}{18}n^{1/4}$, then the semidefinite program (SDP) has, as its unique solution, the rank-one matrix $X=xx^{\ast}$.

We defer the proof of Lemma 3.2 to Section 4. The following proposition, whose proof we defer to Appendix A, shows how this lemma can be used to prove Theorem 2.1.

The latter result is not surprising. Indeed, the definition of $z$-discordance requires two elements. Namely, (i) that $W$ be not too large as an operator, and (ii) that no row of $W$ be too aligned with $z$. For $W$ a Wigner matrix independent of $z$, those are indeed expected to hold. In fact, for Gaussian noise, the constants 3 can be replaced by $2+\varepsilon$ for any $\varepsilon>0$, provided $n$ is large enough.

The definition of $z$-discordance is not tightly adjusted to Wigner noise. As a result, it is expected that Lemma 3.2 will be applicable to show tightness of semidefinite relaxations for a larger span of noise models.

The proof

In this section, we prove Lemma 3.2. See Section 2.2 for an outline of the proof.

Without loss of generality, assume the global phase of $x$ is such that $z^{*}x=|z^{*}x|$, i.e., $x$ and $z$ are optimally aligned. Expand the inequality $z^{*}Cz\leq x^{*}Cx$ using the data model $C=zz^{*}+\sigma W$ to obtain

Since $n^{2}-|z^{*}x|^{2}=(n-|z^{*}x|)(n+|z^{*}x|)$, divide both sides by $n+|z^{*}x|\geq n$ to obtain

Combine this and (4.1) with (4.2) to obtain $\|x-z\|_{2}\leq 12\sigma$. ∎

Note that the constant 12 is pessimistic, because we used $n+|z^{*}x|\geq n$ even though it is closer to $2n$. Assuming $\|x-z\|_{2}\leq\alpha\sigma$ and $\sigma\leq t\sqrt{n}$, the argument above can be bootstrapped to reduce the constant. One obtains $\|x-z\|_{2}\leq\alpha_{k}\sigma$ for all $k$, with $\alpha_{0}=12$ and $\alpha_{k+1}=6+(t/2)^{2}\alpha_{k}^{3}$. For $t<1/6\sqrt{2}$ small enough, $\alpha_{k}$ converges arbitrarily close to 6. For example, if $\sigma\leq\sqrt{n}/12$, then $\|x-z\|_{2}\leq 6.5\sigma$.

The next lemma establishes a bound on the largest individual error, $\|x-z\|_{\infty}$, after proper global phase alignment of $x$ and $z$. Interestingly, for $\sigma\ll n^{1/4}$, the bound shows that individual errors decay, uniformly, as $n$ increases.

and combine with the assumption $z^{*}x=|z^{*}x|$ to obtain

Invoke Lemma 4.1, namely, $|z^{*}x|\geq n-72\sigma^{2}$, to get

Since $\|x-z\|_{\infty}\leq 2$, it finally comes that

We discuss the problem of bounding $\|Wx\|_{\infty}$ in more details later on. For now, we simply use the suboptimal bound (4.11) (obtained independently of the present lemma), i.e., $\|Wx\|_{\infty}\leq 3\sqrt{n\log n}+36\sigma\sqrt{n}$. Then, for all $n\geq 2$, using $24/\sqrt{2}\leq 17$,

(For $\sigma\ll n^{1/2}$, the constant $29$ could be replaced by one arbitrarily close to $12$.) ∎

2 Optimality conditions for (SDP)

The global optimizers of the semidefinite program (SDP) can be characterized completely via the Karush-Kuhn-Tucker (KKT) conditions.

If, furthermore, $\operatorname{rank}(\hat{S})=n-1$, then $X$ has rank one and is the unique global optimizer of (SDP).

Certainly, if (SDP) admits a rank-one solution, it has to be of the form $X=xx^{*}$, with $x$ an optimal solution of the original problem (QP). Based on this consideration, our proof of Lemma 3.2 goes as follows. We let $x$ denote a global optimizer of (QP) and we consider $X=xx^{*}$ as a candidate solution for (SDP). Using the optimality of $x$ and assumptions on the noise, we then construct and verify a dual certificate matrix $\hat{S}$ as required per Lemma 4.3. In such proofs, one of the nontrivial parts is to guess an analytical form for $\hat{S}$ given a candidate solution $X$. We achieve this by inspecting the first-order optimality conditions of (QP) (which $x$ necessarily satisfies). The main difficulty is then to show the suitability of the candidate $S$, as it depends nonlinearly on the global optimum $x$, which itself is a complicated function of the noise $W$. We show feasibility of $S$ via a program of inequalities, relying on $z$-discordance of the noise $W$ (see Definition 3.1).

3 Construction of the dual certificate S𝑆S

Every global optimizer of the combinatorial problem (QP) must, a fortiori, satisfy first-order necessary optimality conditions. We derive those now.

over the smooth Riemannian manifold $\mathcal{S}^{n}$. Therefore, the first-order necessary optimality conditions for (QP) (i.e., the KKT conditions) can be stated simply as $\operatorname{grad}g(x)=0$, where $\operatorname{grad}g(x)$ is the Riemannian gradient of $g$ at $x\in\mathcal{S}^{n}$ . This gradient is given by the orthogonal projection of the Euclidean (the classical) gradient of $g$ onto the tangent space of $\mathcal{S}^{n}$ at $x$ [3, eq. (3.37)],

The projector and the Euclidean gradient are given respectively by:

Note that $S$ is Hermitian and $Sx=0$. Referring to the KKT conditions in Lemma 4.3, it follows immediately that $X$ is feasible for (SDP) (conditions 1 and 2); that $SX=(Sx)x^{*}=0$ (condition 3); and that $S+C$ is a diagonal matrix (condition 4). It thus only remains to show that $S$ is also positive semidefinite and has rank $n-1$. If such is the case, then $X$ is the unique global optimizer of (SDP). Note the special role of the first-order necessary optimality conditions: they guarantee complementary slackness, without requiring further work.

We will also use second-order necessary optimality conditions, namely, that the (Riemannian) Hessian of $g$ at an optimizer $x$ is positive semidefinite on the tangent space (4.7). The action of the Riemannian Hessian is obtained by projecting the directional derivatives of the Riemannian gradient [3, eq. (5.15)]. Explicitly, for any tangent vector $\dot{x}\in T_{x}\mathcal{S}^{n}$, one can compute that (with $\operatorname{D}\!h(x)[\dot{x}]$ denoting the directional derivative of $h$ at $x$ along $\dot{x}$)

Thus, if $x$ is a (local) optimizer, then, since $\operatorname{Proj}_{x}$ is self-adjoint,

for all $\dot{x}\in T_{x}\mathcal{S}^{n}$: a necessary but insufficient step towards making $S$ positive semidefinite. We will later use this condition along selected directions.

The following lemma further shows that $S$ is the right candidate dual certificate. More precisely, for $x$ a critical point of (QP), it is necessary and sufficient for $S$ to be positive semidefinite in order for $X=xx^{*}$ to be optimal for (SDP). This confirms that, by studying $S$, nothing is lost with respect to the original question. See also .

A feasible $X$ (of any rank) for (SDP) is optimal if and only if $S=\Re\{\operatorname{ddiag}(CX)\}-C$ (4.9) is positive semidefinite. There exists no other certificate.

The if part follows from Lemma 4.3: set $\hat{S}=S$ and observe that, since $\operatorname{Tr}\left(SX\right)=0$ by construction, and since $S,X\succeq 0$, it follows that $SX=0$. We now show the only if part. Assume $X$ is optimal. Then, by Lemma 4.3, there exists $\hat{S}\succeq 0$ which satisfies $\hat{S}X=0$ and $\hat{S}+C=\hat{D}$, where $\hat{D}$ is diagonal. Thus, $CX=(\hat{D}-\hat{S})X=\hat{D}X$ and $\Re\{\operatorname{ddiag}(CX)\}=\hat{D}$. Consequently, $S=\hat{D}-C=\hat{S}$. ∎

4 A sufficient condition for rank recovery

Knowing which certificate $S$ (4.9) to verify for a given $x$, it remains to characterize the point $x$. Of course, $x$ is the global optimizer of (QP), but this is not a convenient property to exploit. Instead, we let $x$ be a second-order critical pointA second-order critical point satisfies first- and second-order necessary optimality conditions, namely, the gradient is zero and the Hessian is positive semidefinite (if minimizing) [26, §3.2.1]. for (QP) which outperforms the planted signal $z$ (certainly, the MLE is one such point). In effect, we prove the following, which immediately yields Lemma 3.2.

To this end, we prove that, at such points $x$, the certificate $S$ is positive semidefinite of rank $n-1$. As a first observation, note that $x$ being critical ($Sx=0$) implies that $\Re\{(Cx)_{i}\bar{x}_{i}\}x_{i}=(Cx)_{i}$ for all $i$. Thus, $(Cx)_{i}\bar{x}_{i}$ is real, and it follows that

Furthermore, since $x$ is second-order critical, the Hessian of $g$ at $x$ is positive semidefinite, implying $\left\langle\dot{x},S\dot{x}\right\rangle\geq 0$ for all $\dot{x}\in T_{x}\mathcal{S}^{n}$ (4.7). In particular, for all $i$, $\dot{x}=(jx_{i})e_{i}$ is a tangent vector at $x$ (where $j=\sqrt{-1}$ and $e_{i}$ is the $i$th canonical basis vector), and it follows that

Since $C_{ii}=1$ by construction,As before, $S$ is independent of $\operatorname{diag}(C)$. Assuming $C_{ii}=1$ involves no loss of generality. it follows in particular that $(Cx)_{i}\bar{x}_{i}$ is real and positive. Thus:

As a result, a sufficient condition for $S$ to be positive semidefinite with rank $n-1$ is to have

Combining with (4.10) yields the following sufficient condition:

This condition involves only $\sigma$ and $n$, and as such is the best result we prove. The bottleneck is the term in $\sigma^{2}$, which leads to a bound of the type $\sigma\leq c\cdot n^{1/4}$. Further inspection of (4.12) shows $\sigma\leq\frac{1}{18}n^{1/4}$ is indeed a sufficient condition, for $n\geq 2$. This concludes the proof of Lemma 3.2.

One avenue to improve the current bound might be to expand $x=x(\sigma W)$ around 0, to first order. Some computations (omitted here) show that such a development would lead to $x=z+\frac{\sigma}{n}\Im\left\{\operatorname{ddiag}(Wzz^{*})\right\}(iz)+\epsilon$. Then,

Conclusions

Appendix A Wigner matrices are discordant

A matrix $W$ is $z$-discordant if and only if $\operatorname{diag}(z)^{*}W\operatorname{diag}(z)$ is $\mathds{1}$-discordant. Since $\operatorname{diag}(z)^{*}W\operatorname{diag}(z)$ has the same distribution as $W$ (owing to complex normal random variables having uniformly random phase), we may without loss of generality assume $z=\mathds{1}$ in the remainder of the proof.

Although tail bounds for the real version of this are well-known (see for example ) and they mostly hold verbatim in the complex case, for the sake of completeness we include a classical argument, based on Slepian’s comparison theorem and Gaussian concentration, for a tail bound in the complex valued case.

This means that we can use Slepian’s comparison theorem (see for example [39, Cor. 3.12]) to get

$\Pr\left\{\|W\mathds{1}\|_{\infty}>3\sqrt{n\log n}\right\}\leq 2n^{-5/4}$.

The random vector given by $\frac{1}{(n-1)^{1/2}}W\mathds{1}$ is jointly Gaussian where the marginal of each entry is a standard complex Gaussian. By a suboptimal union bound argument, the maximum absolute value among $k$ standard complex Gaussian random variables (not necessarily independent) is larger than $t$ with probability at most $2ke^{-t^{2}/4}$. Hence,

To support the discussion following Proposition 3.3, we further argue that

It is easy to see that $\mathds{1}^{*}W\mathds{1}$ is a real Gaussian random variable with zero mean and variance $2\frac{n(n-1)}{2}=n(n-1)$. This implies that:

Acknowledgments

A. S. Bandeira was supported by AFOSR Grant No. FA9550-12-1-0317. Most of this work was done while he was with the Program for Applied and Computational Mathematics at Princeton University. N. Boumal was supported by a Belgian F.R.S.-FNRS fellowship while working at the Université catholique de Louvain (Belgium), by a Research in Paris fellowship at Inria and ENS, the “Fonds Spéciaux de Recherche” (FSR UCLouvain), the Chaire Havas “Chaire Economie et gestion des nouvelles données” and the ERC Starting Grant SIPA. A. Singer was partially supported by Award Number R01GM090200 from the NIGMS, by Award Numbers FA9550-12-1-0317 and FA9550-13-1-0076 from AFOSR, by Award Number LTR DTD 06-05-2012 from the Simons Foundation, and by the Moore Foundation.

References