Quadrianto, NoviCaetano, TiberioLim, JohnSchuurmans, Dale2015-12-10December 7http://hdl.handle.net/1885/56825We 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.Keywords: Closed form; Convex relaxation; Efficient algorithm; Expectation Maximization; Fast algorithms; Max-min; Maximum a posteriori estimation; Mixture regression; Motion segmentation; Quasi-Newton; Real problems; Regression model; Semi-definite matrix; Semi-de200910.1.1.155.2316&rank=12016-02-24