PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonconvex phase synchronization

Nicolas Boumal

arXiv:1601.06114v3math.OC

TL;DR

The paper asks how to solve phase synchronization globally despite its nonconvex, generally hard least-squares formulation. It uses an inertia-modified generalized power method in the original low-dimensional space and analyzes second-order optimality conditions. Under restrictive noise conditions, the method converges to the global optimum, while second-order criticality is also sufficient; the authors note extensions beyond Gaussian noise and two-dimensional phase synchronization as open directions.

  • Problem

    Phase synchronization estimates unknown phases from noisy relative measurements, but its nonconvex optimization problem is generally NP-hard.

  • Method

    The paper applies a generalized power method with an inertia term directly in C^n and studies second-order optimality conditions for the nonconvex problem.

  • Results

    Under restrictive noise conditions, the generalized power method converges to the unique global optimum up to phase, and all second-order critical points are global optima.

  • Takeaways & Limitations

    The method is more practical than semidefinite relaxation, while experiments suggest both approaches succeed in the same noise regime.

  • Takeaways & Limitations

    The guarantees require more restrictive noise assumptions than the semidefinite-relaxation results, and extensions to rotations and non-Gaussian noise remain prospective.

Abstract

from arXiv · show

We estimate $n$ phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.

1 Introduction

Phase synchronization estimates unknown angles from noisy relative-phase measurements, yielding a nonconvex least-squares problem with an unidentifiable global phase. The paper studies when global optima and globally convergent algorithms can nevertheless be obtained under noise.

  • The task recovers n phases from noisy measurements of pairwise phase differences, with applications including clock synchronization and phaseless signal reconstruction.
  • The optimization is nonconvex and generally NP-hard, although semidefinite relaxation can sometimes certify global optimality and solve the problem in polynomial time.
  • Because measurements contain only relative information, the signal is identifiable only up to multiplication by a common phase.
  • The approach is more practical than high-dimensional semidefinite relaxation, while experiments suggest both methods succeed in the same noise regime.
  • A generalized power method operates directly in C^n, alternating an inertia-shifted matrix application with projection onto the unit-modulus constraint set.
  • Under stated operator- and signal-alignment noise bounds, the generalized power method converges to the unique global optimum up to phase when adequately initialized.
  • In the same noise regime, second-order necessary optimality conditions are sufficient, so algorithms reaching second-order critical points reach global optima regardless of initialization.
  • For white Gaussian noise, the assumptions hold with high probability when variance is not too large; the proven Gaussian regime is σ = O(n^1/6), while experiments suggest σ = ˜O(n^1/2) is acceptable.

2 The eigenvector method

The eigenvector method relaxes the unit-modulus constraints to a single norm constraint, yielding a tractable estimator that is close to the signal but need not solve the original problem.

  • Spectral relaxation: Relaxing the n unit-modulus constraints to ||x||2^2 = n makes the leading eigenvector of C a global optimum of the relaxed problem.Its component-wise phase projection provides the eigenvector estimator used for phase synchronization.
  • Estimator quality: The projected eigenvector estimator is nearly as close to the ground-truth signal as global optima of (P).The comparison is made using the phase-aligned distance to z.
  • Scope: The method applies to the real sign-synchronization setting as well as the complex phase-synchronization setting.In the real case, the unknown entries lie in {±1} and measurements are relative signs.
  • Limitation: The eigenvector estimator does not generally produce a global optimum of (P) because the original component-wise constraints are stronger than the relaxed norm constraint.The leading eigenvector is efficiently computable, and its phase projection is used as an estimator.

3 The generalized power method

