mae283_lec04.tex

\mainmatter%
\setcounter{page}{1}

\lectureseries[\course]{\course}

\auth[\lecAuth]{Lecturer: \lecAuth\\ Scribe: \scribe}
\date{October 6, 2009}

\setaddress%

% the following hack starts the lecture numbering at 4
\setcounter{lecture}{3}
\setcounter{chapter}{3}

\lecture{Stochastic Systems and Dynamics}

\section{Stationary Stochastic Signals}
This lecture closely follows Chapter 2 of Ljung, specifically \S2.1-2.3, which deal with stationary stochastic signals.% chktex 8
These systems can be modeled as in Figure~\ref{fig:04system}, where $u(t)$ is deterministic and $v(t)$ is noise.
When $v(t)=0$ it implies that $y(t)$ is noise-free --- this is a boring topic to study and very rarely occurs in practice.
The system is more interesting when $v(t)\neq 0$ and then $y(t)$ is a sum of deterministic and stochastic signals.
This means that the output can be found as $y(t)=w(t)+v(t)$, where $w(t)=G_0(q)u(t)$ is unknown.
Recall that $G_0(q)$ is not a function but is a time-shift operator so that $w(t)$ is not a product of two terms.
Typically, we assume that the noise has zero-mean such that

\begin{equation*}
E\{v(t)\}=0 \Rightarrow E\{y(t)\}=w(t)
\end{equation*}

This is referred to as the ``time-varying'' or ``non-stationary'' mean value.
\begin{figure}[ht!]
\centering
\includegraphics[width=.3\textwidth]{images/04system}
\caption{Block diagram of system with input, output and noise signals.}%
\label{fig:04system}
\end{figure}

The expectation operator yields the average of the stochastic portion of the output.
What we want to find is a linear operator that will give the average of the deterministic part as well.
For that we use the extended expectation operator.

\begin{equation*}
\bar{E}\{y(t)\} = \lim_{N\to\infty}\frac{1}{N}\sum_{t=1}^N E\{y(t)\}
\end{equation*}

When the expectation operator is used it takes the stochastic portion of the output and makes it deterministic, giving just a scalar value.
The extended expectation operator averages the output, $y(t)$, over time to give a scalar as well.

The time-shifted input, $w(t)=G_0(q)u(t)$, is deterministic with

\begin{equation*}
\bar{E}\{w(t)\} = \lim_{N\to\infty}\frac{1}{N}\sum_{t=1}^N E\{w(t)\}
\end{equation*}

and we typically assume $\bar{E}\{w(t)\}=0$.

\begin{example}
Given a deterministic signal, $u(t)$, as shown in Figure~\ref{fig:04inputSignal} we can say that

\begin{equation*}
\lim_{N\to\infty}\frac{1}{N}\sum_{t=1}^N E\{u(t)\} = 0
\end{equation*}

This is shown as a block diagram in Figure~\ref{fig:04detSignal} and makes it clear that $\lim_{N\to\infty}\frac{1}{N}\sum_{t=1}^N w(t)=0$ since $u(t)=0$ and the system is linear.
$\lozenge$
\end{example}
\begin{figure}[ht!]
\centering
\includegraphics[width=.5\textwidth]{images/04inputSignal}
\caption{Example of an input signal that tends to have zero-mean over long enough time periods.}%
\label{fig:04inputSignal}
\end{figure}

\begin{figure}[ht!]
\centering
\includegraphics[width=.3\textwidth]{images/04detSignal}
\caption{Block diagram of system with deterministic, zero-mean input signal.}%
\label{fig:04detSignal}
\end{figure}

\begin{definition}{Extended Expectation Operator}

\begin{equation*}
\bar{E}\{y(t)\}=\lim_{N\to\infty}\frac{1}{N}\sum_{t=1}^N E\{y(t)\}
\end{equation*}

Typically, we assume that $E\{y(t)\}=0$ if $\bar{E}\{u(t)\}=0$ and $G_0(q)$ is BIBO stable.
If the system is not BIBO stable then we get Brownian motion resulting in random walk.
\end{definition}

\begin{definition}{Quasi-stationary Signal}%
\label{def:quasistationary}
A process $u(t)$ is quasi-stationary if there exists some $c_1, c_2 \in\mathbb{R}$ such that
\begin{itemize}
\item $\bar{E}\{u(t)\} < c_1~\forall t$
\item $\bar{E}\{u(t)u(t-\tau)\} = R_u(\tau) < c_2~\forall \tau$
\end{itemize}
The first inequality indicates that the mean of the process must be bounded.
The second inequality means that $u(t)$ correlated with itself and time-shifted a small amount should also be bounded and is known as the ``auto-covariance'' function.
\end{definition}

\begin{definition}{Covariance and Spectral Functions}

