On the complexity of piecewise affine system identification
Author:
Preprint
Abstract
The paper provides results regarding the computational complexity of hybrid system identification. More precisely, we focus on the estimation of piecewise affine (PWA) maps from input-output data and analyze the complexity of computing a global minimizer of the error. Previous work showed that a global solution could be obtained for continuous PWA maps with a worst-case complexity exponential in the number of data. In this paper, we show how global optimality can be reached for a slightly more general class of possibly discontinuous PWA maps with a complexity only polynomial in the number of data, however with an exponential complexity with respect to the data dimension. This result is obtained via an analysis of the intrinsic classification subproblem of associating the data points to the different modes. In addition, we prove that the problem is NP-hard, and thus that the exponential complexity in the dimension is a natural expectation for any exact algorithm.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Identification of switched linear regression models using sum-of-norms regularizationAutomatica, 2013
- Identification of switched linear systems via sparse optimizationAutomatica, 2011
- A continuous optimization framework for hybrid system identificationAutomatica, 2011
- Segmentation of ARX-models using sum-of-norms regularizationAutomatica, 2010
- NP-hardness of Euclidean sum-of-squares clusteringMachine Learning, 2009
- A Bayesian approach to identification of hybrid systemsIEEE Transactions on Automatic Control, 2005
- A bounded-error approach to piecewise affine system identificationIEEE Transactions on Automatic Control, 2005
- Identification of piecewise affine systems via mixed-integer programmingAutomatica, 2004
- A clustering technique for the identification of piecewise affine systemsAutomatica, 2003
- A survey of computational complexity results in systems and controlAutomatica, 2000