The generalized power method adds inertia to power-method updates and projects each iterate entrywise onto the unit circle. Its cost improves monotonically, and under noise conditions it converges to the unique global optimum up to phase.

  • Algorithm: GPM alternates applying C + αI to the current iterate with entrywise phase normalization onto the feasible set.The inertia parameter α is chosen so that C + αI is positive semidefinite; the algorithm iterates x_{k+1} = T(x_k).
  • Monotonicity: The inertia term ensures strict cost improvement unless an iterate is already fixed, so the sequence cannot cycle.All accumulation points are fixed points and have cost at least that of the initialization.
  • Fixed-point landscape: Fixed points split into good and bad groups according to their correlation with z, with good points near z and bad points far away.For α = ||∆||op and ||∆||op < n/16, the two groups are separated by correlation bounds.
  • Convergence analysis: If ||∆||op ≤ n/13 and α ≤ ||∆||op, every accumulation point is a good fixed point satisfying |z∗x| ≥ n − 8||∆||op.A suitable initialization rules out convergence to the bad fixed points through monotonicity.
  • Global convergence: Under the theorem’s bounds on ||∆||op and ||∆z||∞, GPM converges in the quotient space to the unique global optimum of (P) up to phase.The proof shows accumulation points are globally optimal and that the optimum is unique up to phase.

4 About sufficiency of necessary optimality conditions

The paper studies whether first- and second-order necessary conditions identify global solutions of the nonconvex problem. In the relevant noise regime, second-order critical points are close to the signal and are globally optimal.

  • Optimality conditions: Second-order critical points satisfy first- and second-order necessary optimality conditions on the phase manifold.These conditions correspond to a zero Riemannian gradient and a negative semidefinite Riemannian Hessian.
  • Sufficiency: Under the paper’s perturbation assumptions, the necessary conditions are sufficient for global optimality.This makes the nonconvex problem solvable by algorithms that converge to second-order critical points, including certain Riemannian trust-region methods.
  • Connection to GPM: The fixed points of GPM coincide with critical points under the stated diagonal condition, linking the algorithmic and landscape analyses.All GPM fixed points are critical points, and all second-order critical points are fixed points when diag(C + αI) ≥ 0.
  • Localization: All second-order critical points are close to z when diag(C) ≥ 0 and ||∆||op ≤ n/13.The resulting phase-aligned distance obeys d(z, x)^2 ≤ 8||∆||op.
  • Localization: Second-order critical points cannot remain in the low-correlation branch, which leaves only points near z.The proof separates candidate points into high- and low-correlation cases and excludes the latter.
  • Local convergence: Smaller perturbations improve the conditioning of the Riemannian Hessian and therefore the local convergence of Riemannian optimization methods.The condition-number statement excludes the trivial eigenvalue caused by global phase indeterminacy.

5 Numerical experiments

Experiments compare eigenvector, GPM, and Riemannian trust-region estimators under Gaussian noise. GPM and RTR reach the same broad solvable noise regime as semidefinite relaxation while scaling better in practice.

  • Experimental setup: The experiments generate 100 independent Gaussian-noise realizations for each combination of signal size n and noise level σ.Each realization uses C = zz∗ + σW and compares eigenvector, GPM, and RTR estimators.
  • GPM implementation: GPM is initialized with the eigenvector estimator and uses α = max(0, −λmin(C)), the smallest value ensuring the shifted matrix is positive semidefinite.Iterations continue until the normalized update criterion reaches 1 − 10^-7.
  • RTR implementation: RTR uses default settings and a random initial guess, stopping when the scaled Riemannian gradient norm falls below 10^-6.The reported comparison includes average iteration counts and numerical global-optimality tests.
  • Global-optimality regime: Noise levels up to approximately O~(n^1/2) appear manageable, and GPM and RTR solve (P) in the same regime as the semidefinite relaxation.Both methods scale better than interior-point methods in practice.
  • Estimator accuracy: RTR is mostly as accurate as the eigenvector estimator, with a slight advantage and a consistent benefit when n is large and σ is just below √n.In that challenging regime, RTR outperforms the simpler eigenvector estimator.
  • Baseline: The eigenvector estimator is used as a baseline for identifying when spectral initialization is effective and for comparing practical computation.The experiments also assess how often it has greater likelihood than the planted signal.

6 Perspectives and conclusions