These are formal definitions and cannot actually be computed because they require an infinite number of samples.
Later we will learn how to estimate their values given a finite number of samples.
\begin{itemize}
\item Auto-covariance function \\
$R_y(\tau) \triangleq \bar{E}\{y(t)y(t-\tau)\}, \qquad |\tau|\in\mathbb{N}$
\item Cross-covariance function \\
$R_{yu}(\tau) \triangleq \bar{E}\{y(t)u(t-\tau)\}, \qquad |\tau|\in\mathbb{N}$
\item Auto-spectral density function \\
$\Phi_u(\w) \triangleq \sum_{\tau=-\infty}^\infty R_y(\tau)e^{-j\w\tau}$ \\
This is the discrete-time Fourier transform (DTFT) of the auto-covariance function.
\item Cross-spectral density function \\
$\Phi_{yu}(\w) \triangleq \sum_{\tau=-\infty}^\infty R_y u(\tau)e^{-j\w\tau}$ \\
This is the DTFT of the cross-covariance function.
\end{itemize}
Note that $\w\in\mathbb{R}$ and $|\tau|\in\mathbb{N}$.
To get from the spectral density functions to the covariance functions use the inverse Fourier transform:

\begin{equation*}
R_y(\tau) = \frac{1}{2\pi}\int_{\w=-\pi}^\pi \Phi_y(\w)e^{j\w\tau}d\w
\end{equation*}

\end{definition}

\section{White Noise}
White noise, $e(t)$, is a zero-mean signal and is satisfied by the following properties:
\begin{itemize}
\item $\bar{E}\{e(t)\}=0$
\item $\bar{E}\{e(t)e(t-\tau)\} = R_e(\tau) = \begin{cases} \lambda>0, & \tau=0 \\ 0, & |\tau|\neq 0 \end{cases}$ \\
The case when $\tau=0$ is known as the variance of the signal.
\item $\Phi_e(\w) = \sum_{\tau=-\infty}^\infty \lambda\delta_d(t)e^{-j\w t} = \lambda e^{-j\w 0} = \lambda$ \\
We only need to evaluate the $\delta$-function at time $t=0$.
See Figure~\ref{fig:04deltaFn}.
\item $\bar{E}\{e^2(t)\} = R_e(0) = \lambda = \frac{1}{2\pi}\int_{\w=-\pi}^\pi\Phi_u(\w)e^{j\w\tau}d\w = \frac{1}{2\pi} \int_{\w=-\pi}^\pi\Phi_u(\w)d\w$ \\
where the exponential goes to one because $\tau=0$.
This can be thought of as the surface under the auto-spectral density function between $[-\pi,\pi]$ and is equal to the variance of the signal.
\end{itemize}

\begin{figure}[ht!]
\centering
\includegraphics[width=.4\textwidth]{images/04deltaFn}
\caption{A delta function at $t=0$ with magnitude of $\lambda$.}%
\label{fig:04deltaFn}
\end{figure}

\section{Uncorrelated Signals}
Consider two signals $u(t)$ and $v(t)$ that are not necessarily input and output.
We say that $u\perp y$ or ``u is uncorrelated with y'' if $R_{yu}(\tau)=0~\forall \tau$.

\subsection{Application}
Consider the system $y(t)=G_0(q)u(t)+v(t)$.
The cross-correlation function is found as
\begin{align*}
\bar{E}\{y(t)u(t-\tau)\} &= \bar{E}\{G_0(q)u(t)u(t-\tau)\} + \bar{E}\{v(t)u(t-\tau)\} \\
&= \bar{E}\{G_0(q)u(t)u(t-\tau)\} \\
&\Rightarrow R_{yu}(\tau) = G_0(q)R_u(\tau)
\end{align*}
The term $\bar{E}\{v(t)u(t-\tau)\} = 0$ based on the assumption that since $u(t)$ is a designed and deterministic signal then it is highly unlikely that the input and the noise are correlated.

\section{Effects of Dynamics/Filtering}
\subsection{Cross-covariance Function}
Let $\{u(t)\}$ be white noise, $y(t)=G_0(q)u(t)+v(t)$, $u\perp v$ and $G_0(q)=\sum_{k=0}^\infty g(k)q^{-k}$.
Note that $\{u(t)\}$ is white but known.
How do we find $R_{yu}(\tau)$?

Start with
\begin{align*}
R_{yu}(\tau) &= G_0(q)R_u(\tau) \\
R_u(\tau) &= \begin{cases} \lambda, & \tau=0 \\ 0, & \tau\neq 0 \end{cases} = \lambda\delta_d(\tau)
\end{align*}
Substituting the second equation into the first is equivalent to getting the impulse response of the system as described by the coefficients $g(k)$ so that

\begin{equation*}
R_{yu}(\tau) = \lambda g(\tau)
\end{equation*}

