An Novel Algorithm to Solve the Nonlinear Filtering Problems in Real-Time

This dissertation provides an affirmative answer to the well-known half century old engineering question raised by Office of Naval Research: “How can one solve nonlinear filtering (NLF) problems in real time without memory, if enough computational resources are provided?” Instead of the prestigious Kalman filter (KF) and its derivatives to estimate the mean and the covariance matrix of the states, we resort to solving the Duncan-Mortensen-Zakai (DMZ) equation, which is satisfied by the un-normalized probability density function of the states. In this dissertation, we develop a novel algorithm, which is applicable to the most general settings of the NLF problems and keeps two of the most important properties of KF: real-time and memory-less. Briefly speaking, in our algorithm, we split the approximation of the conditional density function into two parts: one part could be pre-computed before any on-line experiments ran (so-called off-line computation); the other part has to be sychronized the real-time data with the pre-computed data (so-called on- line computation). More precisely, the off-line computation solves a forward Kolmogorov equation (FKE) with the initial conditions, which are chosen to be a complete base functions in square-integrable function space, while the on-line part computes the projection of the conditional density function at each time step onto the basis, and then synchronize them with the off-line data to obtain the conditional density function at the next time step. First, we validate our algorithm theoretically, by estimating the convergence rate with respect to the sampling frequency. Second, we tackle some difficulties in the implementation of our algorithm and apply it to some 1-D benchmark NLF problems. Compared with the two most widely used methods nowadays, extended Kalman filter and particle filters, our algorithm surpasses both of them in the real-time manner with comparable accuracy. Last, when we investigate the application of our algorithm to the high-dimensional state NLF problems, we combine the sparse grid algorithm with the Hermite spectral method to serve as the off-line solver of FKE. The convergence rate is investigated both theoretically and numerically.