SIAM Journal on Optimization · 2018 · 108 citations · 34 references
Natural SciencesComputer ScienceAlgorithmsOptimizationTheory Of ComputationConvex OptimizationDigital Signal ProcessingGlobal OptimizationMaximum Likelihood EstimationNumerical AlgorithmsNumerical AnalysisConvex RelaxationsLarge-scale Convex OptimizationMaximum Likelihood EstimatorPolynomial-time AlgorithmsQuadratic Programming RelaxationsSemidefinite ProgrammingSemidefinite Programming RelaxationSemidefinite Relaxation
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.
34
A tutorial on spectral clustering
Ulrike von Luxburg · Statistics and Computing · 2007 · 10.3K citations · Full text
SPECTRAL CLUSTERING AND THE HIGH-DIMENSIONAL STOCHASTIC BLOCKMODEL
Karl Rohe, Sourav Chatterjee, Bin Yu · 2013 · 799 citations