\begin{example}
Let $G_0(q)$ be a mass-spring-damper system with low amounts of damping.
Given an impulse as input the output signal will oscillate at some frequency while dying down due to the damping.
See Figure~\ref{fig:04dimSine}.
$\lozenge$
\end{example}
\begin{figure}[ht!]
\centering
\includegraphics[width=.5\textwidth]{images/04dimSine}
\caption{A diminishing sine wave representing the impulse response in a mass-spring-damper system with low amounts of damping.}%
\label{fig:04dimSine}
\end{figure}

\subsection{Auto-spectral Density Function}
\begin{example}
Let $\{e(t)\}$ be white noise where $E\{e(t)\}=0$, $v(t)=H_0(q)e(t)$.
How do we find $\Phi_v(\w)$?
\begin{align*}
\Phi_v(\w) &= \mathcal{F}\{R_v(\tau)\} \\
&= \mathcal{F}\{E\{v(t)v(t-\tau)\}\} \\
&= \mathcal{F}\{E\{H_0(q)e(t)H_0(q)e(t-\tau)\}\} \\
&= \vectornorm{H_0(e^{j\w})}^2\Phi_e(\w) \\
&= \vectornorm{H_0(e^{j\w})}^2\cdot\lambda
\end{align*}
The final equality uses the fact that $\Phi_e(\w)=\lambda$ because the noise is white.
This shows that applying the filter $H_0(q)$ changes the shape of the input of white noise.
After the filter the white noise contains much lower frequencies so the noise, $v(t)$, is colored.
See Figure~\ref{fig:04filteredNoise}.
$\lozenge$
\end{example}
\begin{figure}[ht!]
\centering
\includegraphics[width=.7\textwidth]{images/04filteredNoise}
\caption{Effect of filtering white noise.}%
\label{fig:04filteredNoise}
\end{figure}

\subsection{Cross-spectral Density Function}
\begin{example}
How do we find $\Phi_{yu}(\w)$?

\begin{equation*}
\Phi_{yu}(\w) = \mathcal{F}\{R_{yu}(\tau)\} = \lambda G_0(e^{j\w})
\end{equation*}

The Fourier transform of an implulse response yields the transfer function.
This allows us to back out the Markov parameters.
$\lozenge$
\end{example}

\begin{example}
Given $y(t)=w(t)+v(t)$ we get
\begin{align*}
\Phi_y(\w) &= \lambda\vectornorm{G_0(e^{j\w})}^2 + \Phi_v(\w) \\
\Phi_v(\w) &= \Phi_y(\w) - \vectornorm{\Phi_{yu}(\w)}
\end{align*}
$\Phi_v(\w)$ is the noise that was acting on the system and can now be identified.
$\lozenge$
\end{example}

\section{Effect of Periodogram}
This is covered in Ljung, pages 31-33.% chktex 8
\begin{definition}{Periodogram}

Essentially, the periodogram $\hat{\Phi}_y(\w)$ is a cheap way of estimating the spectrum, or the frequency contents, of a signal.
\begin{align*}
\Phi_y(\w) &= \mathcal{F}\{R_u(\tau)\} \\
\hat{\Phi}_y(\w) &= Y(\w)Y^\ast(\w) \\
Y(\w) &= \sum_{t=1}^N y(t)e^{-j\w t}, |t|\in\mathbb{N} \\
\hat{\Phi}_y(\w) &= |Y(\w)|^2 = Y(\w)Y^\ast(\w)
\end{align*}
Recall that the Fourier transform of the convolution operator is the multiplication operator.
\end{definition}

\begin{theorem}
This is Theorem 2.1 from Ljung on page 31.
If the output is noise-free such that $y(t)=G_0(q)u(t)$ then
\begin{align*}
Y_N(\w) &= \frac{1}{\sqrt{N}}\sum_{t=1}^N y(t)e^{-j\w t} \\
U_N(\w) &= \frac{1}{\sqrt{N}}\sum_{t=1}^N u(t)e^{-j\w t} \\
Y_N(\w) &= G_0(e^{j\w})U_N(\w) + R_N(\w)
\end{align*}
The first two equalities are discrete Fourier transforms.
$Y_N(\w)$ and $U_N(\w)$ are finite Fourier transforms and $R_N(\w)$ is an infinite Fourier transform.
This leads to

\begin{equation*}
|R_N(\w)| \leq 2\cdot C_w\cdot \frac{C_g}{\sqrt{N}}
\end{equation*}

where $|u(t)|<C_w~\forall t$, $C_g=\sum_{k=0}^\infty k|g_k|<\infty$ if the system is BIBO stable.
\end{theorem}
Note that $R_N(\w)$ is the noise due to the inital and end conditions that can be bounded.
This noise arises because when we use the Fourier transform we automatically make the assumption that the signal is periodic even when they are not periodic as discussed in \S\ref{sec:impliedperiodicity}.