A convex program for mixed linear regression with a recovery guarantee for well-separated data. (5th January 2018)

• Record Type: Journal Article
• Authors: Hand, Paul; Joshi, Babhru
• Is Part Of: Information and inference. Volume 7:Number 3(2018)
• Page Start: 563
• Page End: 579
• Publication Date: 2018-01-05
• Subjects: mixed linear regression -- L1 minimization -- second-order cone programming -- clustering -- iteratively reweighted least squares; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iax018
• Languages: English
• ISSNs: 2049-8764

Abstract

Abstract: We introduce a convex approach for mixed linear regression over d features. This approach is a second-order cone program, based on L1 minimization, which assigns an estimate regression coefficient in $\mathbb {R}^{d}$ for each data point. These estimates can then be clustered using, for example, k -means. For problems with two or more mixture classes, we prove that the convex program exactly recovers all of the mixture components in the noiseless setting under technical conditions that include a well-separation assumption on the data. Under these assumptions, recovery is possible if each class has at least d -independent measurements. We also explore an iteratively reweighted least squares implementation of this method on real and synthetic data.