Source-linked AI summary
Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Afonso S. Bandeira, Nicolas Boumal, Amit Singer
TL;DR
Angular synchronization has an intractable maximum-likelihood estimator, motivating convex relaxations whose tightness is difficult to prove when the MLE differs from the planted signal. The paper develops a dual-certificate proof and shows that the semidefinite relaxation recovers and certifies the MLE with high probability under Gaussian noise, even when noise grows unboundedly with problem size.
Problem
Maximum-likelihood estimation can be computationally intractable, while tightness proofs for convex relaxations usually rely on an explicitly known planted solution.
Method
The paper analyzes complete-graph angular synchronization and constructs a dual certificate using optimality conditions, despite the certificate depending on the unknown MLE rather than the planted signal.
Results
The semidefinite relaxation uniquely recovers the MLE's rank-one solution under suitable conditions, with high probability for Gaussian noise.
Takeaways & Limitations
Angular synchronization's NP-hard MLE can often be computed and certified in polynomial time through the semidefinite relaxation, even at unbounded noise levels.
Takeaways & Limitations
The analysis does not establish the numerically suggested tightness regime σ ≤ n^1/2 polylog(n), although it proves that σ may grow unboundedly with n.
Abstract
from arXiv · showhide
Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we study an estimation problem (angular synchronization) for which the MLE is not a simple function of the planted solution, yet for which the convex relaxation is tight. To establish tightness in this context, the proof is less direct because the point at which to verify optimality conditions is not known explicitly. Angular synchronization consists in estimating a collection of $n$ phases, given noisy measurements of the pairwise relative phases. The MLE for angular synchronization is the solution of a (hard) non-bipartite Grothendieck problem over the complex numbers. We consider a stochastic model for the data: a planted signal (that is, a ground truth set of phases) is corrupted with non-adversarial random noise. Even though the MLE does not coincide with the planted signal, we show that the classical semidefinite relaxation for it is tight, with high probability. This holds even for high levels of noise.
1 Introduction
The paper studies when convex relaxations can recover the exact MLE for angular synchronization despite computational hardness and noisy, non-adversarial data. It proves tightness through a dual-certificate argument whose target depends on the unknown MLE rather than directly on the planted signal.
- Motivation: Convex relaxations replace hard likelihood optimization with tractable optimization, but may require a potentially suboptimal rounding step.The relaxation enlarges the feasible set and can produce solutions outside the original parameter space.
- Motivation: In non-adversarial random settings, tightness can yield an optimal solution and a certificate of optimality with high probability.This trades guarantees for every instance for true optimality on typical instances.
- Problem: Angular synchronization estimates n phases from noisy pairwise relative-phase measurements and has applications in networks, phaseless reconstruction, ranking, communications, and computer vision.The paper analyzes the complete-graph setting with measurements available for every pair.
- Contribution: The paper proves that the angular-synchronization MLE can often be computed and certified in polynomial time through a semidefinite relaxation, even with noise levels growing unboundedly with n.The result concerns Gaussian noise and addresses an NP-hard estimation problem.
- Contribution: Unlike typical tightness results based on exact planted-signal recovery, this work establishes exact MLE computation when exact recovery of the planted signal is impossible.The result complements prior stable recovery under adversarial noise by treating a non-adversarial setting.
- Proof strategy: The proof constructs a dual certificate from necessary optimality conditions because the certificate depends on the MLE, which is not known in closed form.The hard problem's optimality conditions both provide the certificate expression and partially characterize the unknown target.
2 The Angular Synchronization problem
Angular synchronization estimates unit-modulus phases from noisy pairwise differences by solving a nonconvex MLE and its semidefinite relaxation. The paper shows that, despite noise preventing exact recovery of the planted complex signal, the relaxation can remain tight and recover the MLE with high probability.
- Problem: Angular synchronization estimates n unit-modulus complex phases from noisy measurements of every pairwise phase difference.The measurements have the form C_ij = z_i z_j^* + ε_ij.
- Maximum likelihood estimation: The MLE is the nonconvex constant-modulus QP max x^*Cx subject to |x_i| = 1, also called the complex non-bipartite Grothendieck problem.The solution is identifiable only up to a global phase.
- Semidefinite relaxation: The SDP relaxation drops the rank-one constraint and maximizes Tr(CX) subject to diag(X) = 1 and X ⪰ 0.This lifted problem is solvable to global optimality in polynomial time, up to arbitrary precision.
- Tightness: When the SDP has a rank-one optimum, its leading eigenvector is a global optimizer of the original QP, so no rounding is needed.The paper studies precisely when this relaxation is tight.
- Complex case: In the complex setting, even slight noise generally prevents exact recovery of the planted signal, but the MLE remains close to it and can be computed through the SDP.The main theorem establishes a unique rank-one SDP solution with high probability when the noise is on the order of n^1/4 or smaller.
- Proof strategy: The proof constructs a dual certificate from first-order optimality conditions at the unknown MLE, preserving a pinned zero eigenvalue while controlling the remaining eigenvalues.This avoids requiring an explicit closed form for the MLE.
3 Main result
The paper introduces z-discordance to characterize non-adversarial noise, then uses a deterministic lemma to establish tightness of the semidefinite relaxation. For Gaussian noise, the required discordance holds with high probability, yielding a unique rank-one SDP solution under the stated noise bound.
- z-discordance is introduced as a characterization of non-adversarial noise matrices.
- The main technical lemma is deterministic and non-asymptotic.
- For a global optimizer x of the quadratic program, the lemma shows that x is close to the planted vector z.
- If σ ≤ 1/18n^1/4, the semidefinite program has the unique rank-one solution X = xx∗.
- For Gaussian Hermitian noise, z-discordance holds with probability at least 1 − 2n^−5/4 − e^−n/2.
- Because the z-discordance definition is not tightly tailored to Wigner noise, the technical lemma may apply to a broader range of noise models.
4 The proof
The proof characterizes the MLE through second-order optimality conditions, constructs the corresponding dual certificate, and verifies its positive semidefiniteness under noise conditions. This establishes uniqueness and rank-one tightness of the semidefinite relaxation, while the proved noise threshold remains limited by a suboptimal bound.
- 4.1 Global optimizers of (QP) are close to z: The proof first bounds the MLE’s ℓ2 and ℓ∞ errors relative to the planted signal after global phase alignment.The ℓ2 bound is later used for SDP tightness, while the ℓ∞ bound controls individual coordinate errors.
- 4.2 Optimality conditions for (SDP): The KKT conditions characterize global SDP optimizers, and rank(Ŝ) = n−1 ensures a unique rank-one primal solution.Slater’s condition makes the KKT conditions necessary and sufficient for global optimality.
- 4.3 Construction of the dual certificate S: The candidate certificate is derived from first-order conditions, then shown feasible using inequalities based on z-discordance of the noise.Its dependence on the unknown optimizer x is the central technical difficulty.
- 4.3 Construction of the dual certificate S: For a critical point x, S = ℜ{ddiag(CX)} − C is the unique certificate whose positive semidefiniteness is equivalent to SDP optimality.Thus, analyzing S preserves the original optimization question rather than introducing a separate sufficient condition.
- 4.4 A sufficient condition for rank recovery: Second-order critical points of (QP) that outperform the planted signal provide a tractable characterization of the unknown MLE.The MLE is one such point, avoiding the need for a closed-form expression for the global optimizer.
- 4.4 A sufficient condition for rank recovery: The proved sufficient condition is σ ≤ 1/(18n^1/4), while the unresolved ∥Wx∥∞ bound prevents reaching the empirically suggested σ ≤ n^1/2 polylog(n) rate.The bottleneck is the σ^2 term in the available bound.
5 Conclusions
The paper makes partial progress toward polynomial-time computation of the angular synchronization MLE when exact signal recovery is unavailable. It identifies the current noise-rate bottleneck and notes extensions that remain outside the analysis.
- 5 Conclusions: The paper proves polynomial-time computation and certification of the MLE only within a suboptimal noise regime, leaving higher empirically observed noise levels unresolved.Improving the bound from (4.11) to ˜O(√n) is identified as the route toward the tentatively correct rate.
- 5 Conclusions: The analysis does not cover incomplete measurement graphs or synchronization of rotations in Rd, whose noncommutativity may make tightness harder to establish.The paper specifically highlights rotations for d > 2 and incomplete weighted graphs as open settings.
A Wigner matrices are discordant
The appendix proves that complex Wigner matrices are z-discordant with high probability for any unit-modulus vector z. The proof reduces to z = 1 by distributional invariance and controls the relevant Gaussian quantities through eigenvalue and tail bounds.
- A Wigner matrices are discordant: For arbitrary z ∈ C^n with |z_1| = ··· = |z_n| = 1, complex Wigner matrices are z-discordant with high probability.This is Proposition 3.3 proved in the appendix.
- A Wigner matrices are discordant: Diagonal phase conjugation preserves the distribution of W, so z-discordance reduces without loss of generality to 1-discordance.The reduction uses the uniform random phases of complex normal entries.
- A Wigner matrices are discordant: The Gaussian-process comparison uses Slepian’s theorem and Gaussian concentration to obtain a tail bound in the complex-valued setting.The complex argument is included as a self-contained counterpart to familiar real-valued bounds.
- A Wigner matrices are discordant: The proof bounds the largest eigenvalue λ+ = max_{∥v∥=1} v∗Wv using a real-valued Gaussian process indexed by unit vectors.A union bound then also controls the smallest eigenvalue and hence the largest eigenvalue in magnitude.
- A Wigner matrices are discordant: A normalized W1 has jointly Gaussian coordinates with standard complex-Gaussian marginals, enabling a union-bound control of their maximum absolute value.The stated bound is at most 2k e^{-t^2/4} for k such variables exceeding t.