On the complexity of piecewise affine system identification
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Self-Excited Dynamics of Discrete-Time Lur'e Models with Affinely Constrained, Piecewise-C1 Feedback Nonlinearities
Self-excited systems (SES) arise in numerous applications, such as fluid-structure interaction, combustion, and biochemical systems. In support of system identification and digital control of SES, this paper analyzes dis…
AllFast Piecewise-Affine Motion Estimation Without Segmentation
Current algorithmic approaches for piecewise affine motion estimation are based on alternating motion segmentation and estimation. We propose a new method to estimate piecewise affine motion fields directly without inter…
Motion EstimationMotion SegmentationSegmentationExpressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity
Piecewise-affine neural networks (e.g., with ReLU or LeakyReLU activations) implement continuous piecewise-affine maps, and the number of affine regions provides a natural proxy for expressive capacity. However, the gap …
Identification of Analytic Nonlinear Dynamical Systems with Non-asymptotic Guarantees
This paper focuses on the system identification of an important class of nonlinear systems: linearly parameterized nonlinear systems, which enjoys wide applications in robotics and other mechanical systems. We consider t…
AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks
Piecewise affine neural networks (PANNs) provide a principled geometric perspective on neural network expressivity by characterizing the input--output map as a continuous piecewise affine (CPA) function whose complexity …