On the complexity of switching linear regression

DOI10.1016/J.AUTOMATICA.2016.07.027MaRDI QIDQ340631zbMATH OpenOpenAlexFDO

Authors Fabien Lauer

Publication date 14 November 2016

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.06920

zbMATH Keywords

computational complexityglobal optimizationlinear classificationswitched linear systemssystem identification

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Complexity and performance of numerical algorithms (65Y20) Linear systems in control theory (93C05) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30) Identification in stochastic control theory (93E12)

Abstract: 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.

Recommendations

• On the complexity of piecewise affine system identification
• Identification of switched linear regression models using sum-of-norms regularization
• Complexity of penalized likelihood estimation
• Estimating the probability of success of a simple algorithm for switched linear regression
• The MIN PFS problem and piecewise linear model estimation

Cites work

• A continuous optimization framework for hybrid system identification
• A Difference of Convex Functions Algorithm for Switched Linear Regression
• A survey of computational complexity results in systems and control
• Estimating the probability of success of a simple algorithm for switched linear regression
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Identification of hybrid systems. A tutorial
• Identification of switched linear systems via sparse optimization
• On the complexity of piecewise affine system identification

Cited in

(4)

• Global optimization for low-dimensional switching linear regression and bounded-error estimation
• Estimating the probability of success of a simple algorithm for switched linear regression
• Data driven stability analysis of black-box switched linear systems
• Learning stability of partially observed switched linear systems

This page was built for publication: On the complexity of switching linear regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340631)