On the complexity of piecewise affine system identification

DOI10.1016/J.AUTOMATICA.2015.09.031MaRDI QIDQ901110zbMATH OpenOpenAlexFDO

Authors Fabien Lauer

Publication date 23 December 2015

Published in Automatica (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityglobal optimizationsystem identificationpiecewise affine systemspiecewise affine regression

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(15)

• Rao-blackwellized sampling for batch and recursive Bayesian inference of piecewise affine models
• Optimal complexity reduction of polyhedral piecewise affine systems
• Piecewise affine regression via recursive multiple least squares and multicategory discrimination
• Identification of hybrid and linear parameter‐varying models via piecewise affine regression using mixed integer programming
• Global optimization for low-dimensional switching linear regression and bounded-error estimation
• Data-driven switching modeling for MPC using regression trees and random forests
• 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
• Persistence of excitation for identifying switched linear systems
• scientific article; zbMATH DE number 1956624 (Why is no real title available?)
• Piecewise affine identification of a hydraulic pumping system using evolutionary computation
• 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)