Skip to main content

The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

Author(s): Chen, Yuxin; Candès, EJ

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1cs1n
Full metadata record
DC FieldValueLanguage
dc.contributor.authorChen, Yuxin-
dc.contributor.authorCandès, EJ-
dc.date.accessioned2021-10-08T20:16:30Z-
dc.date.available2021-10-08T20:16:30Z-
dc.date.issued2018en_US
dc.identifier.citationChen, Y, Candès, EJ. (2018). The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences. Communications on Pure and Applied Mathematics, 71 (1648 - 1714. doi:10.1002/cpa.21760en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1cs1n-
dc.description.abstractVarious 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.en_US
dc.format.extent1648 - 1714en_US
dc.language.isoen_USen_US
dc.relation.ispartofCommunications on Pure and Applied Mathematicsen_US
dc.rightsAuthor's manuscripten_US
dc.titleThe Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differencesen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1002/cpa.21760-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
The Projected Power Method An Efficient Algorithm for Joint Alignment from Pairwise Differences.pdf1.96 MBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.