PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-optimal bounds for phase synchronization

Yiqiao Zhong, Nicolas Boumal

arXiv:1703.06605v1math.OC

TL;DR

Phase synchronization requires estimating a unit-modulus phase vector from noisy relative measurements, but the MLE’s nonconvex optimization problem had analyses limited to σ = O(n^1/4). This paper proves SDP tightness and GPM convergence for σ = O(√(n/log n)), using auxiliary iterate sequences to control dependence.

  • Problem

    Existing analyses rigorously supported efficient phase synchronization only up to σ = O(n^1/4), despite empirical success near σ = O(√n).

    Source: §1 · p. 2

  • Method

    The paper tracks n auxiliary sequences of feasible iterates alongside GPM’s iterates to reduce statistical dependence and establish perturbation bounds.

    Source: §1 · p. 3, The difficulty: statistical dependence · p. 4, Introducing auxiliary problems to… · p. 5

  • Results

    SDP and GPM find the global optimum with high probability for σ = O(√(n/log n)); GPM also converges linearly, and the MLE receives a tighter ℓ∞ bound.

    Source: §1 · pp. 2–3, §5 · p. 20

  • Takeaways & Limitations

    The results show that maximum-likelihood phase synchronization is computationally feasible in a noise regime that nearly matches the information-theoretic threshold.

    Source: §5 · p. 20

    Whether the extra logarithmic factor is necessary for efficiently computing the MLE up to the threshold remains undetermined.

    Source: §1 · p. 4

Abstract

from arXiv · show

The problem of phase synchronization is to estimate the phases (angles) of a complex unit-modulus vector $z$ from their noisy pairwise relative measurements $C = zz^* + \sigma W$, where $W$ is a complex-valued Gaussian random matrix. The maximum likelihood estimator (MLE) is a solution to a unit-modulus constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite relaxation (SDP) approach or the generalized power method (GPM) to solve it. Numerical experiments suggest both of these methods succeed with high probability for $\sigma$ up to $\tilde{\mathcal{O}}(n^{1/2})$, yet, existing analyses only confirm this observation for $\sigma$ up to $\mathcal{O}(n^{1/4})$. In this paper, we bridge the gap, by proving SDP is tight for $\sigma = \mathcal{O}(\sqrt{n /\log n})$, and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter $\ell_\infty$ bound for the MLE. A novel technique we develop in this paper is to track (theoretically) $n$ closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an $\ell_\infty$ perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.

1 Introduction

This section establishes tractability of phase synchronization in a near-optimal noise regime through SDP tightness and global convergence of GPM. It develops auxiliary-sequence tracking to analyze dependence and contraction, while connecting eigenvector initialization, dual certificates, and sharper perturbation and MLE guarantees.

1 Introduction

  • With high probability for large n, SDP admits a unique solution that is a global optimum of (P), while GPM in the same regime converges at least linearly to (P)’s global optimum, improving prior σ = O(n1/4) guarantees.Source: §1 · pp. 2–3

Analysis of iterations: tracking n auxiliary sequences

The difficulty: statistical dependence

  • The analysis targets the dependent quantity ∥W ˆx∥∞, whose sharp control is needed for SDP tightness and ℓ∞ estimation because W and the MLE ˆx depend on each other.Earlier suboptimal bounds on this dependence led to weaker admissible-noise regimes [2, eq. (4.11)][8, Lemma 12][23, Proof of Thm. 2].Source: The difficulty: statistical dependence · pp. 4–5

Introducing auxiliary problems to reduce dependence

First analysis: an ℓ∞perturbation bound for eigenvectors

  • The leading eigenvector initializer satisfies a sharp ℓ∞ perturbation bound in the regime σ = O(√(n / log n)), making it an estimator of z comparable to the MLE up to constants.The bound follows by comparing the full matrix with row-and-column-deleted perturbations using eigenvector perturbation analysis.Source: First analysis: an ℓ∞perturbation… · pp. 7–8

