Premium
The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
Author(s) -
Chen Yuxin,
Candès Emmanuel J.
Publication year - 2018
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.21760
Subject(s) - iterated function , algorithm , mathematics , modulo , pairwise comparison , computation , quadratic equation , mathematical optimization , range (aeronautics) , power iteration , computer science , discrete mathematics , iterative method , statistics , mathematical analysis , materials science , geometry , composite material
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 ∊ {1, …, m }, 1 ≤ i ≤ n , given noisy observations of their modulo differences { x i — x j mod m }. We propose a low‐complexity and model‐free nonconvex procedure, which operates in a lifted space by representing distinct label values in orthogonal directions and 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.© 2018 Wiley Periodicals, Inc.