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 - Funding Information:
Acknowledgment. E.C. is partially supported by National Science Foundation Grant IIS-1546206 and by the Math+X Investigator award from the Simons Foundation. Y.C. is supported by the same award and the Princeton SEAS Innovation Award. We thank Qixing Huang for many motivating discussions about the joint image alignment problem. Y.C. is grateful to Vincent Monardo for his helpful comments on an early version of the paper, to Qixing Huang and Leonidas Guibas for inspiring discussions about joint graph matching, and to Tao Zhang for motivating discussion about water-fat separation.
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 -