skip to main content

Title: Efficient Identification of Error-in-Variables Switched Systems via a Sum-of-Squares Polynomial Based Subspace Clustering Method
This paper addresses the problem of identification of error in variables switched linear models from experimental input/output data. This problem is known to be generically NP hard and thus computationally expensive to solve. To address this difficulty, several relaxations have been proposed in the past few years. While solvable in polynomial time these (convex) relaxations tend to scale poorly with the number of points and number/order of the subsystems, effectively limiting their applicability to scenarios with relatively small number of data points. To address this difficulty, in this paper we propose an efficient method that only requires performing (number of subsystems) singular value decompositions of matrices whose size is independent of the number of points. The underlying idea is to obtain a sum-of-squares polynomial approximation of the support of each subsystem one-at-a-time, and use these polynomials to segment the data into sets, each generated by a single subsystem. As shown in the paper, exploiting ideas from Christoffel's functions allows for finding these polynomial approximations simply by performing SVDs. The parameters of each subsystem can then be identified from the segmented data using existing error-in-variables (EIV) techniques.  more » « less
Award ID(s):
1638234 1814631 1646121
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2019 IEEE 58th Conference on Decision and Control (CDC)
Page Range / eLocation ID:
3429 to 3434
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. This paper considers the problem of error in variables identification for switched affine models. Since it is well known that this problem is generically NP hard, several relaxations have been proposed in the literature. However, while these approaches work well for low dimensional systems with few subsystems, they scale poorly with both the number of subsystems and their memory. To address this difficulty, we propose a computationally efficient alternative, based on embedding the data in the manifold of positive semidefinite matrices, and using a manifold metric there to perform the identification. Our main result shows that, under dwell-time assumptions, the proposed algorithm is convergent, in the sense that it is guaranteed to identify the system for suitably low noise. In scenarios with larger noise levels, we provide experimental results showing that the proposed method outperforms existing ones. The paper concludes by illustrating these results with academic examples and a non-trivial application: action video segmentation. 
    more » « less
  2. Abstract

    This paper explores the use of Gaussian process regression for system identification in control engineering. It introduces two novel approaches that utilize the data from a measured global system error. The paper demonstrates these approaches by identifying a simulated system with three subsystems, a one degree of freedom mass with two antagonist muscles. The first approach uses this whole-system error data alone, achieving accuracy on the same order of magnitude as subsystem-specific data (9.28±0.87N vs. 6.96±0.32Nof total model errors). This is significant, as it shows that the same data set can be used to identify unique subsystems, as opposed to requiring a set of data descriptive of only a single subsystem. The second approach demonstrated in this paper mixes traditional subsystem-specific data with the whole system error data, achieving up to 98.71% model improvement.

    more » « less
  3. Avidan, S. (Ed.)
    We address the problem of segmenting moving rigid objects based on two-view image correspondences under a perspective camera model. While this is a well understood problem, existing methods scale poorly with the number of correspondences. In this paper we propose a fast segmentation algorithm that scales linearly with the number of correspondences and show that on benchmark datasets it offers the best trade-off between error and computational time: it is at least one order of magnitude faster than the best method (with comparable or better accuracy), with the ratio growing up to three orders of magnitude for larger number of correspondences. We approach the problem from an algebraic perspective by exploiting the fact that all points belonging to a given object lie in the same quadratic surface. The proposed method is based on a characterization of each surface in terms of the Christoffel polynomial associated with the probability that a given point belongs to the surface. This allows for efficiently segmenting points “one surface at a time” in O(number of points) 
    more » « less
  4. Summary

    The paper introduces a new local polynomial estimator and develops supporting asymptotic theory for nonparametric regression in the presence of covariate measurement error. We address the measurement error with Cook and Stefanski's simulation–extrapolation (SIMEX) algorithm. Our method improves on previous local polynomial estimators for this problem by using a bandwidth selection procedure that addresses SIMEX's particular estimation method and considers higher degree local polynomial estimators. We illustrate the accuracy of our asymptotic expressions with a Monte Carlo study, compare our method with other estimators with a second set of Monte Carlo simulations and apply our method to a data set from nutritional epidemiology. SIMEX was originally developed for parametric models. Although SIMEX is, in principle, applicable to nonparametric models, a serious problem arises with SIMEX in nonparametric situations. The problem is that smoothing parameter selectors that are developed for data without measurement error are no longer appropriate and can result in considerable undersmoothing. We believe that this is the first paper to address this difficulty.

    more » « less
  5. This paper proposes a data-driven framework to address the worst-case estimation problem for switched discrete-time linear systems based solely on the measured data (input & output) and an ℓ ∞ bound over the noise. We start with the problem of designing a worst-case optimal estimator for a single system and show that this problem can be recast as a rank minimization problem and efficiently solved using standard relaxations of rank. Then we extend these results to the switched case. Our main result shows that, when the mode variable is known, the problem can be solved proceeding in a similar manner. To address the case where the mode variable is unmeasurable, we impose the hybrid decoupling constraint(HDC) in order to reformulate the original problem as a polynomial optimization which can be reduced to a tractable convex optimization using moments-based techniques. 
    more » « less