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 -