On the Convergence Analysis of Yau-Yau Nonlinear Filtering Algorithm: from a Probabilistic Perspective

Filtering is an important subject in the field of modern control theory, and has wide applications in various scenarios such as signal processing [3][4], weather forecast [5][6], aerospace industrial [7][8] and so on. The core objective of filtering problem is pursuing accurate estimation or prediction to the state of a given stochastic dynamical system based on a series of noisy observations [9][10]. For practical implementations, it is also necessary that the estimation or prediction to the state can be computed in a recursive and real-time manner.

In the filtering problems we consider in this paper, the evolution of state processes, as well as the noisy observations, is governed by the following system of stochastic differential equations,

in the filtered probability space $(\Omega,\mathcal{F},\{\mathcal{F}_{t}\}_{t=0}^{T},P)$, where $T>0$ is a fixed termination; $X=\{X_{t}:0\leq t\leq T\}\subset\mathbb{R}^{d}$ is the state process we would like to track; $Y=\{Y_{t}:0\leq t\leq T\}\subset\mathbb{R}^{d}$ is the noisy observation to the state process $X$; $\{V_{t}:0\leq t\leq T\}$ and $\{W_{t}:0\leq t\leq T\}$ are mutually independent, $\mathcal{F}_{t}$-adapted, $d$-dimensional standard Brownian motions; $\xi$ is a $\mathbb{R}^{d}$-valued random variable with probability density function $\sigma_{0}(x)$, which is independent of $V_{t}$ and $W_{t}$; $f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, $g:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d\times d}$ and $h:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ are sufficiently smooth vector- or matrix- valued functions.

Mathematically, for a given test function $\varphi:\mathbb{R}^{d}\rightarrow\mathbb{R}$, the optimal estimation of $\varphi(X_{t})$ based on the historical observations up to time $t$ is the conditional expectation $E[\varphi(X_{t})|\mathcal{Y}_{t}]$, where $\mathcal{Y}_{t}:=\sigma\{Y_{s}:0\leq s\leq t\}$ the $\sigma$-algebra generated by historical observations. Such estimation is ‘optimal’ in the sense that,

Therefore, the main task of filtering problem can be specified into finding efficient algorithms to numerically compute the conditional expectation $E[\varphi(X_{t})|\mathcal{Y}_{t}]$, or equivalently, the conditional probability distribution $P[X_{t}\in\cdot|\mathcal{Y}_{t}]$ or the conditional probability density function (if exists).

With some regularity assumptions on the coefficients $f,g,h$ in the system (1), the conditional probability measure $P[X_{t}\in\cdot|\mathcal{Y}_{t}]$ is absolutely continuous with respect to the Lebesgue measure in $\mathbb{R}^{d}$, and the conditional probability density function $\sigma(t,x)$, (without considering a normalization constant), can be described by the well-known DMZ equation, which is named after three researchers: T. E. Duncan [11], R. E. Mortensen [12] and M. Zakai [13], who derived the equation independently in the late 1960s.

The DMZ equation satisfied by the unnormalized conditional probability density function $\sigma(t,x)$ is a second-order stochastic partial differential equation, and does not possess an explicit-form solution in general. In their works [1] and [2], the third author and his collaborator propose a two-stage algorithm framework to compute the solution of the DMZ equation numerically in a memoryless and real-time manner. Later on, this algorithm is referred to as Yau-Yau algorithm.

The basic idea of Yau-Yau algorithm is that the heavy computation burden of numerically solving a Kolmogorov-type partial differential equation (PDE) can be done off-line, and in the meanwhile, the on-line procedure only consists of the basic computations such as multiplication by the exponential function of the observations. In the framework of Yau-Yau algorithm, various kinds of methods to solving the Kolmogorov-type PDEs, such as spectral methods [14][15], proper orthogonal decomposition [16], tensor training [17], etc, are proposed and applied in specific examples of nonlinear filtering problems. Numerical results in the previous works mentioned above show that Yau-Yau algorithm can provide accurate and real-time estimations to the state process of very general nonlinear filtering problems in low and medium-high dimensional space.

