An exact and efficient algorithm for segmentation of ARX modelsN. Ozay We consider the problem of segmentation of autoregressive models with exogenous inputs (ARX models). This problem, where the goal is to determine the parameters of a set of ARX models that can explain a given input/output data within a certain noise bound, has attracted considerable attention in recent years. Most of the recently proposed approaches are based on convex relaxations. Although efficient, these approaches do not necessarily lead to optimal solutions. In the present paper, by exploiting some early results in dynamic programming, we show that an optimal solution can indeed be obtained in polynomial-time. One salient feature of the proposed approach is that exploration of the model complexity/quality of the fit trade-off space comes with negligible additional computational cost. We discuss several other properties of the proposed approach and compare it with existing approaches on numerical examples, which show that the proposed algorithm is consistently faster. |