Projected Power Method for Joint Alignment from Pairwise Modulo Differences

A nonconvex iterative discrete synchronization and joint alignment algorithm (introduced by Yuxin Chen and Emmanuel J. Candès in 2018) for recovering $n$ latent discrete shifts or group elements $x_1,\dots,x_n \in \{0,1,\dots,m-1\}$ (up to a global modular shift $\bmod\ m$) from corrupted pairwise difference measurements. Representing each state $x_i$ as standard basis vector $\boldsymbol{e}_{x_i} \in \mathbb{R}^m$ and stacking $\boldsymbol{z} = [\boldsymbol{z}_1^\top,\dots,\boldsymbol{z}_n^\top]^\top \in \mathbb{R}^{nm}$ along with the $nm \times nm$ block cyclic likelihood matrix $\boldsymbol{L}$ whose $(i,j)$ block encodes the cyclic log-likelihood scores of $x_i - x_j \equiv s \pmod m$, maximum likelihood joint alignment reduces to the nonconvex quadratic program $\max_{\boldsymbol{z}} \boldsymbol{z}^\top\boldsymbol{L}\boldsymbol{z}$ subject to $\boldsymbol{z}_i \in \{\boldsymbol{e}_0,\dots,\boldsymbol{e}_{m-1}\}$ (Equations 2.2–2.5). The Projected Power Method (PPM, Algorithm 1) relaxes the discrete vertices to the scaled probability simplex $\Delta_m = \{\boldsymbol{w}\in\mathbb{R}_+^m : \mathbf{1}^\top\boldsymbol{w} \le 1\}$ and iterates $\boldsymbol{z}^{t+1} = \mathcal{P}_{\Delta}(\mu_t\boldsymbol{L}\boldsymbol{z}^t)$ (Equations 2.7–2.10), where $\mathcal{P}_{\Delta}$ applies blockwise Euclidean projection $\mathcal{P}_{\Delta_m}(\boldsymbol{v}_i) = \arg\min_{\boldsymbol{w}\in\Delta_m} \|\boldsymbol{w} - \boldsymbol{v}_i\|_2^2$ computable in $O(m\log m)$ sorting time (or $O(m)$ expected randomized pivot time) and $\mu_t$ is an amplification factor pushing iterates onto the extreme vertices $\{\boldsymbol{e}_s\}$. Theorems 1–3 prove that under a randomized corruption model with $p_{\mathrm{obs}} \gtrsim \frac{\log^2(nm)}{n \cdot \mathrm{KL}^{\min}}$ (where $\mathrm{KL}^{\min}$ is the minimum Kullback–Leibler divergence between shifted pairwise likelihoods), spectral initialization followed by $O(\log n)$ PPM iterations recovers all $n$ shifts exactly with high probability, matching the information-theoretic Fano/minimax threshold up to logarithmic factors (Theorem 4).