2.4a Discrete-Time System Identification

Discrete-Time System ID Process

For a discrete-time LTI model ${\vec{x}}_d[i+1]$, the system identification algorithm is as follows:

1. Let $D:=\left[\begin{array}{cc}{\vec{x}}_d[i_1{]}^T& {\vec{u}}_d[i_1{]}^T\\ ⋮& ⋮\\ {\vec{x}}_d[i_l{]}^T& {\vec{u}}_d[i_l{]}^T\end{array}\right]\in {\mathbb{R}}^{l\times (n+m)}$ and $S:=\left[\begin{array}{c}{\vec{x}}_d[i_1+1{]}^T\\ ⋮\\ {\vec{x}}_d[i_l+1{]}^T\end{array}\right]\in {\mathbb{R}}^{l\times n}.$
2. Compute the OLS $\hat{P}:=(D^{T}D{)}^{-1}{D}^{T}S\in {\mathbb{R}}^{l\times n}.$
3. Extract $\left[\begin{array}{c}{\hat{A}}_d^T\\ {\hat{B}}_d^T\end{array}\right]:=\hat{P}$.

Intuition

We start with our well-known discrete-time ${\vec{x}}_d[i+1]=A_d{\vec{x}}_d[i]+B_d{\vec{u}}_d[i]$. We can rewrite this equation in matrix-vector form as
${\vec{x}}_d[i+1]=\left[\begin{array}{cc}{A}_d& B_d\end{array}\right]\left[\begin{array}{c}{\vec{x}}_d[i]\\ {\vec{u}}_d[i]\end{array}\right].$
We can make our life easier by transposing the equation to place our data points in rows that are vertically stacked. This yields the inner product
${\vec{x}}_d[i+1{]}^T=\left[\begin{array}{cc}{\vec{x}}_d[i{]}^T& {\vec{u}}_d[i{]}^T\end{array}\right]\left[\begin{array}{c}{A}_d^T\\ B_d^T\end{array}\right].$
We do this so we do not have to transform our least squares later on. Since the dimensions of $A$ are $n\times n$ and the dimensions of $B$ are $n\times m$, we can ensure that there are exactly $n$ columns and $n+m$ rows in $P$ by taking its transpose. We now want to define our stacked matrices for timesteps $i_1,\dots ,i_l$. Therefore, $P:=\left[\begin{array}{c}{A}_d^T\\ B_d^T\end{array}\right]$, whereas $D:=\left[\begin{array}{cc}{\vec{x}}_d[i_1{]}^T& {\vec{u}}_d[i_1{]}^T\\ ⋮& ⋮\\ {\vec{x}}_d[i_l{]}^T& {\vec{u}}_d[i_l{]}^T\end{array}\right]\in {\mathbb{R}}^{l\times (n+m)}$ and $S:=\left[\begin{array}{c}{\vec{x}}_d[i_1+1{]}^T\\ ⋮\\ {\vec{x}}_d[i_l+1{]}^T\end{array}\right]\in {\mathbb{R}}^{l\times n}$. We end up with a very familiar equation in $DP=S$.

So what’s up with the dimensionality? Matrix $D$ has the dimensions $l\times (n+m)$ since there are $l$ timesteps, representing the $l$ rows in $D$, and $n+m$ columns since the state vector $\vec{x}:\mathbb{N}\to {\mathbb{R}}^n$ has $n$ elements, whereas the vector of control inputs $\vec{u}:\mathbb{N}\to {\mathbb{R}}^m$ has $m$ elements. Therefore, each row in $D$ has a combined of $n+m$ elements. We can use the same reasoning for $S$ since the state vector will always contain $n$ elements.

We can now use least squares optimization to find a matrix $\hat{P}$ that minimizes the coefficient matrices $A_d$ and $B_d$. We do so using
$\hat{P}:=(D^{T}D{)}^{-1}{D}^{T}S.$
Note that OLS only works when $D$ is invertible $⟺$ is full column rank $⟺$ $\mathrm{Rank}(D)=n+m$ $⟺$ has $n+m$ linearly independent columns. Here are the two other possibilities:

• If $Rank(D)<n+m$ $⟹$ least squares is not possible since $D$ is not invertible.
• If $D$ has $>n+m$ columns AND is full column rank $⟹$ there is more than one solution for $\hat{P}$.