ELEC 5650 - Mathematic Tools

"We have decided to call the entire field of control and communication theory, whether in the machine or in the animal, by the name Cybernetics, which we form from the Greek ... for steersman."

 -- by Norbert Wiener

This is the lecture notes for "ELEC 5650: Networked Sensing, Estimation and Control" in the 2024-25 Spring semester, delivered by Prof. Ling Shi at HKUST. In this session, we will cover essential mathematical tools and concepts from linear algebra, matrix theory, and system theory that are fundamental to networked sensing, estimation, and control.

1. Mathematic Tools <--
2. Estimation Theory
3. Kalman Filter
4. Linear Quadratic Regulator

Eigenvalues

$A\in {\mathbb{R}}^{n\times n}$, $\lambda$ can be solved by

$$\text{det}(\lambda I-A)=0$$$$\prod _{i=1}^n{\lambda }_i=\text{det}(A),\sum _{i=1}^n{\lambda }_i=\text{Tr}(A),A{v}_i={\lambda }_i{v}_i$$

Lemme

Let $A\in {\mathbb{R}}^{n\times m},B$ the non-zero eigenvalues of $AB$ and $BA$ are the same

Proof

$$\underset{P}{\underbrace{\left[\begin{array}{cc}I& 0\\ B& I\end{array}\right]}}\underset{P^{-1}}{\underbrace{\left[\begin{array}{cc}I& 0\\ -B& I\end{array}\right]}}=\left[\begin{array}{cc}I& 0\\ 0& I\end{array}\right]=I$$$$\underset{P}{\underbrace{\left[\begin{array}{cc}I& 0\\ B& I\end{array}\right]}}\left[\begin{array}{cc}AB& A\\ 0& 0\end{array}\right]\underset{P^{-1}}{\underbrace{\left[\begin{array}{cc}I& 0\\ -B& I\end{array}\right]}}=\left[\begin{array}{cc}0& A\\ 0& BA\end{array}\right]$$

Corollary

$$\text{Tr}(AB)=\text{Tr}(BA),\text{Tr}(ABC)=\text{Tr}(BCA)=\text{Tr}(CAB)$$$$\text{Tr}(ABC)\ne \text{Tr}(ACB)$$

Cholesky Decomposition

If $A⪰0$, then $\mathrm{\exists }$ a lower triangular matrix $L$ with real and non-negative diagonal entries such that

$$A=L{L}^T=\left[\begin{array}{ccc}\ddots & & 0\\ & \ddots & \\ \ddots & & \ddots \end{array}\right]\left[\begin{array}{ccc}\ddots & & \ddots \\ & \ddots & \\ 0& & \ddots \end{array}\right]$$$$A=\left[\begin{array}{cc}{a}_{11}& {\mathbf{a}}_{12}\\ {\mathbf{a}}_{21}& A_{22}\end{array}\right],L=\left[\begin{array}{cc}{l}_{11}& \mathbf{0}\\ {\mathbf{l}}_{21}& L_{22}\end{array}\right]$$$$\left[\begin{array}{cc}{a}_{11}& {\mathbf{a}}_{12}\\ {\mathbf{a}}_{21}& A_{22}\end{array}\right]=\left[\begin{array}{cc}{l}_{11}& \mathbf{0}\\ {\mathbf{l}}_{21}& L_{22}\end{array}\right]\left[\begin{array}{cc}{l}_{11}& {\mathbf{l}}_{21}^T\\ \mathbf{0}& L_{22}^T\end{array}\right]=\left[\begin{array}{cc}{l}_{11}^2& l_{11}{\mathbf{l}}_{21}^T\\ l_{11}{\mathbf{l}}_{21}& {\mathbf{l}}_{21}{\mathbf{l}}_{21}^T+L_{22}{L}_{22}^T\end{array}\right]$$$$l_{11}=\sqrt{a_{11}},{\mathbf{l}}_{21}=\frac{1}{l_{11}}{\mathbf{a}}_{21},L_{22}{L}_{22}^T=A_{22}-{\mathbf{l}}_{21}{\mathbf{l}}_{21}^T$$

Recursive Calculation !!!

Matrix Inversion Lemma

For matrix $A$ and $B$

$$(A+B{)}^{-1}=A^{-1}(I+B{A}^{-1}{)}^{-1}$$

For any matrix $A,B,C,D$ with compatible dimensions, $A,C$ nonsingular, then

