Convex Relaxation of Mixture Regression with Efficient Algorithms

Part of Advances in Neural Information Processing Systems 22 (NIPS 2009)

Bibtex Metadata Paper Supplemental


Novi Quadrianto, John Lim, Dale Schuurmans, Tibério Caetano


We develop a convex relaxation of maximum a posteriori estimation of a mixture of regression models. Although our relaxation involves a semidefinite matrix variable, we reformulate the problem to eliminate the need for general semidefinite programming. In particular, we provide two reformulations that admit fast algorithms. The first is a max-min spectral reformulation exploiting quasi-Newton descent. The second is a min-min reformulation consisting of fast alternating steps of closed-form updates. We evaluate the methods against Expectation-Maximization in a real problem of motion segmentation from video data.