On the complexity of piecewise affine system identification

DOI10.1016/J.AUTOMATICA.2015.09.031zbMATH Open1329.93052arXiv1509.02348OpenAlexW2095838877MaRDI QIDQ901110FDOQ901110

Authors: Fabien Lauer 

Publication date: 23 December 2015

Published in: Automatica (Search for Journal in Brave)

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.

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

Recommendations

• A bounded-error approach to piecewise affine system identification
• Identification of dynamic systems using piecewise-affine basis function models
• Identification of piecewise affine systems via mixed-integer programming.
• Complexity, convergence and computational efficiency for system identification algorithms
• Two steps piecewise affine identification of nonlinear systems
• On the time complexity of worst-case system identification
• Piecewise linear identification of non-linear systems
• Complexity of identification of linear systems with rational transfer functions
• Recursive estimation in piecewise affine systems using parameter identifiers and concurrent learning

zbMATH Keywords

computational complexityglobal optimizationsystem identificationpiecewise affine systemspiecewise affine regression

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) System identification (93B30)

Cites Work

• NP-hardness of Euclidean sum-of-squares clustering
• Title not available (Why is that?)
• Title not available (Why is that?)
• A clustering technique for the identification of piecewise affine systems
• Title not available (Why is that?)
• Identification of switched linear regression models using sum-of-norms regularization
• Identification of hybrid systems. A tutorial
• Identification of switched linear systems via sparse optimization
• A Sparsification Approach to Set Membership Identification of Switched Affine Systems
• Segmentation of ARX-models using sum-of-norms regularization
• A continuous optimization framework for hybrid system identification
• Identification of piecewise affine systems via mixed-integer programming.
• A Bayesian approach to identification of hybrid systems
• A bounded-error approach to piecewise affine system identification
• A survey of computational complexity results in systems and control
• A Difference of Convex Functions Algorithm for Switched Linear Regression
• Estimating the probability of success of a simple algorithm for switched linear regression

Cited In (14)

• Rao-blackwellized sampling for batch and recursive Bayesian inference of piecewise affine models
• Optimal complexity reduction of polyhedral piecewise affine systems
• Identification of hybrid and linear parameter‐varying models via piecewise affine regression using mixed integer programming
• Piecewise affine regression via recursive multiple least squares and multicategory discrimination
• Data-driven switching modeling for MPC using regression trees and random forests
• Global optimization for low-dimensional switching linear regression and bounded-error estimation
• Valid inequalities for concave piecewise linear regression
• Recursive estimation in piecewise affine systems using parameter identifiers and concurrent learning
• Identification of piecewise affine systems via mixed-integer programming.
• Direct data‐driven design of switching controllers
• On the complexity of switching linear regression
• Title not available (Why is that?)
• Persistence of excitation for identifying switched linear systems
• Identification of piecewise affine systems based on statistical clustering technique

This page was built for publication: On the complexity of piecewise affine system identification

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