On the complexity of switching linear regression

Fabien Lauer (1)

1 ABC - Machine Learning and Computational Biology

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.

Mots clés: Global optimization; System Identification; Switched linear systems; Computational complexity; Linear classification

Domaines: Machine Learning [stat.ML]; Complexité [cs.CC]; Automatique; Apprentissage [cs.LG]

Fabien Lauer. On the complexity of switching linear regression. Automatica, 2016, 74, pp.80-83. ⟨10.1016/j.automatica.2016.07.027⟩. ⟨hal-01219794v2⟩