TY - JOUR

T1 - The Projected Power Method

T2 - An Efficient Algorithm for Joint Alignment from Pairwise Differences

AU - Chen, Yuxin

AU - Candès, Emmanuel J.

N1 - Publisher Copyright:
© 2018 Wiley Periodicals, Inc.

PY - 2018/8

Y1 - 2018/8

N2 - 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 xi ∊ {1, …, m}, 1 ≤ i ≤ n, given noisy observations of their modulo differences {xi — xj 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.

AB - 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 xi ∊ {1, …, m}, 1 ≤ i ≤ n, given noisy observations of their modulo differences {xi — xj 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.

UR - http://www.scopus.com/inward/record.url?scp=85050497443&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050497443&partnerID=8YFLogxK

U2 - 10.1002/cpa.21760

DO - 10.1002/cpa.21760

M3 - Article

AN - SCOPUS:85050497443

SN - 0010-3640

VL - 71

SP - 1648

EP - 1714

JO - Communications on Pure and Applied Mathematics

JF - Communications on Pure and Applied Mathematics

IS - 8

ER -