This is one of a series of talks that are given by Professor Chen. The full list of his talks is as follows:
Wednesday, August 28, 2019; 11:00 am - 12:00 pm; Groseclose 402
Thursday, August 29, 2019; 11:00 am - 12:00 pm; Groseclose 402
Tuesday, September 3, 2019; 11:00 am - 12:00 pm; Main - Executive Education Room 228
Wednesday, September 4, 2019; 11:00 am - 12:00 pm; Main - Executive Education Room 228
Thursday, September 5, 2019; 11:00 am - 12:00 pm; Groseclose 402

Check https://triad.gatech.edu/events for more information. 
For location information, please check https://isye.gatech.edu/about/maps-directions/isye-building-complex

Title of this talk: The projected power method: an efficient nonconvex algorithm for a joint discrete assignment from pairwise data

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 discrete alignment problem---that is, the problem of recovering n discrete variables given noisy observations of their modulo differences. We propose a low-complexity and model-free procedure, which operates in a lifted space by representing distinct label values in orthogonal directions, and which 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.

This is joint work with Emmanuel Candes.