Analysis of iterations: tracking n auxiliary sequences

  • Tracking n auxiliary sequences keeps the actual and modified GPM paths close through local contraction, with discrepancy errors remaining small because the modified noise is independent of the auxiliary iterates.The recursive bound prevents proximity errors from accumulating over iterations and yields an O(σ√(log n/n)) discrepancy error, smaller than the O(σ) iterate-to-solution distance.Source: Analysis of iterations: tracking n… · p. 9
  • Controlling ∥W x_t∥∞ and proving proximity to auxiliary paths are essential for keeping iterates in the contraction region and completing the induction.Source: Analysis of iterations: tracking n… · p. 9
  • The proof handles infinitely many iterations by using concentration through T = O(n^2), then deterministic induction and exponentially decaying updates to preserve contraction afterward.This keeps later iterates in a slightly enlarged contraction region despite the nonzero probability that concentration inequalities fail.Source: Analysis of iterations: tracking n… · p. 10
  • A dual optimality certificate S = Re{ddiag(Cx∞(x∞)∗)} − C verifies that the GPM limit is an optimal and phase-unique solution of (P).Source: Analysis of iterations: tracking n… · p. 10
  • Eigenvector perturbation bounds establish the practical leading-eigenvector initializer, while initializing theoretically at z would already suffice to prove SDP tightness.Including the perturbation analysis additionally yields a guarantee for the runnable version of Algorithm 1.Source: Analysis of iterations: tracking n… · p. 10

2 Main results

The paper formalizes phase synchronization under global-phase ambiguity and proves that SDP and GPM succeed in the regime σ = O(√(n/log n)). It also establishes eigenvector and MLE error guarantees under a broader sub-gaussian noise model.

Quotient space

  • Global phase cannot be identified because replacing z by zeiθ leaves the relative measurements unchanged, so distances and optima are interpreted modulo phase.The quotient-space formulation records this invariance explicitly.Source: §2 · pp. 10–11

Noise model

  • All optimization statements extend from Gaussian noise to Hermitian Wigner matrices with sub-gaussian entries, although (P) need not remain an MLE in that broader model.The Gaussian model is a special case of the richer noise class.Source: §2 · p. 11

SDP approach

  • σ ≤ c0√(n/log n) yields a unique rank-one SDP solution and a unique global optimum of (P) up to phase, with probability 1 − O(n^-2).This rigorously closes the gap between earlier σ = O(n^1/4) guarantees and the empirically suggested near-√n regime.Source: §2 · p. 12

GPM approach

  • σ ≤ c0√(n/log n) also gives GPM linear convergence to an optimum up to phase, with probability 1 − O(n^-2).GPM extracts entrywise phases after multiplication by C, rather than projecting onto a sphere, and is described as much faster than SDP.Source: §2 · p. 12
  • The GPM limit is the unique optimum of (P) up to phase and satisfies the paper’s stated ℓ2 and ℓ∞ error bounds.The global phase is chosen so that ˆx*z = |ˆx*z| when stating the bounds.Source: §2 · p. 12

Eigenvector estimator

  • The leading eigenvector and its entrywise projection satisfy error bounds comparable to the MLE, while the paper derives a tighter ℓ∞ perturbation guarantee.The eigenvector result addresses an ℓ∞ question that had received less attention than ℓ2 perturbation analysis.Source: §2 · p. 13

3 Proof organization for eigenvector perturbations

The eigenvector perturbation analysis combines concentration bounds with auxiliary leave-one-row-and-column problems. This isolates sparse perturbations and enables sharper entrywise control than a generic operator-norm argument.

Concentration lemmas

  • Concentration lemmas uniformly control perturbations over finite, noise-independent sets of eigenvectors and iterates with high probability.The sets may contain the leading eigenvectors or the first T + 1 auxiliary GPM iterates, with cardinality at most 3n^2.Source: Concentration lemmas · pp. 13–14
  • The proof bounds row-wise noise interactions using sub-gaussian concentration, including terms of order O(√(n log n)) with high probability.These bounds are used later to control ℓ∞ quantities such as ∥W˜x∥∞.Source: Concentration lemmas · p. 14

