# How to derive an expression for the optimal importance distribution?

I'm trying to answer the exercise 7.6 letter b of this book:

https://users.aalto.fi/~ssarkka/pub/cup_book_online_20131111.pdf

page 133 but I'm having some problems in understanding the question because there is no explanation in the book about how to derive the optimal importance distribution... just references to that ( page 125 ) but the problem is that the references are books that I don't have access to them. If someone can put me on the right direction, it will be very helpful. This is the question:

Update 1: Base on Atul Ingle answer, I believe the answer is something like this:

These images are taken from:

https://www.amazon.com/Beyond-Kalman-Filter-Applications-Hardcover/dp/158053631X

# Hint

Well, it looks like the question tells you what the optimal importance distribution is! It's $p(\mathbf x_k | \mathbf x_{k-1},\mathbf y_{1:k})$. So the problem boils down to computing a closed form expression for this conditional density using the given state space model.

# More Hints

The transition model tells you $p(\mathbf x_k | \mathbf x_{k-1})$ is a multivariate Gaussian. The observation model tells you $p(y_k|\mathbf x_{k})$ is another multivariate Gaussian.

1. Can you write these multivariate Gaussians in closed form?
2. Can you express $p(\mathbf x_k | \mathbf x_{k-1},\mathbf y_{1:k})$ in terms of $p(\mathbf x_k | \mathbf x_{k-1})$ and $p(y_k|\mathbf x_{k})$?

# Almost complete solution

\begin{eqnarray} p(\mathbf x_k | \mathbf x_{k-1}, \mathbf y_{1:k}) &=& p(\mathbf x_k | \mathbf x_{k-1}, \mathbf y_{1:k-1}, y_k) \label{1}\tag{1} \\ &=& p(\mathbf x_k|\mathbf x_{k-1}, y_k) \label{2} \tag{2}\\ &=& \frac{p(y_k|\mathbf x_k,\mathbf x_{k-1}) p(\mathbf x_k | \mathbf x_{k-1})}{p(y_k | \mathbf x_{k-1})} \label{3} \tag{3} \\ &=& \frac{p(y_k|\mathbf x_k)p(\mathbf x_k | \mathbf x_{k-1})}{p(y_k | \mathbf x_{k-1})} \label{4}\tag{4} \end{eqnarray} where (\ref{1}) is just another way of writing $\mathbf y_{1:k}$, (\ref{2}) follows from Markov property (Eq. 4.2 of the book), (\ref{3}) follows from Bayes' theorem and (\ref{4}) follows from conditional independence of measurements (Eq. 4.3 of the book).

Using the model given in Eq. (7.49) in the original question we have $$p(y_k|\mathbf x_k) \sim N((1 \;\; 0) \mathbf x_k,10^2) \label{5}\tag{5}$$ and $$p(\mathbf x_{k}|\mathbf{x}_{k-1}) = N\left(\left(\begin{array}{} 1 & 1\\ 0 & 1 \end{array} \right)\mathbf x_{k-1}, \left(\begin{array}{} 1/10^2 & 0\\ 0 & 1 \end{array} \right)\right). \label{6}\tag{6}$$ To compute $p(y_k | \mathbf x_{k-1})$ we express $y_k$ in terms of $\mathbf x_{k-1}$ as follows: \begin{eqnarray} y_k &=& (1\;\;0)\mathbf x_{k} + r_k \\ &=& (1\;\;0) \left(\begin{array}{} 1 & 1\\ 0 & 1 \end{array} \right)\mathbf x_{k-1} + (1\;\;0)\mathbf q_{k-1} + r_k \\ &=& (1 \;\; 1) \mathbf x_{k-1} + (1\;\;0) \mathbf q_{k-1} + r_k \end{eqnarray} which implies that $$p(y_k | \mathbf x_{k-1}) \sim N\left((1 \;\; 1) \mathbf x_{k-1}, \frac{1}{10^2}+10^2\right).\label{7}\tag{7}$$ Finally you should use Wikipedia or Eq. (A.1) from Appendix A.1 of the book for the expression for a multivariate Gaussian density function.

Time for grunge work. Plug (\ref{5}), (\ref{6}) and (\ref{7}) into (\ref{4}) and finish with some algebra.

• Thanks! I misread the question. I just don't understand why you have to write the multivariate Gaussian in closed form and express the optimal importance distribution in the terms of the multivariates. By the way, I updated my question with the possible answer I found in a book. I'm trying to figure it out how they got from equation 3.34 to equation 3.35. – andrestoga Nov 3 '17 at 17:15
• @andrestoga see updated answer with more details. as for eq. 3.34 and 3.35 in your screenshots, those terms are just the exponents in the multivariate Gaussian. – Atul Ingle Nov 4 '17 at 17:13