$$\begin{array}{rl}(A+BCD{)}^{-1}& =[A(I+A^{-1}BCD){]}^{-1}\\ & =(I+A^{-1}BCD{)}^{-1}(I+A^{-1}BCD-A^{-1}BCD)A^{-1}\\ & =[I-(I+A^{-1}BCD{)}^{-1}{A}^{-1}BCD]A^{-1}\\ & =A^{-1}-(I+A^{-1}BCD{)}^{-1}{A}^{-1}BCD{A}^{-1}\\ & =A^{-1}-(I+A^{-1}BCD{A}^{-1}A{)}^{-1}{A}^{-1}BCD{A}^{-1}\\ & =A^{-1}-A^{-1}BCD{A}^{-1}(I+A{A}^{-1}BCD{A}^{-1}{)}^{-1}\\ & =A^{-1}-A^{-1}B[CD{A}^{-1}(I+BCD{A}^{-1}{)}^{-1}]\\ & =A^{-1}-A^{-1}B[(I+CD{A}^{-1}B{)}^{-1}CD{A}^{-1}]\\ & =A^{-1}-A^{-1}B[C{C}^{-1}+CD{A}^{-1}B{]}^{-1}CD{A}^{-1}\\ & =A^{-1}-A^{-1}B[C(C^{-1}+D{A}^{-1}B){]}^{-1}CD{A}^{-1}\\ & =A^{-1}-A^{-1}B(C+D{A}^{-1}B{)}^{-1}D{A}^{-1}\end{array}$$

Schur Complement

$$\left[\begin{array}{cc}\mathrm{A}& \mathrm{B}\\ \mathrm{C}& \mathrm{D}\end{array}\right]=\left[\begin{array}{cc}\mathrm{I}& 0\\ \mathrm{C}{\mathrm{A}}^{-1}& \mathrm{I}\end{array}\right]\left[\begin{array}{cc}\mathrm{A}& 0\\ 0& \mathrm{D}-\mathrm{C}{\mathrm{A}}^{-1}\mathrm{B}\end{array}\right]\left[\begin{array}{cc}\mathrm{I}& {\mathrm{A}}^{-1}\mathrm{B}\\ 0& \mathrm{I}\end{array}\right]$$$$\left[\begin{array}{cc}\mathrm{A}& \mathrm{B}\\ \mathrm{C}& \mathrm{D}\end{array}\right]=\left[\begin{array}{cc}\mathrm{I}& \mathrm{B}{\mathrm{D}}^{-1}\\ 0& \mathrm{I}\end{array}\right]\left[\begin{array}{cc}\mathrm{A}-\mathrm{B}{\mathrm{D}}^{-1}\mathrm{C}& 0\\ 0& \mathrm{D}\end{array}\right]\left[\begin{array}{cc}\mathrm{I}& 0\\ {\mathrm{D}}^{-1}\mathrm{C}& \mathrm{I}\end{array}\right]$$

Inner Product Space

$\mathbf{u},\mathbf{v}\in \mathcal{V}$, the inner product $⟨\mathbf{u},\mathbf{v}⟩$ satisfies

1. Linearity: $⟨{\alpha }_1{\mathbf{u}}_1+{\alpha }_2{\mathbf{u}}_2,\mathbf{v}⟩={\alpha }_1⟨{\mathbf{u}}_1,\mathbf{v}⟩+{\alpha }_2⟨{\mathbf{u}}_2,\mathbf{v}⟩$
2. Conjugate Symmetry: $⟨\mathbf{u},\mathbf{v}⟩=⟨\mathbf{v},\mathbf{u}{⟩}^{\ast }$, $(·{)}^{\ast }$ means transpose
3. Positive Definiteness: $||\mathbf{u}|{|}^2=⟨\mathbf{u},\mathbf{u}⟩=0\iff \mathbf{u}=0$

For two random variables $X,Y$, define $⟨X,Y⟩=E[X{Y}^T]$

Projection Theorem

Let $\mathcal{H}\in {\mathbb{R}}^m$ be a linear subspace of $\mathcal{S}\in {\mathbb{R}}^n,(m<n)$. For some vector $\mathbf{y}\in \mathcal{S}$, the projection of $\mathbf{y}$ onto $\mathcal{H}$ denoted as ${\hat{\mathbf{y}}}_{\mathcal{H}}$ is a uniyque element in $\mathcal{H}$, such that $\mathrm{\forall }\mathbf{x}\in \mathcal{H},⟨\mathbf{y}-{\hat{\mathbf{y}}}_{\mathcal{H}},\mathbf{x}⟩=0$, in other word $\mathbf{y}-{\hat{\mathbf{y}}}_{\mathcal{H}}\perp \mathbf{x}$.

Gram-Schmidt Process

