Various applications involve assigning discrete label values to a collection
of objects based on some pairwise noisy data. Due to the discrete---and hence
nonconvex---structure of the problem, computing the optimal assignment
(e.g.~maximum likelihood assignment) becomes intractable at first sight. This
paper makes progress towards efficient computation by focusing on a concrete
joint alignment problem---that is, the problem of recovering $n$ discrete
variables $x_i \in \{1,\cdots, m\}$, $1\leq i\leq n$ given noisy observations
of their modulo differences $\{x_i - x_j~\mathsf{mod}~m\}$. We propose a
low-complexity and model-free procedure, which operates in a lifted space by
representing distinct label values in orthogonal directions, and which attempts
to optimize quadratic functions over hypercubes. Starting with a first guess
computed via a spectral method, the algorithm successively refines the iterates
via projected power iterations. We prove that for a broad class of statistical
models, the proposed projected power method makes no error---and hence
converges to the maximum likelihood estimate---in a suitable regime. Numerical
experiments have been carried out on both synthetic and real data to
demonstrate the practicality of our algorithm. We expect this algorithmic
framework to be effective for a broad range of discrete assignment problems.

该论文提出了一种新的低复杂度算法框架，基于投影幂迭代算法，处理了离散标签分配等多种应用问题，解决了经典问题主要通过最大似然估计，同时证明了算法在一定条件下的正确性及收敛性。