Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

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 dwelltime 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 nontrivial application: action video segmentation.more » « less

Systems consisting of interacting agents are prevalent in the world, ranging from dynamical systems in physics to complex biological networks. To build systems which can interact robustly in the real world, it is thus important to be able to infer the precise interactions governing such systems. Existing approaches typically dis cover such interactions by explicitly modeling the feedforward dynamics of the trajectories. In this work, we propose Neural Interaction Inference with Potentials (NIIP) as an alternative approach to discover such interactions that enables greater flexibility in trajectory modeling: it discovers a set of relational potentials, represented as energy functions, which when minimized reconstruct the original trajectory. NIIP assigns low energy to the subset of trajectories which respect the relational constraints observed. We illustrate that with these representations NIIP displays unique capabilities in testtime. First, it allows trajectory manipulation, such as interchanging interaction types across separately trained models, as well as trajectory forecasting. Additionally, it allows adding external handcrafted potentials at testtime. Finally, NIIP enables the detection of outofdistribution samples and anomalies without explicit training.more » « less

Matni, N ; Morari, M ; Pappas, G.J. (Ed.)One of the longterm objectives of Machine Learning is to endow machines with the capacity of structuring and interpreting the world as we do. This is particularly challenging in scenes involving time series, such as video sequences, since seemingly different data can correspond to the same underlying dynamics. Recent approaches seek to decompose video sequences into their composing objects, attributes and dynamics in a selfsupervised fashion, thus simplifying the task of learning suitable features that can be used to analyze each component. While existing methods can successfully disentangle dynamics from other components, there have been relatively few efforts in learning parsimonious representations of these underlying dynamics. In this paper, motivated by recent advances in nonlinear identification, we propose a method to decompose a video into moving objects, their attributes and the dynamic modes of their trajectories. We model video dynamics as the output of a Koopman operator to be learned from the available data. In this context, the dynamic information contained in the scene is encapsulated in the eigenvalues and eigenvectors of the Koopman operator, providing an interpretable and parsimonious representation. We show that such decomposition can be used for instance to perform video analytics, predict future frames or generate synthetic video. We test our framework in a variety of datasets that encompass different dynamic scenarios, while illustrating the novel features that emerge from our dynamic modes decomposition: Video dynamics interpretation and user manipulation at testtime. We successfully forecast challenging object trajectories from pixels, achieving competitive performance while drawing useful insights.more » « less

Systems consisting of interacting agents are prevalent in the world, ranging from dynamical systems in physics to complex biological networks. To build systems which can interact robustly in the real world, it is thus important to be able to infer the precise interactions governing such systems. Existing approaches typically discover such interactions by explicitly modeling the feedforward dynamics of the trajectories. In this work, we propose Neural Interaction Inference with Potentials (NIIP) as an alternative approach to discover such interactions that enables greater flexibility in trajectory modeling: it discovers a set of relational potentials, represented as energy functions, which when minimized reconstruct the original trajectory. NIIP assigns low energy to the subset of trajectories which respect the relational constraints observed. We illustrate that with these representations NIIP displays unique capabilities in testtime. First, it allows trajectory manipulation, such as interchanging interaction types across separately trained models, as well as trajectory forecasting. Additionally, it allows adding external handcrafted potentials at testtime. Finally, NIIP enables the detection of outofdistribution samples and anomalies without explicit training.more » « less

Recently, there has been renewed interest in datadriven control, that is, the design of controllers directly from observed data. In the case of linear timeinvariant (LTI) systems, several approaches have been proposed that lead to tractable optimization problems. On the other hand, the case of nonlinear dynamics is considerably less developed, with existing approaches limited to at most rational dynamics and requiring the solution to a computationally expensive Sum of Squares (SoS) optimization. Since SoS problems typically scale combinatorially with the size of the problem, these approaches are limited to relatively low order systems. In this paper, we propose an alternative, based on the use of statedependent representations. This idea allows for synthesizing datadriven controllers by solving at each time step an online optimization problem whose complexity is comparable to the LTI case. Further, the proposed approach is not limited to rational dynamics. The main result of the paper shows that the feasibility of this online optimization problem guarantees that the proposed controller renders the origin a globally asymptotically stable equilibrium point of the closedloop system. These results are illustrated with some simple examples. The paper concludes by briefly discussing the prospects for adding performance criteria.more » « less

Semidefinite programs (SDP) are a staple of today’s systems theory, with applications ranging from robust control to systems identification. However, current stateofthe art solution methods have poor scaling properties, and thus are limited to relatively moderate size problems. Recently, several approximations have been proposed where the original SDP is relaxed to a sequence of lower complexity problems (such as linear programs (LPs) or second order cone programs (SOCPs)). While successful in many cases, there is no guarantee that these relaxations converge to the global optimum of the original program. Indeed, examples exists where these relaxations "get stuck" at suboptimal solutions. To circumvent this difficulty in this paper we propose an algorithm to solve SDPs based on solving a sequence of LPs or SOCPs, guaranteed to converge in a finite number of steps to an εsuboptimal solution of the original problem. We further provide a bound on the number of steps required, as a function of ε and the problem data.more » « less

Koopman operators provide tractable means of learning linear approximations of nonlinear dynamics. Many approaches have been proposed to find these operators, typically based upon approximations using an apriori fixed class of models. However, choosing appropriate models and bounding the approximation error is far from trivial. Motivated by these difficulties, in this paper we propose an optimization based approach to learning Koopman operators from data. Our results show that the Koopman operator, the associated Hilbert space of observables and a suitable dictionary can be obtained by solving two rankconstrained semidefinite programs (SDP). While in principle these problems are NPhard, the use of standard relaxations of rank leads to convex SDPs.more » « less

This paper proposes a datadriven framework to address the worstcase estimation problem for switched discretetime linear systems based solely on the measured data (input & output) and an ℓ ∞ bound over the noise. We start with the problem of designing a worstcase 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 momentsbased techniques.more » « less