Let $\{{\mathbf{v}}_1,{\mathbf{v}}_2,...{\mathbf{v}}_n\}$ be a set of linearly independent vectors in an inner product space VV. The Gram-Schmidt process constructs an orthonormal basis $\{{\mathbf{u}}_1,{\mathbf{u}}_2,\cdots ,{\mathbf{u}}_n\}$ for the subspace spanned by $\{{\mathbf{v}}_1,{\mathbf{v}}_2,...{\mathbf{v}}_n\}$ as follows:

$$\begin{array}{rl}{\mathbf{u}}_1& ={\mathbf{v}}_1\\ {\mathbf{u}}_2& ={\mathbf{v}}_2-{\text{proj}}_{{\mathbf{u}}_1}({\mathbf{v}}_2)\\ & ⋮\\ {\mathbf{u}}_k& ={\mathbf{v}}_k-\sum _{j=1}^{k-1}{\text{proj}}_{{\mathbf{u}}_j}({\mathbf{v}}_k)\end{array}{\mathbf{e}}_i=\frac{{\mathbf{u}}_i}{||{\mathbf{u}}_i||}$$

Autonomous System

A linear system $x_{k+1}=A{x}_k$ is said to be stable if

$$\mathrm{\forall }{x}_0,\underset{k\to \mathrm{\infty }}{lim}|x_k|=0$$

The system is stable if and only if

$$\underset{i}{max}|{\lambda }_i(A)|<1$$

Controllability

A linear system $x_{k+1}=A{x}_k+B{u}_k$ is said to be controllable if

$$\mathrm{\forall }{x}_0,x^{\ast },\mathrm{\exists }k>0,{\mathbf{u}}_k=[u_{k-1},\cdots ,u_1,u_0],\text{s.t.}{x}_k=x^{\ast }.$$

$(A,B)$ is controllable is equivalent to the following

1. $M_c=[B,AB,A^{2}B,\cdots ,A^{n-1}B]$ is full rank
2. $W_c=\sum _{k=0}^{n-1}{A}^{k}B{B}^T(A^T{)}^k$ is full rank
3. PBH test: $\mathrm{\forall }\lambda \in \mathbb{C},[A-\lambda I,B]$ is full rank

Assume $(A,B)$ is controllable, given $x_0,x^{\ast }$, find ${\mathbf{u}}_n$ such that $x_n=x^{\ast }$

$$\begin{array}{rl}{x}^{\ast }=x_n& =A{x}_{n-1}+B{u}_{n-1}\\ & =A(A{x}_{n-2}+B{u}_{n-2})+B{u}_{n-1}\\ & =A^2{x}_{n-2}+AB{u}_{n-2}+B{u}_{n-1}\\ & =A^n{x}_0+A^{n-1}B{u}_0+\cdots +AB{u}_{n-2}+B{u}_{n-1}\\ & =A^n{x}_0+M_c{\mathbf{u}}_n\end{array}$$$${\mathbf{u}}_n=M_c^T(M_c{M}_c^T{)}^{-1}(x^{\ast }-A^n{x}_0)$$

Observability

A linear system $x_{k+1}=A{x}_k,y_k=C{x}_k$ is said to be observable if $\mathrm{\forall }{x}_0,\mathrm{\exists }k>0$, such that $x_0$ can be computed from ${\mathbf{y}}_k=[y_0,y_1,\cdots ,y_{k-1}{]}^T$.

$(A,C)$ is observable is equivalent to the following

1. $M_o=\left[\begin{array}{c}C\\ CA\\ ⋮\\ C{A}^{n-1}\end{array}\right]$ is full rank
2. $W_o=\sum _{k=0}^{n-1}(A^k{)}^T{C}^{T}C{A}^k$ is full rank
3. PBH test: $\mathrm{\forall }\lambda \in \mathbb{C},\left[\begin{array}{c}A-\lambda I\\ C\end{array}\right]$ is full rank

Assume $(A,C)$ is observable, find $x_0$ from ${\mathbf{y}}_k$.

$$\begin{array}{rl}{y}_0& =C{x}_0\\ y_1& =C{x}_1=CA{x}_0\\ & ⋮\\ y_{n-1}& =C{A}^{n-1}{x}_0\end{array}\Rightarrow {\mathbf{y}}_n=\left[\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_{n-1}\end{array}\right]=\left[\begin{array}{c}C\\ CA\\ ⋮\\ C{A}^{n-1}\end{array}\right]x_0=M_o{x}_0$$$$x_0=(M_o^T{M}_o{)}^{-1}{M}_o^T{\mathbf{y}}_n$$

Controllability & Observability

$(A,C)$ is observable if and only if $(A^T,C^T)$ is controllable.