Convex Relaxations for Robust Identification of Hybrid Models

Necmiye Ozay
Ph.D. Dissertation, Electrical and Computer Engineering, Northeastern University, Boston, MA, USA, 2010.

  In order to extract useful information from a data set, it is necessary to understand the underlying model. This dissertation addresses two of the main challenges in identification of such models. First, the data is often generated by multiple, unknown number of sources; that is, the underlying model is usually a mixture model or hybrid model. This requires solving the identification and data association problems simultaneously. Second, the data is usually corrupted by noise necessitating robust identification schemes. Motivated by these challenges we consider the problem of robust identification of hybrid models that interpolate the data within a given noise bound. In particular, for static data we try to fit affine subspace arrangements or more generally a mixture of algebraic surfaces to the data; and for dynamic data we try to infer the underlying switched affine dynamical system. Clearly, as stated, these problems admit infinitely many solutions. For instance, one can always find a trivial hybrid model with as many submodels/subspaces as the number of data points (i.e. one submodel/subspace per data point). In order to regularize the problem, we define suitable a priori model sets and objective functions that seek “simple” models. Although this leads to generically NP-Hard problems, we develop computationally efficient algorithms based on convex relaxations.
  Additionally, we discuss a related problem: robust model (in)validation for affine hybrid systems. Before a given system description, obtained either from first principles or an identification step, can be used to design controllers, it must be validated using additional experimental data. In this dissertation, we show that the invalidation problem for switched affine systems can be solved within a similar framework by exploiting a combination of elements from convex analysis and the classical theory of moments.
  Finally, the effectiveness of the proposed methods are illustrated using both simulations and several non-trivial applications in computer vision such as video and dynamic texture segmentation, two-view motion segmentation and human activity analysis. In all cases the proposed methods significantly outperform existing approaches both in terms of accuracy and resilience to noise.

pdf