Introducing auxiliary eigenvector problems

  • Auxiliary eigenvectors ˜x(m), formed by deleting the mth row and column noise contributions, are independent of the corresponding sparse perturbations.This independence permits sharper concentration after splitting W˜x into a dominant term and a discrepancy term.Source: Introducing auxiliary eigenvector… · p. 14, Concentration lemmas · p. 14
  • The sparse-perturbation comparison gives d2(˜x,˜x(m)) = O(σ√(log n/n)), much smaller than the global error d2(˜x,z) = O(σ).The difference is small because the perturbation affects only one row and column.Source: Introducing auxiliary eigenvector… · p. 15
  • Using ∥E˜u∥2 rather than the looser ∥E∥2 in Davis–Kahan yields a sharper eigenvector perturbation bound for sparse random perturbations.The paper emphasizes that ∥E˜u∥2 can be much smaller than ∥E∥2 when the eigenvector is not entrywise large.Source: Introducing auxiliary eigenvector… · p. 15

4 Proof organization for phase synchronization

The phase-synchronization proof establishes local contraction for GPM, tracks auxiliary iterates to control dependence, and then verifies optimality through an SDP dual certificate. This yields convergence and uniqueness under the stated noise conditions.

Local contraction lemmas

  • Entrywise projection requires ℓ∞ bounds in addition to ℓ2 bounds, because the unit-modulus constraint acts separately on each coordinate.This is the central technical complication beyond the ordinary normalized power method.Source: Local contraction lemmas · p. 16
  • Under suitable neighborhood and noise conditions, the GPM operator is locally contractive with ratio ρ ∈ (0,1) along the relevant iterates.The operator need not contract on the entire neighborhood; contraction along the iterates is sufficient.Source: Local contraction lemmas · pp. 16–17

4 Proof organization for phase synchronization

  • The proof tracks n auxiliary GPM sequences generated from modified matrices to keep them close to the actual iterates and preserve independence for concentration arguments.These sequences are theoretical only and are not computed in practice.Source: Convergence analysis · p. 17

Convergence analysis

  • The auxiliary-sequence induction controls dependence between the random operator and iterates, while concentration bounds keep the iterates in the contraction region.The first T + 1 iterations use concentration, and later iterations use deterministic arguments.Source: Convergence analysis · pp. 17–18
  • The iterate differences decrease geometrically for the initial iterations, after which the sequence remains close to a limiting fixed point by deterministic induction.After T = 3n^2 − 1 iterations, the updates are almost negligible, and the limit inherits the established bounds.Source: Convergence analysis · pp. 18–19

Verifying optimality

  • A dual certificate proves the limiting point is globally optimal: positive semidefiniteness and rank n − 1 imply a unique SDP solution and a unique optimum of (P) up to phase.The certificate is checked using the limit’s distance and noise bounds.Source: Verifying optimality · pp. 19–20

5 Conclusions and perspectives

The paper establishes that SDP and GPM recover the global optimum under noise σ = O(√(n/log n)), nearly matching the information-theoretic threshold. It also identifies proof innovations, error-bound improvements, and directions involving broader synchronization groups, incomplete measurements, and robustness.

5 Conclusions and perspectives

  • SDP and GPM find the global optimum with high probability when σ = O(√(n/log n)), making the MLE computationally feasible in this regime.This regime nearly matches the information-theoretic threshold and closes the gap in previous analyses.Source: §5 · p. 20
  • Tracking n auxiliary sequences enables the analysis, while also yielding an improved ℓ∞ bound for the MLE and an ℓ∞ eigenvector perturbation bound.The eigenvector bound is presented as an independently interesting by-product.Source: §5 · p. 20
  • Second-order critical-point sufficiency remains unresolved, and the GPM analysis does not directly characterize all second-order critical points.Existing results cited in the passage only establish this property for σ = O(n^1/6) and σ = O(n^1/4).Source: §5 · p. 20
  • Extensions include synchronization over SO(d) and SE(d), incomplete measurement graphs, and robust losses for outlier-prone measurements.The present work addresses SO(2) with all entries of C known and squared-error loss; SO(3) introduces non-commutativity.Source: §5 · pp. 20–21

