S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In ACM SIGKDD, volume 62, pages 63-72, 1999.
 S. Finney, L. Kaelbling, and T. Lozano-Perez. Predicting partial paths from planning problem parameters. In Proceedings of Robotics: Science and Systems, Atlanta, GA, USA, June 2007.
 A. J. Storkey and M. Sugiyama. Mixture regression for covariate shift. In Scho¨lkopf, editor, Advances in Neural Information Processing Systems 19, pages 1337-1344, 2007. [OpenAIRE]
 A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1-38, 1977.
 T. De Bie, N. Cristianini, P. Bennett, and E. Parrado-herna¨ndez. Fast sdp relaxations of graph cut clustering, transduction, and other combinatorial problems. JMLR, 7:1409-1436, 2006.
 Y. Guo and D. Schuurmans. Convex relaxations for latent variable training. In Platt et al., editor, Advances in Neural Information Processing Systems 20, pages 601-608, 2008.
 S. M. Goldfeld and R.E. Quandt. Nonlinear methods in econometrics. Amsterdam: NorthHolland Publishing Co., 1972.
 D. W. Hosmer. Maximum likelihood estimates of the parameters of a mixture of two regression lines. Communications in Statistics, 3(10):995-1006, 1974.
 H. Spa¨th. Algorithm 39: clusterwise linear regression. Computing, 22:367-373, 1979.
 W.S. DeSarbo and W.L. Cron. A maximum likelihood methodology for clusterwise linear regression. Journal of Classification, 5(1):249-282, 1988.
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.