Iterative Least Trimmed Squares for Mixed Linear Regression

In vanilla linear regression, one (implicitly) assumes that each sample is a linear measurement of a single unknown vector, which needs to be recovered from these measurements. Statistically, it is typically studied in the setting where the samples come from such a ground truth unknown vector, and we are interested in the (computational/statistical complexity of) recovery of this ground truth vector. Mixed linear regression (MLR for brevity) is the problem where there are multiple unknown vectors, and each sample can come from any one of them (and we do not know which one, a-priori). Our objective is again to recover all (or some, or one) of them from the samples. In this paper we consider MLR with the additional presence of corruptions - i.e. adversarial additive errors in the responses - for some unknown subset of the samples. There is now a healthy and quickly growing body of work on algorithms, and corresponding theoretical guarantees, for MLR with and without additive noise and corruptions; we review these in detail in the related work section. In our paper we start from a classical (but hard to compute) approach from robust statistics: least trimmed squares [Rou84]. This advocates fitting a model so as to minimize the loss on only a fraction τ of the samples, instead of all of them - but crucially, the subset S of samples chosen and the model to fit them are to be estimated jointly.