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 for any fixed data dimension and number of modes.

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

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

Fabien Lauer. On the complexity of switching linear regression. 2015. ⟨hal-01219794v1⟩