Reviews: Iterative Least Trimmed Squares for Mixed Linear Regression

The paper considers the problem of mixed linear regression: in this problem, an algorithm is given access to n data samples (x_i, y_i) with possibly corrupted labels, where each y_i is one of the m possible linear functions of x_i, i.e., y_i x_i T theta_j for j in {1,...,m} (but the algorithm does not know which one). The goal of the algorithm is to determine vectors theta_1,..., theta_m. A straightforward but computationally inefficient (the complexity is exponential in d) approach to solving this problem is by using Least Trimmed Squares (LTS), which tries to identify the best fit vector (in terms of least squares) over all possible subsets of the data points of a particular, predefined size. To address this issue, the paper proposes using an alternative, simple, algorithm called Iterative Least Trimmed Squares (ILTS), which is similar to other algorithms that have been used for related problems in the literature, as acknowledged in the paper. The algorithm is essentially alternating minimization: it alternates between (1) finding the best set of a given size tau * n, given the least squares solution from the previous iteration and (2) solving least squares over the set determined in (1).