Convex relaxation of mixture regression with efficient algorithms

Novi Quadrianto; Tibério S. Caetano; John Lim; Dale Schuurmans

Convex relaxation of mixture regression with efficient algorithms

Novi Quadrianto^*, Tibério S. Caetano, John Lim, Dale Schuurmans

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference
Publisher	Neural Information Processing Systems
Pages	1491-1499
Number of pages	9
ISBN (Print)	9781615679119
Publication status	Published - 2009
Event	23rd Annual Conference on Neural Information Processing Systems, NIPS 2009 - Vancouver, BC, Canada Duration: 7 Dec 2009 → 10 Dec 2009

Publication series

Name	Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

Conference

Conference	23rd Annual Conference on Neural Information Processing Systems, NIPS 2009
Country/Territory	Canada
City	Vancouver, BC
Period	7/12/09 → 10/12/09

Cite this

Quadrianto, N., Caetano, T. S., Lim, J., & Schuurmans, D. (2009). Convex relaxation of mixture regression with efficient algorithms. In Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference (pp. 1491-1499). (Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference). Neural Information Processing Systems.

Quadrianto, Novi ; Caetano, Tibério S. ; Lim, John et al. / Convex relaxation of mixture regression with efficient algorithms. Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference. Neural Information Processing Systems, 2009. pp. 1491-1499 (Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference).

@inproceedings{f77ab0e71d0b429fbcaf087609558937,

title = "Convex relaxation of mixture regression with efficient algorithms",

abstract = "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.",

author = "Novi Quadrianto and Caetano, {Tib{\'e}rio S.} and John Lim and Dale Schuurmans",

year = "2009",

language = "English",

isbn = "9781615679119",

series = "Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference",

publisher = "Neural Information Processing Systems",

pages = "1491--1499",

booktitle = "Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference",

note = "23rd Annual Conference on Neural Information Processing Systems, NIPS 2009 ; Conference date: 07-12-2009 Through 10-12-2009",

}

Quadrianto, N, Caetano, TS, Lim, J & Schuurmans, D 2009, Convex relaxation of mixture regression with efficient algorithms. in Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference. Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference, Neural Information Processing Systems, pp. 1491-1499, 23rd Annual Conference on Neural Information Processing Systems, NIPS 2009, Vancouver, BC, Canada, 7/12/09.

Convex relaxation of mixture regression with efficient algorithms. / Quadrianto, Novi; Caetano, Tibério S.; Lim, John et al.
Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference. Neural Information Processing Systems, 2009. p. 1491-1499 (Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Convex relaxation of mixture regression with efficient algorithms

AU - Quadrianto, Novi

AU - Caetano, Tibério S.

AU - Lim, John

AU - Schuurmans, Dale

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84858741522&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781615679119

T3 - Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

SP - 1491

EP - 1499

BT - Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference

PB - Neural Information Processing Systems

T2 - 23rd Annual Conference on Neural Information Processing Systems, NIPS 2009

Y2 - 7 December 2009 through 10 December 2009

ER -

Convex relaxation of mixture regression with efficient algorithms

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this