Selected topics in nonlinear system identification

1. Behavioral approach to system theory
2. A general framework for system identification
3. Linear time/parameter-varying systems
4. Static nonlinear systems
5. Representation and identification of nonlinear dynamic systems
   • Nonlinear auto-regressive-exogenous system identification (NARX)
   • Identification of autonomous Wiener systems
6. Data-driven control and signal processing

common theme: data modeling using matrix low-rank approximation

• Choose an individual mini-project.
• Work on the mini-project and prepare a written report (to be submitted by <2021-12-16 Thu>).
• You give a 15 minutes oral presentation for all course participants. The presentation is followed by 15 minutes questions, discussion, and feedback.

If you complete the mini-project and deliver a report of your work, you earn 10 points. The final mark (10–20) is determined by the quality of the report, oral presentation, and participation in the discussions.

We will often use the following concepts:

• behavioral definition of a dynamical system; properties of linearity, time-invariance, and final dimensionality;
• representations of linear time-invariant systems—convolution, transfer function, state space;
• links among representations—the realization problem.

For detailed notes, see:

• I. Markovsky, Exact and approximate modeling in the behavioral setting, Chapter 7
• J.-W. Polderman and J. Willems, Introduction to mathematical systems theory
• D. Luenberger, Introduction to dynamical systems: Theory, models and applications

Three types of problems are discussed in engineering mathematics:

• analysis problems, e.g., establishing stability, controllability, and observability properties of a system
• synthesis problems, e.g., design of an observer and controller for a given system, and
• identification problems, i.e., deriving a model of the system from observed trajectories.

This course focuses on the identification problem. Solving identification problems, however, requires knowledge of analysis. Also the product of identification—the model—is used in analysis and synthesis. There are deep connections and interactions among the three problem areas.

1. (Testing if a system is static linear)
   1. You are given a system as a black-box or executable code of a software function. You don't know what is within the black-box (or you can not see the code of the function) but you can do an arbitrary experiment with the system, i.e., you can observe its response. Assume that the variables are partitioned into inputs that you can choose and outputs that you observe.
      • What experiments would you do in order to find out whether the system is static linear?
      • How would you infer from the observations if the system is static linear?
      • What if the observations are corrupted by noise?
   2. Consider, now, the case when you are given (noisy) data \(\big\{w^{(1)},\ldots,w^{(N)}\big\}\) of \(N\) experiments with the system, i.e., you have no control over the experiment. How would you infer from the observations if the system is static linear?
2. (Testing if a system is linear time-invariant)
   1. The setup is the same as in problem 1: you are given a system as a black-box and you are allowed to do experiments in order to find out what type of system it is. In this case, the properties of interest are linearity and time-invariance, i.e., the system may be dynamic. What experiments would you do and how would you infer from the observations if the system is linear time-invariant? Consider separately the cases of exact and noisy data.
   2. Consider, now, the case when you are given trajectories \(\big\{w^{(1)},\ldots,w^{(N)}\big\}\) \[ w^{(i)} = \big( w^{(i)}(1),\ldots,w^{(i)}(T) \big) \] of the system, i.e., you have no control over the experiment. How would you infer from the observations if the system is linear time-invariant? Consider separately the cases of exact and noisy data.

1. (Exact modeling of an input/output static polynomial system, a.k.a., polynomial interpolation)

   Given a set of \(N\) data points \(\big\{w^{(1)},\ldots,w^{(N)}\big\} \subset \mathbb{R}^2\), where \(w^{(i)} = \big( u^{(i)}, y^{(i)}\big)\), find a polynomial static model \[\mathcal{B} = \{\, (u, y) \ | \ y = p_0u^0 + p_1 u^1 + \cdots + p_d u^d \,\} \] that fits the data exactly.

