On the complexity of switching linear regression
This work addresses a theoretical complexity problem for researchers in machine learning and optimization, providing incremental insights by extending prior results on piecewise-affine models.
The paper tackles the computational complexity of minimizing error in switching linear regression models, showing that the problem is NP-hard but admits a polynomial-time algorithm for fixed data dimensions and mode numbers.
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.