Efficient Spectral Differentiation in Grid-Based Continuous State Estimation
J. Matoušek, J. Duník, M. Brandner · 2024
Read Efficient Spectral Differentiation in Grid-Based Continuous State Estimation by J. Matoušek, J. Duník, M. Brandner (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07240.txt.
Introduction
Jakub Matousek, Jindrich Dunik, and Marek Brandner wrote a 2024 study on estimating the state of systems that change continuously under randomness. Their setting solves a key equation for probability distributions on a grid. They bring in spectral differentiation, a technique known for very fast convergence on smooth functions.
Standard grid methods improve slowly as points are added, which forces large grids and heavy computation. The spectral approach reaches good accuracy with fewer points, even with a moving grid and zero values at the edges. For readers in filtering and control, the gain is a more accurate estimate at lower computing cost.
Catalog record
| CREATOR | J. Matoušek, J. Duník, M. Brandner |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-07240
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Spectral Differentiation in Grid-Based Continuous State Estimation J. Matoušek, J. Duník, M. Brandner Abstract This paper deals with the state estimation of stochastic models with continuous dynamics. The aim is to incorporate spectral differentiation methods into the solution to the Fokker-Planck equation in grid-based state estimation routine, while taking into account the specifics of the field, such as probability density function (PDF) features, moving grid, zero boundary conditions, etc. The spectral methods, in general, achieve very fast convergence rate of 𝒪 ( c N ) ( O < c < 1 ) \mathcal{O}(c^{N})(O<c<1) for analytical functions such as the probability density function, where N N is the number of grid points. This is significantly better than the standard finite difference method (or midpoint rule used in discrete estimation) typically used in grid-based filter design with convergence rate 𝒪 ( 1 N 2 ) \mathcal{O}(\frac{1}{N^{2}}) . As consequence, the proposed spectral method based filter provides better state estimation accuracy with lower number of grid points, and thus, with lower computational complexity. This paper has been accepted for publication in 2024 27th International Conference on Information Fusion (FUSION). Please cite the paper as: J. Matoušek, J. Duník and M. Brandner, ”Efficient Spectral Differentiation in Grid-Based Continuous State Estimation,” 2024 27th International Conference on Information Fusion (FUSION), Venice, Italy, 2024, pp. 1-8, doi: 10.23919/FUSION59988.2024.10706533.. I Introduction The goal of this paper is to introduce the usage of spectral methods to state estimation, and to show how the spectral methods can benefit from the efficient grid-based point mass filter formulation proposed in [ 1 , 2 , 3 ] . The continuous state estimation starts with a model described by the stochastic differential equation (SDE), and stochastic algebraic equation \displaystyle d\mathbf{x}(t) \displaystyle=\mathbf{A}\mathbf{x}(t)dt+\mathbf{Q}d\mathbf{w}(t) (1) \displaystyle\mathbf{z}_{t_{k}} \displaystyle=\mathbf{h}(\mathbf{x}_{t_{k}})+\mathbf{v}_{t_{k}}, (2) where t denotes the time, the vector \mathbf{x}(t)\in\mathbb{R}^{n_{x}} represents the unknown state of the system, \mathbf{z}_{t_{k}}\in\mathbb{R}^{n_{z}} the known measurement, and t_{k}=t_{0},t_{1},\ldots,T is a discrete time instant, when the measurement arrived. The matrix \mathbf{A}\in\mathbb{R}\\ ^{n_{x}\times n_{x}} and the function \mathbf{h}(\cdot)\mathrel{\mathop{\ordinarycolon}}\mathbb{R}^{n_{x}}\rightarrow\mathbb{R}^{n_{z}} are known, \mathbf{Q}\in\mathbb{R}^{n_{x}\times n_{x}} is a known diffusion coefficient, \mathbf{w}(t) is the state noise modelled by the Brownian motion with the normally distributed increment with the covariance matrix E[d\mathbf{w}(t)(d\mathbf{w}(t))^{T}]=\mathbf{I}_{n_{x}}dt , and \mathbf{v}_{t_{k}} is the measurement noise with the known PDF p(\mathbf{v}_{t_{k}}) . The state and measurement noise random variables are supposed to be independent mutually and of the known initial state \mathbf{x}_{0} with the known PDF p(\mathbf{x}_{0}) . The aim of the state estimation (or filtering) is to compute the PDF of the state \mathbf{x}(t) conditioned on all past measurements \mathbf{z}^{t_{k}}=[\mathbf{z}_{t_{0}},\mathbf{z}_{t_{1}},\ldots,\mathbf{z}_{t_{k}}] . The sought conditional PDF can be either filtering p(\mathbf{x}(t_{k})|\mathbf{z}^{t_{k}}) , which is computed in the filter measurement update step, or predictive p(\mathbf{x}(t)|\mathbf{z}^{t_{k}}),t>t_{k} , which is computed in the filter time update step. I-A Measurement Update The solution to the measurement update providing the filtering PDF is given by the Bayes’ rule \displaystyle p(\mathbf{x}_{t_{k}}|\mathbf{z}^{t_{k}}) \displaystyle=\tfrac{p(\mathbf{x}_{t_{k}},\mathbf{z}_{t_{k}}|\mathbf{z}^{t_{k-1}})}{p(\mathbf{z}_{t_{k}}|\mathbf{z}^{t_{k-1}})}=\tfrac{p(\mathbf{x}_{t_{k}}|\mathbf{z}^{t_{k-1}})p(\mathbf{z}_{t_{k}}|\mathbf{x}_{t_{k}})}{p(\mathbf{z}_{t_{k}}|\mathbf{z}^{t_{k-1}})}, (3) where p(\mathbf{x}_{t_{k}}|\mathbf{z}^{t_{k-1}}) is the predictive 1 1 1 The predictive PDF p(\mathbf{x}_{t_{0}}|\mathbf{z}^{t_{-1}}) is equal to the initial one p(\mathbf{x}_{0}) . PDF, p(\mathbf{z}_{t_{k}}|\mathbf{x}_{t_{k}}) is the measurement PDF obtained from ( 2 ), and the normalization coefficient is given by p(\mathbf{z}_{t_{k}}|\mathbf{z}^{t_{k-1}})=\int p(\mathbf{x}_{t_{k}}|\mathbf{z}^{t_{k-1}})p(\mathbf{z}_{t_{k}}|\mathbf{x}_{t_{k}})d\mathbf{x}_{t_{k}} . I-B Time Update The solution to the time update, w.r.t. the SDE ( 1 ), is given by the Fokker-Planck equation (FPE) describing the time evolution of the filtering PDF to predictive PDF \displaystyle\frac{{\partial}p_{t}(\mathbf{x}|\mathbf{z}^{t_{k}})}{{\partial}t} \displaystyle=-\nabla\cdot\left(\mathbf{A}\mathbf{x}p_{t}(\mathbf{x}|\mathbf{z}^{t_{k}})\right) \displaystyle+\frac{1}{2}\nabla\cdot\left(\mathbf{Q}\nabla p_{t}(\mathbf{x}|\mathbf{z}^{t_{k}})\right), (4) where t\in(t_{k},t_{k+1}) , the operator \nabla denotes the gradient w.r.t. \mathbf{x} , and \nabla\cdot stands for the divergence. Further, when possible, the conditional PDF is written simply as p_{t}(\mathbf{x}) . In ( 4 ), the first right-hand side term is named hyperbolic and it describes the advection of the PDF tied to the state dynamics. The second term is named parabolic and it describes the diffusion caused by the state noise. The standard FPE ( 4 ) holds for the Gaussian state noise only [ 4 ] . II FPE Efficient Solution Prerequisites The FPE is exactly solvable for a narrow set of the SDEs ( 1 ). Within the set, it is possible to find the linear SDEs, for which the solution to the FPE ( 4 ) leads to the prediction step of the Kalman-Bucy filter [ 5 ] , or SDEs of special form that are solved by e.g. Beneš, Daum, and Wong and Yau filters [ 6 ] . For remaining SDEs, the FPE is not exactly solvable and need to be solved either using model linearisation or numerically on a grid of points [ 7 , 5 , 8 ] . Before the numerical solution is discussed, the FPE is rewritten into suitable form allowing simple application of fast frequency-based numerical methods. The changes are twofold, first, a diagonalisation of matrix \mathbf{Q} is performed, second, an advection is solved using Lagrangian approach. II-A Diagonalization First step that greatly reduces the complexity of the advanced efficient numerical algorithms is a diagonalisation of the \mathbf{Q} in ( 1 ) and subsequently in ( 4 ). Instead of solving the FPE for the model with non-diagonal \mathbf{Q} , an alternative diagonalized FPE can be solved \displaystyle{\frac{{\partial}p_{t}(\bar{\mathbf{x}})}{{\partial}t}} \displaystyle=-{\nabla_{\bar{\mathbf{x}}}\cdot\left(\bar{\mathbf{A}}\bar{\mathbf{x}}\ p_{t}(\bar{\mathbf{x}})\right)} \displaystyle+\frac{1}{2}\nabla_{\bar{\mathbf{x}}}\cdot\left(\nabla_{\bar{\mathbf{x}}}^{T}p_{t}(\bar{\mathbf{x}})\right), (5) where the following substitution was done, \mathbf{Q}=\mathbf{G}\mathbf{G}^{T} , \bar{\mathbf{x}}=\mathbf{G}^{-1}\mathbf{x} , \bar{\mathbf{A}}=\mathbf{G}^{-1}\mathbf{A}\mathbf{G} , and \nabla_{\bar{\mathbf{x}}}=[\frac{\partial}{\partial\bar{\mathbf{x}}(1)}...\frac{\partial}{\partial\bar{\mathbf{x}}(n_{x})}] . Then the estimation algorithm is run in the state space \bar{\mathbf{x}} . If the first two moments (i.e. the estimate and its uncertainty) for the original FPE solution are needed they can be calculated as \mathsf{E}[\mathbf{x}]=\mathbf{G}\mathsf{E}[\bar{\mathbf{x}}] , \mathsf{cov}[\mathbf{x}]=\mathbf{G}\ \mathsf{cov}[\bar{\mathbf{x}}]\ \mathbf{G}^{-1} . For simplicity it is further assumed that \mathbf{Q} is diagonal from the very beginning, which is true for many models such as the model in the numerical illustration section of this paper. II-B Advection solution The second step applies a Lagrangian approach to solve the advection part of the FPE \nabla p_{t}(\mathbf{x})\left(\mathbf{A}\mathbf{x}\right) ( 4 ). This part is problematic because the product of p_{t}(\mathbf{x}) and \mathbf{A}\mathbf{x} depends on the actual state, which prevents efficient solution in frequency domain. This part can be disposed of by using - in a sense - a Lagrangian approach [ 9 , pp. 7] . Let every point of the state-space \mathbf{x}\in\mathbb{R}^{n_{x}} be moving according to 2 2 2 Movement of the PDF caused by the advection is compensated by the movement of the observer. Imagine you are one particle of water in the river, in a simplified way, from your point of perspective, the water around you is not moving. \dot{\mathbf{x}}=\mathbf{A}\mathbf{x} . Then, the FPE advection part ( 4 ) taking into account the movement reads [ 10 ] \displaystyle\nabla\cdot\left(\mathbf{A}\mathbf{x}\ p_{t}(\mathbf{x})\right)=\nabla p_{t}(\mathbf{x})\ \dot{\mathbf{x}}+\operatorname{trace}(\mathbf{A})p_{t}(\mathbf{x}), (6) where \operatorname{trace}(\mathbf{A}) is the trace of the matrix \mathbf{A} . The FPE to be solved is then \displaystyle{\frac{{\partial}p_{t}(\mathbf{x})}{{\partial}\mathbf{v}}} \displaystyle=-\operatorname{trace}(\mathbf{A})p_{t}(\mathbf{x}) \displaystyle+\frac{1}{2}\nabla\cdot\left(\mathbf{Q}\left(\nabla^{T}p_{t}(\mathbf{x})\right)\right), (7) where \mathbf{v}=\begin{bmatrix}\bf{\dot{x}}&1\end{bmatrix} , and \displaystyle{\frac{{\partial}p_{t}(\mathbf{x})}{{\partial}\mathbf{v}}}=\mathbf{v}\begin{bmatrix}\nabla p_{t}(\mathbf{x})\ ,&\ \frac{{\partial}p_{t}(\mathbf{x})}{{\partial}t}\end{bmatrix}^{T}. (8) Compared to the FPE ( 4 ), where the PDF is differentiated w.r.t. the time t , in ( 7 ) it is differentiated w.r.t. observer, which is moving in time. As will be seen, the remaining advection term \operatorname{trace}(\mathbf{A})p_{t}(\mathbf{x}) can be easily handled. III Grid-Based Estimation In this section a grid-based estimation for continuous dynamics is briefly introduced, starting with usually used approximation to the PDFs. After that two grid-based estimation methods are presented; (i) standard basic finite difference method