In the original works [1] and [2], the convergence analysis of Yau-Yau algorithm is conducted pathwisely. For regular paths of observations with some boundedness conditions, it is proved that the numerical solution provided by Yau-Yau algorithm will converge to the exact solution of DMZ equation both pointwisely and in $L^{2}$-sense, as the size of time-discretization step tends to zero, while in the works on the practical implementations of Yau-Yau algorithm, such as [14] and [15], the convergence analysis mainly focuses on the capability of numerical methods to approximate the solution of Kolmogorov-type PDEs arising in Yau-Yau algorithms.

In this paper, we will revisit the convergence analysis of Yau-Yau algorithm from a probabilistic perspective. Instead of considering the convergence results pathwisely, we prove that the solution of Yau-Yau algorithm will converge to the exact solution of DMZ equation in expectation, and also, after the normalization procedure, the approximated solution to the filtering problem provided by Yau-Yau algorithm will converge to the conditional expectation $E[\varphi(X_{t})|\mathcal{Y}_{t}]$.

The advantage of this probabilistic perspective is that for a theoretically rigorous convergence analysis, instead of regularity assumptions on observation paths, we only need to make assumptions on the coefficients $f,g,h$ of the filtering system (1) and the test function $\varphi$, which are verifiable off-line in advance for practitioners. In the meanwhile, as shown in the main results of this paper in Section 3, those assumptions we need are in fact quite general, and it is straightforward to check that the most commonly used test functions $\varphi(x)=x_{i}$ and $\varphi(x)=x_{i}x_{j}$, $x=(x_{1},\cdots,x_{d})^{\top}\in\mathbb{R}^{d}$, corresponding to the conditional mean and conditional covariance matrix, as well as the linear Gaussian systems (with $f(x)=Fx$, $g(x)\equiv\Gamma$, and $h(x)=Hx$, $F,H,\Gamma\in\mathbb{R}^{d\times d}$), satisfy all the assumptions.

Moreover, to the best of the authors’ knowledge, most of the theoretical analysis of PDE-based filtering algorithm mainly deals with convergence results with respect to the DMZ equation. In such probabilistic perspective we consider here in this paper, however, it is natural and convenient to make a step forward and discuss the approximation capability of Yau-Yau algorithm to the normalized conditional expectation and conditional probability distribution. In this way, we will provide a thorough convergence analysis of the Yau-Yau algorithm for filtering problems.

The organization of this paper is as follows. Section 2 serves as preliminaries, in which we will summarize some basic concepts of filtering problems and the main procedure of Yau-Yau algorithm. The main theorems in this paper will be stated in Section 3, together with a sketch of the proofs. In the next four sections, we will provide the detailed proofs of the lemmas and theorems. We first focus on the properties of the exact solution of DMZ equation in Section 4 and Section 5, and then deal with the approximated solutions given by Yau-Yau algorithm in Section 6 and Section 7. Finally, Section 8 is a conclusion.

In this section, we would like to briefly summarize the theory of nonlinear filtering, including the change-of-measure approach to deriving the DMZ equation, as well as the main idea and procedures of Yau-Yau algorithm.

In the change-of-measure approach to deriving the DMZ equation corresponding to the filtering system (1), we first introduce a series of reference probability measures $\{\tilde{P}_{t}:0\leq t\leq T\}$, absolutely continuous to the original probability measure $P$ with Radon derivatives given by

According to Girsanov’s theorem, as long as the process $\{Z_{t}:0\leq t\leq T\}$ defined in (3) is a martingale, then under the reference probability measure $\tilde{P}_{T}$, the observation process $\{Y_{t}:0\leq t\leq T\}$ is a standard Brownian motion which is independent of the state process $X$.

