ELEC 5650 - Estimation Theory

"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 explore fundamental concepts and techniques in estimation theory, including maximum a posteriori (MAP) estimation, minimum mean squared error (MMSE) estimation, maximum likelihood (ML) estimation, weighted least squares estimation, and linear minimum mean square error (LMMSE) estimation.

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

MAP (Maximum A Posterior) Estimation

$x$ is the parameter to be estimated

$$\hat{x}=\arg \underset{x}{max}\{\begin{array}{ll}f(x|y),& x\text{ is continuous}\\ p(x|y),& x\text{ is discrete}\end{array}$$

MMSE (Minimum Mean Squared Error) Estimation

$$\hat{x}=\arg \underset{\hat{x}}{min}E[e^{T}e|y]=\arg \underset{\hat{x}}{min}E[\hat{x}|y],e=x-\hat{x}$$$$\hat{x}=\int x\cdot f(x|y)\mathrm{d}x\text{or}\sum x\cdot p(x|y)$$

Proof:

$$\begin{array}{rl}E[e^{T}e]& =E[(x-\hat{x}{)}^T(x-\hat{x})|y]\\ & =E[x^{T}x|y]-2{\hat{x}}^{T}E[x|y]+{\hat{x}}^T\hat{x}\end{array}$$$$\frac{\partial }{\partial \hat{x}}(E[x^{T}x|y]-2{\hat{x}}^{T}E[x|y]+{\hat{x}}^T\hat{x})=0$$$$-2E[X|Y]+2\hat{x}=0$$$${\hat{x}}_{\text{MMSE}}=E[X|Y]$$

ML (Maximum Likelihood) Estimation

Non Bayesian. $p(y|x)$ is conditional probability and $p(y;x)$ is parameterized probability, $p(y|x)\nLeftrightarrow p(y;x)$.

Assume we have $n$ measurements $\mathcal{X}=(X_1,\cdots ,X_n)$, we use $p(\mathcal{X};\theta )$ to describe the joint probability of $\mathcal{X}$.

$${\hat{\theta }}_n=\arg \underset{\theta }{max}\{\begin{array}{ll}f(\mathcal{X};\theta ),& \theta \text{ is continuous}\\ p(\mathcal{X};\theta ),& \theta \text{ is discrete}\end{array}$$$$p(\mathcal{X};\theta )=\prod _{i=1}^{n}p(X_i;\theta )\iff \log p(\mathcal{X};\theta )=\sum _{i=1}^n\log p(X_i;\theta )$$

MAP & ML

$$\begin{array}{rl}{\hat{\theta }}_{\text{MAP}}& =\arg \underset{\theta }{max}p(\theta |x)=\arg \underset{\theta }{max}\frac{p(\theta )p(x|\theta )}{p(x)}p(\theta |x)=\arg \underset{\theta }{max}p(\theta )p(x|\theta )\\ {\hat{\theta }}_{\text{ML}}& =\arg \underset{\theta }{max}p(x;\theta )\end{array}$$

Weighted Least Square Estimation

$$\mathcal{E}(x)=||Ax-b|{|}_{\mathrm{\Sigma }}^2=x^T{A}^T{\mathrm{\Sigma }}^{-1}Ax-2b^T{\mathrm{\Sigma }}^{-1}Ax+b^T{\mathrm{\Sigma }}^{-1}b$$$$\mathrm{\nabla }\mathcal{E}=2A^T{\mathrm{\Sigma }}^{-1}Ax-2A^T{\mathrm{\Sigma }}^{-1}b$$$$\hat{x}=(A^T{\mathrm{\Sigma }}^{-1}A{)}^{-1}{A}^T{\mathrm{\Sigma }}^{-1}b$$

LMMSE (Linear Minimum Mean Square Error) Estimation

LMMSE estimation wants to find a linear estimator

$$\hat{x}=Ky+b$$

such that minimize the mean square error

$$\begin{array}{rl}\text{MSE}& =E[(x-\hat{x}{)}^T(x-\hat{x})]\\ & =E[x^{T}x]-2E[x^T\hat{x}]+E[{\hat{x}}^T\hat{x}]\\ & =E[x^{T}x]-2E[x^T(Ky+b)]+E[(Ky+b{)}^T(Ky+b)]\end{array}$$$$\frac{\partial \text{MSE}}{\partial b}=-2E[x]+2b+2KE[y]=0$$$$b={\mu }_x-K{\mu }_y$$$$\begin{array}{rl}\text{MSE}& =E[x^{T}x]-2E[x^T(Ky+b)]+E[(Ky+b{)}^T(Ky+b)]\\ & =E[x^{T}x]-2E[x^T(Ky+{\mu }_x-K{\mu }_y)]+E[(Ky+{\mu }_x-K{\mu }_y{)}^T(Ky+{\mu }_x-K{\mu }_y)]\\ & =E[x^{T}x]-2E[x^{T}Ky]-2{\mu }_x^T{\mu }_x+2{\mu }_x^{T}K{\mu }_y+E[y^T{K}^{T}Ky]+{\mu }_x^T{\mu }_x-2{\mu }_x^{T}K{\mu }_y+{\mu }_y^T{K}^{T}K{\mu }_y\end{array}$$$$\frac{\partial \text{MSE}}{\partial K}=-2{\mathrm{\Sigma }}_{xy}+2K{\mathrm{\Sigma }}_{yy}=0$$$$K={\mathrm{\Sigma }}_{xy}{\mathrm{\Sigma }}_{yy}^{-1}$$$$\hat{x}=Ky+b={\mu }_x+{\mathrm{\Sigma }}_{xy}{\mathrm{\Sigma }}_{yy}^{-1}(y-{\mu }_y)$$$${\mathrm{\Sigma }}_{\hat{x}\hat{x}}={\mathrm{\Sigma }}_{xx}-{\mathrm{\Sigma }}_{xy}{\mathrm{\Sigma }}_{yy}^{-1}{\mathrm{\Sigma }}_{yx}$$

Orthogonality Principle

$$\begin{array}{rl}⟨x-Ky-b,y⟩& =E[(x-Ky-b)y^T]\\ & =E[x{y}^T]-KE[y{y}^T]-bE[y^T]\\ & ={\mathrm{\Sigma }}_{xy}+{\mu }_x{\mu }_y^T-K({\mathrm{\Sigma }}_{yy}+{\mu }_y{\mu }_y^T)-({\mu }_x-K{\mu }_y){\mu }_y^T\\ & ={\mathrm{\Sigma }}_{xy}-({\mathrm{\Sigma }}_{xy}{\mathrm{\Sigma }}_{yy}^{-1}){\mathrm{\Sigma }}_{yy}\\ & =0\end{array}$$$$x-(Ky+b)\perp y$$

This shows that error $e=x-\hat{x}$ is independent of observation $y$.

Innovation Process

Calculating ${\mathrm{\Sigma }}_{yy}$ consumes lots of time, however, if ${\mathrm{\Sigma }}_{yy}$ is diagonal the thing becomes easy. By G.S. process, we can obtain orthogonality vectors ${\overrightarrow{e}}_1,\cdots {\overrightarrow{e}}_k$ and the lower triangular transform matrix $F$ from ${\overrightarrow{y}}_1,\cdots ,{\overrightarrow{y}}_k$. The key idea of ​​orthogonal projection is to decompose the observation vector $y_k$ into a part related to the past prediction value, which can be predicted by $y_1,\cdots y_{k-1}$, and a new part that is irrelevant to the past prediction value (innovation).

$$e=Fy$$

Then the covariance can be calculated by

$${\mathrm{\Sigma }}_{ee}=F{\mathrm{\Sigma }}_{yy}{F}^T,{\mathrm{\Sigma }}_{ex}=F{\mathrm{\Sigma }}_{yx}$$$$K_e={\mathrm{\Sigma }}_{ex}{\mathrm{\Sigma }}_{ee}^{-1}=F{\mathrm{\Sigma }}_{yx}(F^T{)}^{-1}{\mathrm{\Sigma }}_{yy}^{-1}{F}^{-1}$$

Although $K_e$ is not equal to $K$, it serves as the Kalman gain in the transformed or projected space defined by the matrix $F$.

For new coming ${\overrightarrow{y}}_{t+1}$ we can find ${\overrightarrow{e}}^{k+1}$ by G.S. process

$$\begin{array}{rl}{e}_{k+1}& =y_{k+1}-{\hat{y}}_{k+1|k}\\ & =y_{k+1}-\text{proj}(y_{k+1};{\mathcal{E}}_k)\\ & =y_{k+1}-\sum _{i=1}^k\frac{⟨y_{k+1},e_i⟩}{⟨e_i,e_i⟩}\cdot e_i\end{array}$$

It satisfies

$$⟨e_{k+1},y_i⟩=E[e_{k+1}{y}_i^T]=0,\mathrm{\forall }i\in [1,k]$$

To estimate $x$ at $k+1$

$$\begin{array}{rl}{\hat{x}}_{k+1}& =\text{proj}(x_{k+1};{\mathcal{E}}_{k+1})\\ & =\sum _{i=1}^{k+1}\frac{⟨x_{k+1},e_i⟩}{⟨e_i,e_i⟩}\cdot e_i\\ & =\sum _{i=1}^k\frac{⟨x_{k+1},e_i⟩}{⟨e_i,e_i⟩}\cdot e_{+}\frac{⟨x_{k+1},e_{k+1}⟩}{⟨e_{k+1},e_{k+1}⟩}\cdot e_{k+1}\\ & =\sum _{i=1}^k\frac{⟨x_k,e_i⟩}{⟨e_i,e_i⟩}\cdot e_i+\frac{⟨x_{k+1},e_{k+1}⟩}{⟨e_{k+1},e_{k+1}⟩}\cdot e_{k+1}\\ & ={\hat{x}}_k+\frac{⟨x_{k+1},e_{k+1}⟩}{⟨e_{k+1},e_{k+1}⟩}\cdot e_{k+1}\end{array}$$