## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 1648-1714 |

Number of pages | 67 |

Journal | Communications on Pure and Applied Mathematics |

Volume | 71 |

Issue number | 8 |

DOIs | |

State | Published - Aug 2018 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)
- Applied Mathematics