The Projected Power Method: A Nonconvex Algorithm for Discrete Problems

21 Apr
Electrical Engineering Seminar Series
Yuxin Chen, Princeton University
Friday, April 21, 2017 -
3:00pm to 4:00pm
Pierce Hall 209

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 work makes progress towards efficient computation by focusing on a concrete joint 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.  We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.

Speaker Bio: 

Yuxin Chen is currently an assistant professor in the Department of Electrical Engineering at Princeton University.  Prior to joining Princeton, he was a postdoctoral scholar in the Department of Statistics at Stanford University, and he completed his Ph.D. in Electrical Engineering at Stanford University.  His research interests include high-dimensional structured estimation, convex and nonconvex optimization, statistical learning, and information theory.

Yue Lu
Gioia Sweetland