Proofs for Section 3

The Section 3 proofs establish concentration bounds for Gaussian-noise quantities and use them to control eigenvector-related terms. These bounds support the stated perturbation and error conclusions with high probability.

Proofs for Section 3

  • Concentration arguments control the noise matrix, leave-one-coordinate-out perturbations, and quadratic noise terms uniformly over relevant choices.The proof uses sub-gaussian and sub-exponential concentration, Bernstein’s inequality, and union bounds.Source: Proofs for Section 3 · pp. 21–22
  • The resulting bounds hold with probability 1 − O(n^-2), providing the high-probability control needed for the theorem.The union bound over choices of u and m yields the stated probability.Source: Proofs for Section 3 · pp. 22–23
  • The proof applies the concentration results to eigenvector perturbation and eigengap estimates, then derives the first theorem claim.Weyl’s inequality controls the eigengap, while the leading-eigenvector analysis bounds d2(˜x, z) and related quantities.Source: Proofs for Section 3 · p. 23
  • A coordinatewise argument bounds the leading eigenvector’s noise term, yielding ∥W ˜x∥∞ ≲ √(n log n) and an associated d∞ control.The leave-one-out construction makes the relevant coordinate independent of the corresponding perturbation.Source: Proofs for Section 3 · pp. 22–23

Proofs for Section 4

The Section 4 proofs establish contraction properties for the GPM map near the signal and propagate them through auxiliary iterates. These arguments yield uniform iterate control, geometric convergence, and a fixed point corresponding to the optimum.

Proofs for Section 4

  • Decomposing vectors into signal-aligned and orthogonal components enables bounds relating phase-invariant distances to coordinatewise errors.The proof controls global phase alignment and derives inequalities used to compare normalized iterates.Source: Proofs for Section 4 · p. 24
  • Under ε < 1/2, the proof derives |1−e^{iθ}| ≤ 4ε∥e^{iθα −β∥2 and |e^{iθ}a −b| ≤ 6ε∥e^{iθα −β∥2.The second bound uses a ≤ 1 and the triangle inequality.Source: Proofs for Section 4 · p. 25
  • Induction transfers distance, coordinatewise, and eigenvector bounds from each auxiliary iterate to the next with probability 1 − O(n^-2).The leave-one-out iterates are functions of W^(m) and independent of ΔW^(m), enabling the required concentration estimates.Source: Proofs for Section 4 · p. 26
  • The contraction estimates yield geometric decay of successive GPM distances, convergence to a fixed point, and identification of that fixed point as the unique optimum up to phase.The proof uses induction, completeness of the phase-quotient space, and continuity of the GPM map.Source: Proofs for Section 4 · pp. 28–30

Proofs for Section 2

The Section 2 proofs establish the GPM convergence and optimality results under the paper’s noise condition. They combine eigenvector initialization bounds with an induction argument and conclude uniqueness up to global phase.

Proofs for Section 2

  • The proof starts from eigenvector initializers and uses established spectral bounds to verify the base-case estimates required for the GPM induction.The initialization analysis uses Weyl’s inequality and the eigengap of the perturbed matrix.Source: Proofs for Section 2 · p. 31
  • With probability 1 − O(n^-2), the iterates satisfy the required distance and coordinatewise bounds throughout the finite induction horizon.The proof explicitly invokes the established estimates and the trivial initial distance bound.Source: Proofs for Section 2 · p. 31
  • The limiting GPM iterate is the unique optimum of (P) up to phase with probability 1 − O(n^-2).This establishes the claimed optimality after the convergence argument identifies the fixed point.Source: Proofs for Section 2 · p. 31
  • The noise condition σ = O(√(n/log n)) yields an ℓ∞ error bound of the form ∥x∞ − z∥∞ ≤ Cσ.The argument combines the convergence result with the bound on the limiting iterate’s distance from the signal.Source: Proofs for Section 2 · p. 31
Loading 1703.06605v1…