On the complexity of switching linear regression
  This technical note extends recent results on the computational complexity of
globally minimizing the error of piecewise-affine models to the related problem
of minimizing the error of switching linear regression models. In particular,
we show that, on the one hand the problem is NP-hard, but on the other hand, it
admits a polynomial-time algorithm with respect to the number of data points
for any fixed data dimension and number of modes.