We also introduce the process $\{\tilde{Z}_{t}:0\leq t\leq T\}$, $\tilde{Z}_{t}=Z_{t}^{-1}$, to be the inverse of $Z_{t}$, which is also a Radon derivative and can be expressed by the stochastic integral with respect to $Y$ as follows:

Therefore, for any $\mathcal{F}_{t}$-measurable, integrable random variable $U\in\mathcal{F}_{t}$, its expectation with respect to measure $P$ can be computed by

where $\tilde{E}$ means the expectation is taken under the probability measure $\tilde{P}_{T}$.

As an extension of Bayesian formula in the context of continuous-time stochastic processes, the following Kallianpur-Striebel formula allows us to express and calculate the solution of filtering problem, $E[\varphi(X_{t})|\mathcal{Y}_{t}]$, by a ratio of conditional expectations under $\tilde{P}_{T}$:

Since the denominator $\tilde{E}\left[\tilde{Z}_{t}|\mathcal{Y}_{t}\right]$ in (6) is independent of the test function $\varphi$, people often refer to the nominator, $\tilde{E}\left[\tilde{Z}_{t}\varphi(X_{t})|\mathcal{Y}_{t}\right]$, as the unnormalized conditional expectation of $\varphi(X_{t})$. The corresponding measure-valued stochastic process $\{\rho_{t}:0\leq t\leq T\}$ defined by

is also referred to as unnormalized conditional probability measure, and we also denote the unnormalized conditional expectation by

With sufficient regularity assumptions on the coefficients $f,g,h$ and test function $\varphi$, the evolution of $\rho_{t}(\varphi)$ is governed by the following well-known DMZ equation:

where

is a second-order elliptic operator with $a(x):=(a^{ij}(x))_{1\leq i,j\leq d}=g(x)g(x)^{\top}$.

If the stochastic measures $\rho_{t}$, $t\in[0,T]$, are almost surely absolutely continuous to the Lebesgue measure in $\mathbb{R}^{d}$, and the density functions (or the Radon derivatives) $\sigma(t,x)$, as well as the derivatives of $\sigma(t,x)$, is square-integrable, then $\sigma(t,x)$ is the solution to the following equation, (which is also referred to as the DMZ equation):

which is a second-order stochastic partial differential equation with

the adjoint operator of $\mathcal{L}$.

In this case, the unnormalized conditional expectation $\rho_{t}(\varphi)$ can be expressed as

and the (normalized) conditional expectation $E\left[\varphi(X_{t})|\mathcal{Y}_{t}\right]$ can be calculated by

Because the solution of (11) does not have a closed form for general nonlinear filtering systems, efficient numerical methods must be proposed, so that we can get a good approximation to the conditional expectation $E[\varphi(X_{t})|\mathcal{Y}_{t}]$ through the equation (14).

At the beginning of this century, the third author and his collaborator proposed a two-stage algorithm to numerically solve the DMZ equation (11) in a memoryless and real-time manner, which is often referred to as Yau-Yau algorithm. Here, we would like to briefly introduce the basic idea and main procedure of this algorithm.

Firstly, if we consider the exponential transformation

then the function $w(t,x)$ satisfies the robust DMZ equation

where the stochastic differential terms in the original DMZ equation (11) are eliminated and

are stochastic functions that depend on the specific value of observation $Y_{t}$ at time $t$.

Instead of solving equation (11) directly, we will mainly focus on the robust DMZ equation (16), especially the corresponding initial-boundary value (IBV) problems in a closed ball $B_{R}:=\{x\in\mathbb{R}^{d}:|x|\leq R\}$, with a given radius $R>0$.

where $\mathscr{S}_{R}(x)$ is a $C^{\infty}$ function supported in $B_{R}$ and satisfies