2. (Exact modeling of a static polynomial system in the behavioral setting)

   Given a set of \(N\) data points \(\big\{w^{(1)},\ldots,w^{(N)}\big\} \subset \mathbb{R}^2\), find a polynomial static model \[\mathcal{B} = \{\, w \ | \ p_{00} w_1^0 w_2^0 + p_{10} w_1^1 w_2^0 + p_{01} w_1^0 w_2^1 + p_{11} w_1^1 w_2^1 + p_{20} w_1^2 w_2^0 + p_{02} w_1^0 w_2^2 = 0 \,\}\] that fits the data exactly.

• linear differential/difference equation: the coefficients are functions of time
• state-space representation: the \(A,B,C,D\) matrices are functions of time
• autonomous case and state transition matrix \(\Phi(t_2, t_1) := A(t_2-1)A(t_2-1)\cdots A(t_1)\), for \(t_2>t_1\)
• driven response \[ x(t) = \Phi(t,0)x(0) + \underbrace{\begin{bmatrix} \Phi(t, 1)B(0) & \Phi(t, 2)B(1) & \cdots & B(t-1) \end{bmatrix}}_{\Gamma(t,0)} \begin{bmatrix} u(0)\\ u(1)\\ \vdots\\ u(t-1) \end{bmatrix} \]
• similarities and differences with the linear time-invariant case
  • the notions of poles and zeros are no longer relevant
  • stability analysis is more complicated (requires construction of a Lyapunov function)
  • linear time-varying systems are essentially nonparameteric: the number of parameters is \(O(T)\), where \(T\) is the number of data points

• when the coefficients variation is a periodic function, the number of parameters is fixed (independent of \(T\))
• a "lifting" technique reduces a linear periodically time-varying system to a linear time-invariant system

In order to capture the global behavior of a strongly nonlinear system, a single linear time-invariant model is not sufficient. If the system has a number of equilibrium points, it is reasonable to expect that "most of the time" the system is in the neighborhood of these points. More generally, we have a number of operating points (these can be equilibrium points as well as other points of interest) that represent well the global nonlinear behavior.

Linearization around the set of operating point leads to a set of linear time-invariant models (local models) that are "good" approximation of the original nonlinear system in the neighborhoods of the operating points. Such a system is called a multiple model system. Consider as an analogy piecewise linear approximation of a nonlinear function. The number and location of operating points is a design parameter in the construction of the approximation.

The approximation of a nonlinear system by a multiple model system can be done by switching from one local model to another depending on the state of the system or by "blending" all models, taking a linear combination of the local models. The first approach leads to a switch system, which is type of a hybrid system: continues/discrete-time dynamics of the local models and discrete-event dynamics of the switching rule. The second approach leads to a parameter dependent system.

./mm-approx.pdf The parameter is the vector of the coefficients in the linear combination. We will consider next the second approach.

The parameter of the multiple model system can be used for system approximation, estimation, and control. In the system approximation problem, given is a system or input/output data and the goal is to find the value of the parameter that minimizes the error between the multiple model system and the given system. In the estimation problem, a linear combination of a bank of local estimator is taken,

./mm-est.pdf and the parameters of the linear combination are optimized to achieve the smallest estimation error. Finally in the control problem the linear combination is formed from the control signals of local controllers

./mm-ctr.pdf and the objective is to select the optimal coefficients according to a specified control objective.

A Volterra series expansion is a non-parametric system description that has a universal approximation property. It generalizes the concept of the finite impulse response to the nonlinear case, in much the same way as a Taylor series expansion for function approximation. In simple terms, a Volterra series is nothing more than a polynomial function of time-shifted input signals. The output \(y\) of a system can hence be written as the finite sum \[y(t) =\sum_{i=1}^d \, \sum_{\tau_1} \sum_{\tau_2} \cdots \sum_{\tau_i} H_i(\tau_1, \tau_2, \ldots, \tau_i)\, u(t - \tau_1)\, u(t - \tau_2)\, \cdots u(t - \tau_i) \] where \(u\) denotes the input and \(H_i\) is the \(i\)th-order Volterra kernel. A major advantage is that estimating the Volterra kernel coefficients is a linear problem. However, the number of coefficients grows at least combinatorially with the system memory (number of lags) and order.