Fast Gauss Transforms based on a High Order Singular Value Decomposition for Nonlinear Filtering

We develop new algorithms to speed up the evaluation of the Chapman-Kolmogorov equation when using the marginal particle filter for nonlinear filtering. Evaluation of the Chapman Kolmogorov equation is equivalent to performing kernel denity estimation (KDE) and therefore has O(N2) complexity. The computational complexity of KDE can be reduced to O(N) using the fast Gauss transform (FGT), however the computational constant of the FGT grows exponentially with the dimension, thus making its use impractical in higher dimensions. We develop new FGT algorithms based on a high order singular value decomposition (HOSVD), which can work in high dimensions, and show that they are efficient for high dimensional nonlinear filtering problems.