The paper shows that phase synchronization can reach global optimality with a simple low-dimensional GPM under noise conditions, while second-order necessary conditions become sufficient in the same regime. It also identifies extensions and open questions involving broader transformations, robust costs, and convergence rates.

  • Conclusions: GPM solves phase synchronization to global optimality in the low-dimensional space C^n under specified noise conditions.The approach is presented as more practical than semidefinite relaxation in a higher-dimensional lifted space.
  • Conclusions: The main theorems require more restrictive noise assumptions than the SDP relaxation, although experiments suggest GPM and RTR succeed in the same regime as SDP.The analysis bottleneck is Lemma 12, whose improvement could benefit both analyses.
  • Conclusions: Under suitable noise conditions, second-order necessary optimality conditions are sufficient for (P), and strong duality holds.The paper notes that the broader relationship between strong duality and sufficiency remains unknown for related nonconvex problems.
  • Future directions: A natural extension is synchronization of rotations and orthogonal transformations in R^d for d > 2.Experiments not shown suggest that GPM and RTR perform well in this extended setting.
  • Future directions: For non-Gaussian noise, alternative robust costs such as least unsquared deviations may support adaptations of GPM via iteratively reweighted least squares.The convergence of such methods to global optimality remains an open question.
  • Future directions: Convergence-rate analysis remains an open problem, although empirical results suggest few GPM iterations in favorable noise regimes.Existing worst-case bounds for RTR apply here but appear pessimistic relative to empirical performance.

A Connectedness of the set of accumulation points

The convergence analysis establishes that the set of accumulation points of the iterates is connected and that every accumulation point is a fixed point. This argument relies on sufficient decrease and vanishing successive-step distances.

  • Connectedness argument: Increasing the inertia parameter α can make the modified matrix strictly positive definite, but slows convergence and strengthens noise conditions.The increase in α can be chosen arbitrarily small.
  • Connectedness argument: The accumulation-point set is connected because sufficiently small successive steps prevent the iterates from jumping between separated open neighborhoods.A contradiction is obtained by interleaving convergent subsequences approaching points in two disconnected components.
  • Connectedness argument: Strong convexity yields a cumulative bound on successive iterate differences, implying that the step size tends to zero.The update selects x^{k+1} to maximize the relevant linearized objective over C^n.
  • Connectedness argument: Every accumulation point is a fixed point of the update map.This conclusion follows from the preceding fixed-point lemma.

B Technical convergence lemma

The technical convergence lemma shows that, on a compact metric space, convergence of objective values to the unique optimizer forces the iterates themselves to converge to that optimizer.

  • Technical convergence lemma: If a continuous function has a unique point attaining the target objective value, any sequence whose objective values converge to that value converges to the unique point.Compactness guarantees convergent subsequences, and uniqueness forces every such subsequence to have the same limit.
  • Technical convergence lemma: The proof characterizes convergence by requiring that, for every ε > 0, all sufficiently late iterates lie within ε of the target point.Failure of convergence would produce a subsequence remaining at least ε away.
  • Technical convergence lemma: Compactness of the set outside an ε-neighborhood yields a convergent subsequence away from the target, contradicting uniqueness of the accumulation point.Therefore the full sequence converges to the unique optimizer.
  • Technical convergence lemma: The proof’s contradiction argument is attributed to a Mathematics Stack Exchange post.This attribution concerns the proof technique rather than the convergence result itself.

C Projection to Cn

The projection argument compares a vector’s distance to the planted phase vector before and after projection onto the unit-modulus constraint set. It establishes a factor-of-two distance bound coordinatewise.

  • Projection bound: Projection from C^n to the unit-modulus set increases squared distance to z by at most a factor of 2.The bound is proved entry by entry.
  • Projection bound: The projected coordinate is obtained by retaining the phase of each nonzero input coordinate, while zero coordinates are handled separately.For nonzero v_i, write v_i = r e^{iθ} z_i before comparing projected and original distances.
  • Projection bound: The projected-coordinate error is |e^{iθ} − 1|^2 = 2(1 − cos θ), whereas the unprojected error is 1 + r^2 − 2r cos θ.These expressions reduce the comparison to minimizing over r ≥ 0.
  • Projection bound: Minimizing the unprojected error over r ≥ 0 gives r = cos θ when cos θ ≥ 0 and r = 0 otherwise.The resulting bound uses 1 − (cos θ)^2 = |sin θ| in the first case and 1 in the second.
Loading 1601.06114v3…