and $0\leq\mathscr{S}_{R}(x)\leq 1$ for $R-\frac{1}{R}\leq|x|\leq R$, so that the initial value is compatible with the boundary condition in (18). And from now on, we would like to drop the subscript, $R$, in the notation $u_{R}(t,x)$ for the simplicity of notations, and use $u(t,x)$ to denote the solution to the IBV problem (19).

Let $0=\tau_{0}<\tau_{1}<\cdots<\tau_{K}=T$ be a uniform partition of the time interval $[0,T]$, with $\tau_{k}-\tau_{k-1}=\delta=\frac{T}{K}$, $k=1,\cdots,K$. On each time interval $[\tau_{k-1},\tau_{k}]$, consider the IBV problem of the following parabolic equation

with the value of coefficients $F(t,x)$ and $J(t,x)$ frozen at the left point $t=\tau_{k-1}$ and initial value $u_{0}(\tau_{0},x):=\sigma_{0}(x)$.

With another exponential transformation given by

the newly-constructed function $\tilde{u}_{k}$ satisfies

After the two exponential transformations (15) and (21), the function we would like to use to approximate the unnormalized conditional probability density function $\sigma(\tau_{k},x)$ at time $t=\tau_{k}$ is given by

and the value for approximating the conditional expectation $E[\varphi(X_{t})|\mathcal{Y}_{t}]$ is given by

The main idea of the Yau-Yau algorithm is that the problem of solving the DMZ equation satisfied by the unnormalized probability density function $\sigma(t,x)$ can be separated into two parts. The computationally expensive part of solving the (IBV) problems of parabolic equation (22) can be done off-line, because it is a deterministic Kolmogorov-type PDE which is independent of observations, and at least, the corresponding semi-group, $\{S_{t}:t\in[0,T]\}$, can be analyzed and approximated off-line. When new observation comes, the remaining task is only about calculating exponential transformations and numerical integrals. The framework of Yau-Yau algorithm is shown in Algorithm 1.

In the next section, we will give a mathematically rigorous interpretation of the approximation results (23) and (24) from a probabilistic perspective. In particular, we only need assumptions on the test function and the coefficients of the filtering systems to derive the convergence result. These assumptions are also easy to verify off-line before the observations come, and therefore, this convergence analysis will provide a guidance for practitioners to determine the parameters in the implementations of Yau-Yau algorithm for practical use.

In this section, we would like to state the main result in this paper and also provide a sketch of the proof.

Firstly, besides the smoothness and regularity requirements which guarantee the existence of conditional expectation and the existence of the solution to the DMZ equation, let us further introduce four particular assumptions on the coefficients of the system, the initial distribution and the test function.

For the state equation in the filtering system (1), the drift term $f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ is assumed to be Lipschitz, and the the diffusion term $g:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d\times d}$, together with $a(x)=g(x)g(x)^{\top}$, is assumed to have bounded partial derivatives up to second order, i.e.,

Assumption (A1) guarantees that the state equation of (1) has a strong solution in $[0,T]$, and especially, the state equation for linear filter satisfies this assumption.

Also, in order to conduct energy estimations for the (stochastic) partial differential equations, we would like to assume that the diffusion term in the state equation is nondegenerate, in the sense that

For the initial distribution $\sigma_{0}$, we would like to assume that it is smooth enough and possesses finite high-order moments:

Assumption (A3) is satisfied by commonly-used light-tailed distributions such as Gaussian distributions. In fact, in the following convergence analysis, we only require Assumption (A3) to hold for sufficiently large $n\geq 1$, rather than for all $n\in\mathbb{N}$.

Finally, it is assumed that the test function $\varphi:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is at most polynomial growth:

which is satisfied by most of the commonly-used test functions, such as those correspond to the conditional mean and covariance matrix.

Based on the above assumptions (A1) to (A4), the main result in this paper is stated as follows:

Here in this section, we provide a sketch of the proof of Theorem 25, in which the main idea of the proof is illustrated. The detailed proofs of those key estimations here will be given in order in the next four sections.