# Full text of "Hermite spectral method to 1D forward Kolmogorov equation and its application to nonlinear filtering problems"

## See other formats

Hermite spectral method to ID forward Kolmogorov equation and its application to nonlinear filtering problems Xue Luo and Stephen S.-T. Yau, ieee Fellow Abstract — In this paper, we investigate the Hermite spectral method (HSM) to numerically solve the forward Kolmogorov equation (FKE). A useful guideline of choosing the scaling factor of the generalized Hermite functions is given in this paper. It greatly improves the resolution of HSM. The conver- gence rate of HSM to FKE is analyzed in the suitable function space and has been verified by the numerical simulation. As an important application and our primary motivation to study the HSM to FKE, we work on the implementation of the nonlinear filtering (NLF) problem with a real-time algorithm developed in 1 17 1. The HSM to FKE is served as the off-line computation in this algorithm. The translating factor of the generalized Hermite functions and the moving- window technique are introduced to deal with the drifting of the posterior conditional density function of the states in the on-line experiments. Two numerical experiments of NLF problems are carried out to illustrate the feasibility of our algorithm. Moreover, our algorithm surpasses the particle filter as a real-time solver to NLF. I. Introduction The central problem in the field of nonlinear filtering (NLF) is to give the instantaneous and accurate estimation of the states based on the noisy observations, if enough computational resources are provided. In 1960s, Duncan fTl . Mortensen (T8| and Zakai |23| independently derived the so-called DMZ equation, which the unnormalized conditional density function of the states satisfies. Hence the central problem in NLF is translated into solving the DMZ equation in the real time and memoryless manner. It is worthy to point out that the "real time" and "memory- less" are the most important properties one would like to maintain in the design of the optimal/suboptimal nonlinear filters for real applications. More specifically, "memory- less" refers that one only needs the latest observation to update the estimation of the states without refering back to any earlier observation history; "real time" means that the decision of the states is made on the spot, while the observation data keep coming in. It is well known that the exact solution to the DMZ equation, generally speaking, can not be written in a closed form. With the well-posedness theory of the DMZ X. Luo is with the department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Science and Engineering Offices (M/C 249), 851 S. Morgan Street, Chicago, IL 60607-7045 xluo6@uic.edu S. S.-T. Yau is the faculty of Department of mathematical sciences, Tsinghua University, Beijing, 100084, P.R.China. He is the Emeritus Distinguished Professor of University of Illinois at Chicago yau@uic . edu equation in mind, many mathematicians inake efforts to seek an efficient algorithm to construct a "good" approxi- mate solution to the DMZ equation. One of the methods is the splitting-up method from the Trotter product formula, which was first described in Besoussan, Glowinski, and Rascanu [5], |6|. It has been extensively studied in many articles later, for instance 1121 . 1141 . 1151 and |19| . In 1990s, Lototsky, Mikulevicius and Rozovskii fT6) devel- oped a new algorithm (so-called S'^-algorithm) based on the Cameron-Martin version of Wiener chaos expansion. However, the above methods require the boundedness of the drifting term and the observation term (/ and h in l |l.l[ )), which leaves out even the linear case. To overcome this restriction, Yau and Yau |22| developed a novel algorithm to solve the "pathwise-robust" DMZ equation, where the boundedness of the drift term and observation term is replaced by some mild growth conditions on / and h. Nevertheless, they still made the assumption that the drift term, the observation term and the diffusion term are "time-invariant". That is to say, /, h and g in ([TTTJ are not explicitly time-dependent. In 1171 . we generalized Yau-Yau's algorithm to the most general settings of the NLF problems - "time-varying" case - where /, h and g are explicitly time-dependent. Our study of solving the forward Kolmogorov equation (FKE) by the Hermite spectral method (HSM) is closely related to the implementation of the algorithm developed in 1171 . The detailed formulation of our algorithm could be found in Appendix A or 1 17|. Briefly speaking, in our algorithm, we start from the signal based model: dxt = f{xt,t)dt + g{xt, t)dvt, dyt = h{xt,t)dt + dwt, where Xt is a vector of the states of the system at time t with xo satisfying some initial distribution and yt is a vector of the observations at time t with yo = 0. vt and wt are vector Brownian motion processes with E[dvtdvf] = Q{t)dt and E[dwtdw'^] = S{t)dt, S{t) > 0, respectively. The DMZ equation is derived as da(x, t) = La{x, t)dt + a[x, t)h^ {x, t)S^^ {t)dyt a{x, 0) = ao{x), (1.2) where a{x) is the unnormalized conditional density funci- HSM to ID FKE and its application to the NLF problems ton, (Jo{x) is the density of the initial states xq, and dxidxj dxi (1.3) To maintain the real-time property, solving the DMZ equation is translated into solving a FKE off-line and updating the initial data on-line at the beginning of each time interval. Let Vk = {0 = ro < ri < ■ ■ ■ < ^ T} be a partition of [0,r]. The FKE needs to be solved at each time step is dui , (1.4) where L is defined as l |1.3[ l. The initial data is updated as follows -(x, t) = - ^/i^S ^h^Ui{x,t) on[Ti-i,Ti], ui{x,0) = ao{x) Wi(a;,Ti_i) = exp ri_i)5 ^(ri_i) i > 2, _ilx,ri_il (1.5) where Ui is transformed from o, see the detailed for- mulation of our algorithm in the Appendix A or 1171 . From the above description, it is not hard to see that the FKE \\A\ needs to be solved repeatedly on each time interval [ri_i,ri]. Thus, it is crucial to obtain a good approximate solution to \\A) . In this paper, we adopt HSM to solve FKE for two reasons: on the one hand, HSM is particularly suitable for functions defined on the unbounded domain which decays exponentially at infinity; on the other hand, HSM could be easily patched with the numerical solution obtained in the previous time step while the moving-window technique is in use in the on- line experiments. The HSM itself is also a field of research, which could be traced back to 1970s. In |10|, Gottlieb et. al. gave the example sin a; to illustrate the poor resolution of Hermite polynomials. To resolve M wavelength of sin a;, it requires nearly K'P Hermite polynomials. Due to this fact, they doubted the usefulness of Hermite polynomials as bases. The Hermite functions inherit the same deficiency from the polynomials. Moreover, it is lack of fast Hermite transform (some analogue of fast Fourier transform). Despite of all these drawbacks, the HSM has its inherent strength. Many physical models need to solve a differential equation on an unbounded domain, and the solution decays exponentially at infinity. From the computational point of view, it is hard to describe the rate of decay at infinity numerically or to impose some artificial boundary condition cleverly on some faraway "boundary". Therefore the Chebyshev or Fourier spectral methods are not so useful in this situation. As to the HSM, how to deal with the behavior at infinity is not necessary. Recent applications of the HSM can be found in [S], (51 , fTTl . (20J, tlJJ, etc. To overcome the poor resolution, a scaling factor is necessary to be introduced into the Hermite functions, refer to fS), (4). It is shown in [4| that the scaling factor should be chosen according to the truncated modes A'^ and the asymptotical behavior of the function f{x), as \x\ — >■ oo. Some efforts have been made in seeking the suitable scaling factor a, see II, QU, (20), etc. To optimize the scaling factor is still an open problem, even in the case that fix) is given explicitly, to say nothing of the exact solution to a differential equation, which is generally unknown a-priori. Although some investigations about the scaling factor have been made theoretically, as far as we know, there is no practical guidelines of choosing a suitable scaling factor. Nearly all the scaling factors in the papers with the application of HSM are obtained by the trial-and-error method. Thus, we believe it is necessary and useful to give a practical strategy to pick an appropriate scaling factor and the corresponding truncated mode for at least the most commonly used types of functions, i.e. the Gaussian type and the super- Gaussian type functions. The strategy we are about to give only depends on the asymptotic behavior of the function. In the scenario where the solution of some differential equation needs to be approximated (the exact solution is unknown), we could use asymptotical analysis to obtain its asymptotic behavior. Thus, our strategy of picking the suitable scaling factor is still applicable. A numerical experiment is also included to verify the feasibility of our strategy. Although it may not be optimal with respect to the accuracy, our strategy provides a useful guideline for the implementations of HSM. In this paper, the precise convergence rate of the HSM to FKE is obtained in suitable funciton space by numerical analysis and verified by a numerical example. Let us draw our attention back to the implementation of our algorithm to NLF problems. Through our study of HSM to FKE, the off-line data could be well pre- pared. However, when synchronizing the off-line data with the on-line experiments, to be more specifically, updating the initial data according to \\.5) on-line, another difficulty arises due to the drifting of the conditional density function. The untranslated Hermite functions with limited truncation modes could only resolve the function well, if it is concentrated in the neighborhood of the origin. Let us call this neighborhood as a "window". Unfortunately, the density function will probably drift out of the current "window". The numerical evidence is displayed in Fig. |4.5| To efficiently solve this problem, we for the first time introduce the translating factor to the Hermite functions and the moving-window technique for the on-line implementation. The translating factor helps the moving-window technique to be implemented more neatly and easily. Essentially speaking, we shift the windows back and forth according to the "supporf of the density function, by tuning the translating factor. This paper is organized as follows. Section II introduces the generalized Hermite functions and the guidelines of choosing suitable scaling factor to improve the resolution; 2 HSM to ID FKE and its application to the NLF problems section III focuses on the analysis of the convergence rate of HSM to FKE and a numerical verification is displayed. Section IV is devoted to the application to the NLF problems. The translating factor and the moving- window technique are addressed in detail. Numerical simulations of two NLF problems solved by our algorithm are illustrated, compared with the particle filter. For the readers' convenience, we include the detailed formulation of our algorithm in Appendix A and the proof of Theorem |2.1| in Appendix B. II. Generalized Hermite functions Let us introduce the generalized Hermite functions and derive some properties inherited from the physical Hermite polynomials. Let L^(R) be the Lebesgue space, which equips with thenorm||-|| = {Jp\-\'^dx)^ and the scalar product {■,■) . Let Unix) be the physical Hermite polynomials given by Unix) = (-l)"e^'9Je~'^', n e Z and n > 0. The three-term recurrence ■Ho = l, Hi{x) = 2x and Hn+iix) = 2x'Hn{x) — 2nHn^iix) (2.1) is more handy in implementations. One of the well-known and useful facts of Hermite polynomials is that they are mutually orthogonal with respect to the weight wix) = _ 2 e ^ . We define our generalized Hermite functions as h:^^{x) =1H„(a(x-/?))e-5"'(-«', (2.2) for n £ Z and n > 0, where a > 0, /3 G R are some constants, namely the scaling factor and the translating factor, respectively. It is readily to derive the following properties for \2.2y . I) The {H^'^}'^^o forms an orthogonal basis of L^{R), i.e. / m'^{x)H'^\x)dx^ (2.3) where Snm is the Kronecker function. 2) H"''^{x) is the n eigenfunction of the following Strum-Liouville problem + \nU{x) = 0, u{x))) (2.4) with the corresponding eigenvalue A„ — 2a^n. 3) By convention, H^-^ = 0, for n < 0. Forn G Z and n > 0, the three-term recurrence holds: 2a{x - l3)H^'\x) =^/2^H^'f^[x) (2.5) + .M^HZ'^.ix); or 2a\x - I3)m-^{x) ^^H:l\{x) "+l-^n+^l(^)- 4) The derivative of H"'^ [x) is a linear combination of H"J,{x) and H^'^,{x): d.HZ'^ix) = ^\/A^-H'°fi(3;) - Xn+iH"f^{x) aH^L^x)- aH^f.ix). (2.6) 5) Property 1) and 4) yield the "orthogonality" of {dxm-f'(x)}^^o- dxH"'^ {x)dxH^'^ {x)dx 4a (An + A„+i), if m : I = min{n, m}, if \n — m\ = 2; 0, otherwise. (2.7) The generalized Hermite functions form a complete or- thogonal base in L^(K). That is, any function u G L^(R) can be written in the form u{x) = ^ u„H"''^{x) where {un}^^^ are the Fourier-Hermite coefficients, given by a 7^ u{x)HZ'^ {x)dx (2.8) Let us denote the subspace spanned by the first + 1 generalized Hermite functions by 7?.jv: 7^iv = span{//o"■''(x),••• , ff°'''(a;)} . (2.9) In the sequel, we follow the convection in the asymp- totic analysis that a ~ 6 means that there exists some constants Ci, C2 > such that C\a < b < C2a; a < b means that there exists some constant C3 > such that a < Cs,b. Here, C\,C2 and are generic constants independent of a, j3 and N. A. Orthogonal projection and approximation It is readily shown in )2\\ for a > 0, /3 = that the difference between an arbitrary function and its orthogonal projection onto 7?. at in some suitable function space could be precisely estimated in terms of the scaling factor a and the truncation mode TV. Let us first introduce the function space ;9(K), for any integer r > 0, M^a,;3(K) :={iiG L'(R) : \\u\\r,c,.fi < fe=0 J (2.10) where A^ is in l |2.4[ ( and Uk is the Fourier-Hermite coefficient in jZ8) . We shall denote W''(R) for short. 3 HSM to ID FKE and its application to the NLF problems if no confusion will arise. Also, the norms are denoted briefly as j| • jjr - The larger r is, the smaller space W'^(R) is, and the smoother the functions in VF'^(R) are. The index r can be viewed as the indicator of the regularity of the functions. Let us define the L^— orthogonal projection P\ ,a,/3 L^(R) -i> 7^]v, i.e. given v G -L^(R), (2.11) The superscript q, /? will be dropped in P^'*^ in the sequel if no confusion will arise. More precisely, JV Pnv{x) := v„H^''^{x), n=0 where Vn are the Fourier-Hermite coefficients defined in \2.S\ . And the truncated error j ju— Pjvuj |r, for any integer r > 0, has been essentially estimated in Theorem 2.3, 1111 for a = 1, /3 = 0, and in Theorem 2.1 , 1211 for arbitrary Of > and /3 = 0. For arbitrary q > and /3 7^ 0, the estimate still holds. Theorem 2.1: For any it G VF' (R) and any integer < /i < r, we have PnuIu < ■2N- (2.12) where \u\^ := \ \d^u\\ are the seminorms, if A'^ S> 1. The proof is extremely similar as those in 1111 and 1211 . Thus, we omit it here and include it in Appendix B for the readers' convenience. B. Guidelines of the scaling factor From Theorem |2.1[ it is known for sure that any function in W^'^(R) could be approximated well by the generalized Hermite functions, provided the truncation mode A'^ is large enough. However, in practice, "suffi- ciently" large is impossible. To improve the resolution of Hermite functions with reasonable large we need the scaling factor a, as pointed out in |4|. Many efforts have been made along this direction, refer to (3), l4l . 1131 , etc. However, the optimal choice of a (with respect to the truncation error) is still an open problem. In this subsection, we give a practical guideline to choose an appropriate scaling factor for the Gaussian type and super- Gaussian type functions. It is well known that, for smooth functions f(x) = '^'^^Q fnH"'^ {x), the exponential decay of /„ with respect to n implies that the infinite sum is dominated by the first A'^ terms, that is. o for A'' 3> 1. Thus, the suitable scaling factor is supposed to get the Fourier-Hermite coefficients decaying as fast as possible. Once the coefficient approaching the machine error (say 10~^®), many other factors such as the roundoff error will come into play. Hence, it is wise to truncate the sequence here. Therefore, we need some guidelines of choosing not only the suitable scaling factor a but also the corresponding truncation mode A'^. Suppose the function f{x) concentrates in the neighbor- hood of the origin and behaves asymptotically as e"'''^' with some p > and k > 2, as |x| — >■ +00. Our guidelines are motivated by the following observations: 1) The function / decays exponentially fast, as |a;| — > 00. So, /„ « J_^^ f{x)H"'^ {x)dx, provided L is large enough, due to \2.S) . 2) For the exact Gaussian function e"''^ , p > 0, the optimal a is naturally to be \/2p with the truncated mode A'^ = 1. It follows by the fact that with this choice, e = H^'°{x). thus, e ''^ is orthogonal to all the rest of -ff"'", n > 0. That is, (e-P^^)o ^ and (e-?^^)^ = 0, n > 1. This suggests that the more matching the asymptotical behavior of / to e~3" ^ , the faster the Fourier- Hermite coefficients decays, and the smaller trun- cation mode A' is. 3) It is natural to adopt the Gaussian-Hermite quadra- ture method to compute the Fourier-Hermite coef- ficients by \2.9i) . The truncation mode A' has to be chosen such that the roots of Hermite polynomial Hn+i cover the domain [—aL, aL] where the integral \2.S\ is contributed most from both / and n = 0,--- ,iV. We describe our guidelines for the Gaussian type and the super-Gaussian type functions separately as follows. Case I. Gaussian type, i.e. f{x) ~ e l^l — >■ +00. 2 122 1) e-''^ ~ e--" " , p > 0, as 00, which yields 2) The integrand in i2.8i is approximately e Using the machine error 10 to decide the domain of interest L, i.e. e 10" yielding that L ^ V8p-i In 10; 3) Determine the truncation mode A' such that the roots of Hermite polynomial Hn+i covers approx- imately {—aL, aL), where aL « 4Vln 10. Case II. Super-Gaussian type, i.e. f{x) ~ e~^^ , as ^1 — >■ +00 for some fe > 2, p > 0. 1) Notice that e's"^""^ > e"'"''', when x > 1. Thus, we require that e 2" that aL ^ \/321nl0; 10 , which implies 2) We match e we 2 ^ near x = ±L yields that a ^ ySpLt"^ Hence, L x (16p~MnlO)^, a fcpfc(lnlO)2 (=; 3) Determine the truncation mode A' such that the roots of Hermite polynomial Hn+i cover approxi- mately {—aL,aL). To exam the feasibility of our strategy, we explore the Gaussian type function f{x) — e~^^ cos(^). Accord- ing to the strategy in Case I, we choose the scaling factor a ^ ^ 3.1, L ^ y^^^ « 1.9194 and A^ ^ 24. As shown in Fig. |2.1[ the truncation error with a = 3.1 decay the most fast with respect to the truncation mode A'^ and approach the machine error near the 20* frequency 4 HSM to ID FKE and its application to the NLF problems f(x)=cos(>c;i 0)6"™ , |5=0 □ □ □ □ □ □ □ o + 0=3.1 □ a=1 10 15 truncation mode N Fig. 2.1. The truncation error v.s. the truncation mode of f{x) = cos (^)e-5"=^ is plotted, with ^ = 0, a = 4,3.1 and 1, respectively. mode. Meanwhile, the decay of the truncation error with a = 4 and a — 1 are much slower. Moreover, the truncation mode A'^ = 24 is appropriate in the sense that the next few coefficients start to grow, due to the roundoff error. Remark 2.1: 1) This strategy is very useful. However, it is not the optimal scaling factor a. For example, if f{x) — e~2^ , then the optimal scaling factor a — 1 and A'^ = 0, instead of A'' = 24 from our guideline. 2) Although the scaling factor helps to resolve the function concentrated in the neighborhood of the origin, it helps little if the function is peaking away from the origin. The numerical evidence could be found in Table |4.2| This is the exact reason why we need to introduce the translating factor to the generalized Hermite functions when applying to the NLF problems, see the discussion of translating factor in section IV.B. III. Hermite spectral method to ID forward KOLMOGOROV equation The general ID FKE is in the form ut{x,t) =p{x,t)uxx{x,t) + q{x,t)ux{x,t) + r{x,t)u{x,t), for {x,t) eRxR+ u{x, 0) = cro(x). (3.1) The well-posedness of ID FKE has been investigated in (2|. We state its key result here. Lemma 3.1: (Besala, (2)) Let p{t,x), q{t,x), r{t,x) (real valued) together with pa;, p^cx, Qx be locally Holder continuous in D — (to,^i) x K. Assume that 1) p{t, 2;) > A > 0, V (t, x) G D, for some constant A; 2) r{t,x) < 0,y{t,x) G V- 3) {r-qx+ Pxx){t, x)<0,\/ (t, x) G V. Then the Cauchy problem with the initial condition u(to, x) = uo{x) has a fundamental solution r{t, x; s, z) which satisfies < r{t,x;s,z) < c(t- s)~5 for some constant c and /oo r(t, x; s, z)dx < 1. - 00 Moreover, if 110(2;) is continuous and bounded, then /oo T{t, x; to, z)uo{z)dz - 00 is a bounded solution of p.l[ l. Through the transformation w^x, t) □ p2 [s,t)ds,t (3.2) where q{x,t) =p~^{x,t) <li3:,t) - -p ^Px{x,t) + T p ^pt{s,t)d.s (3.3) equation jSTTJ can be simplified to the following FKE with the diffusion rate equals 1 and without the convection term. Wt{x, t) — Wxx{x, t) + V{x, t)w{x, t), for K X 'w{x, 0) = ^10(3;), (3.4) where V{x,t) 1 + o / qt{s,t)ds + r[x,t) (3.5) Remark 3.2: From the computational point of view, the form {i.4\ is superior to the original form l |3.1[ ) in general, when implementing with the HSM. (i) If both the potential V{x,t) and the initial data 'w{x, 0) are even functions in x, so is the solution to 1 3.4 1 With the fact that the odd modes of the Fourier-Hermite coefficients of the even functions are identically zeros, it requires half amount of computations to resolve the even functions. (ii) Even when V{x, t) and 'w{x, 0) are not even, it is still wise to get rid of the convection term, since this term will drive the states to left and right, and probably out of the current "window". Shifting of the windows frequently by the moving-window technique will definitely affect the computational efficiency. A. Formulation and convergence analysis In this subsection, we shall investigate the convergence rate of the HSM of solving the FKE. Let us consider the FKE j3.4^ with some source term F{x,t). The weak 5 HSM to ID FKE and its application to the NLF problems formulation of HSM is to find un{x, t) G TZn such that {dtUN{x,t),(p) + {V{x,t)uN{x,t),ip) + {F{x,t),^), . un{x, 0) =Pnuo{x), (3.6) for all if £ TZn- The convergence rate is stated below: Theorem 3.2: Assume -(i + la;]')^ < V{x,t) < c, for all {x,t) G K X (0,r), for some 7 > and some constant C. If uo G VK'^(K) and it is the so- lution to 1 3.4 1 with source term F(x,t), then for u G L°°{0,T;W''(R)) n i^(0,r;'tV(K)) with r > 27 and r 47-21- + 2 . 1 iV>max<^ci 2^-1 max{(Q/3) Proof of Theorem \3.2\ Denote Un ~ Pnu for a -T max{(a^)*^,l} it yields that \\u - UN fit) < ca-^''-^ ma.yi{(apf'' , l}N^''-\ (3.7) where c* depends only on T, |!itjjioo(o,T;W"-(E)) and 11^111-2(0, T;VK '-(«))• Before we prove Theorem |3.2[ we need some estimate on ||x'^i9J!2j((^j;)||2^ fQj. jijjy integer ri,r2 > 0: Lemma 3.2: For any function u G W^^^^^ (M.), with some integer ri , r2 > 0, we have \x''^ d^'^ u\f < a ^'■^ ^ max{(Q^)^''\ (3.8) Proof: For any integer ri , r2 > 0, r-i I I 2 X Oj; lt|| = y^^u„x''^d^'^Hn''^{x) ^ 00 r2+ri by ([23} and ( |2.6[ l, where for each n fixed, a„,fe is a product of 2(ri + r2) factors of or ^A„+j, with — r2 — ri < j < r2 + ri. Let n* > such that a /? ~ And notice that A„+_, ~ A^+i for , T- 1 O Tr\r n _L n + j > and W^fAx) = for n + j < 0. Hence, we have 00 Jl — Tl * + 1 -2ri-l o\2ri <Q max{(a/3) ''^ , 1}| juj 1^^+^ simplicity. By i3.4i with source term F{x,t) and the definition of Un, we obtain that = {dt{u - Un),<p) = - {ux,'fix} + {V{x,t)u,ifi) + {F{x,t),(f) - {dtUN,'p) ^ {dtUN,'p) = - {Ux,'Px} + {V{x,t)u,if) + {F{x,t),^), (3.9) for all (/p G 72. AT. Combine with l |3.6| l, it yields that {dt{uN - Un), f) ^ - (dxiuN - u), ^x) + {V{x,t){uN — u),ip), for all </? G 7?.]v. Set qn = un — Un- Choose the function ip — 2qn, then we have dtWoN^ = - 2\\dxQNf - 2{dx(UN - u), BxQn) + 2{V{x,t)QN, Qn) + 2{V{x,t)[UN ~u),qn). (3.10) By Young's inequality, \{dx{UN ~ u),dxQN)\ < l\\dx{UN -u)f + \\dxgNf. (3.11) The assumption V{x,t) < C for {x,t) G M x (0,T) yields that {V{x,t)gN,gN) <C\\eNf, (3.12) for (x,t) G R X (0,T). Moreover, we have \{V{x,t){UN-u),QN)\ < ^\\V(UN^n)f + l\\gNf, (3.13) by Cauchy-Schwartz's inequality. Substitute l |3.11[ l-( |J. 13[ l into l |3.10| l, we obtain that dt\\gN\\' -{C+l)\\gNf <\\V{Un -u)f + ^\\dx{UN - n)f. (3.14) Notice that V > — (l+|a;p)^, for some 7 > 0. Essentially by the estimate in Lemma [^2] we can estimate \\V{UN-U)f <||(1 + \x\'')-'{UN-u)f < Wix^-' + 1){Un - u)\\'' 00 <a"'*^"^max{(a^)''^,l} ^ ^t'iiii-l n = JV + l + \\Un — uf <a""-'-' miix{iaP)*\l}N^^-''\\u\\l I — 2r — Iat — '"ll l|2 + a N kt r- (3.15) for any integer r\,r2 > 0, by l|2.3 The estimate of the second term on the right hand side of l|3.15^ is followed by Theorem |2.1| Again, by Theorem |2.1| we obtain \\dx{UN - u)f = \Un - u\i < a-^'-+'N'-'-\\u\\l (3.16) 6 HSM to ID FKE and its application to the NLF problems Substitute ([STTSj, \3.16\ into l |3.14^ , we obtain dtWQNlf -iC+l)\\gN\\'' provided that Af>max<^ci ^^-i max {(q/3) 1} ^-^^ , a^-T max{(a/3)*^,l}"5^ /' ^0 Therefore, it yields that \\QN\\\t) <a-^^-Vax{(a/3)^^l}iV2^-'' '0 By the triangular inequality and Theorem |2.1| ||u — Mjv||^(t) < ||£)Ar||' + llM-[/ivl|' <a-^->-^N^'^-^ [Ml + max{(a/?)'''',l} /* e-<^+i'<*-"'||u||?,(s)ds < c'a-"^'^ max{(a/?)*^, IjA^^^"", where c* is a constant depending on | |loo(o,t;W(m))> 11,2(0, T;W"-(E)) and T. S. Numerical verification of the convergence rate To verify the convergence rate of HSM, we explore an ID FKE with some source F{x,t). The exact solution could be found explicitly as our benchmark. The error v.s. the truncation mode is plotted. We consider the ID FKE ut = u-xx — X u + (sin t + cos t + 3x)e u{x, 0) = xe (3.17) for (a;, t) £Rx [0, T]. It is easy to verify that u{x, t) = [x + sint)e~ 2^ is the exact solution. Notice that the initial data, the potential and the source in l |3.17^ are all concentrated around the origin. So, we set /3 = 0. For notational convenience, we drop /3 in this example. As to the suitable scaling factor q, from our strategy in section II.B, we know that it is better to let a = 1. However, if we do so, the first two modes will give us extremely good approximation. Hence, the error v.s. the truncation mode won't be perceivable. Due to this consideration, we pick a = 1.4 (a little bit away from 1, but not too far away so that it won't affect the resolution too much). The formulation l|3.6^ yields {dtUN,(p) = — {dxUN,dx(p) — {xUN,X(p) + {F{x,t),^), (3.18) for all ((9 G TZn- Take the test functions tp = H"(x), n = 0, 1, • • • , A'^, in l|3.18|l. The numerical solution ujv £ TZn 20 25 30 35 truncation mode N Fig. 3.2. The L^.g^-ors of the HSM to FKE pi?) v.s. the truncation mode N = 5, 15, 25, 35 and 45 is plotted, with a = 1.4, /3 = and the time step dt = 10~^. can be written in the form UN The matrix form of ( |3.18^ follows from l |2.5[ > and \2J\ : dta{t) = Aa{t) + f{t), (3.19) where a(t) = (ao(t), ai(t), ■ • ■ , ajv(t))^, /(t) = ^/o(t), fi{t), ■ • ■ , ,/]v(t)^ are column vectors with A'^ + 1 entries, fi{t), i = 0, 1, • • • , A^, are the Fourier-Hermite coefficients and ^4 is a penta-diagonal (A'' + 1) x (A'^ + 1) constant matrix, where A = —Ai — A2, 2 fc = min{j,j}, |i-j|=2, , 0, otherwise, and { V(fc + l)(fc + 2) 2q2 fc = min{j,j}, \i-j\=2, (2i + 1) . . * =3, 2q2 I, otherwise. The errors v.s. the truncation mode A'^ at time T = 0.1 is plotted in Fig. |3.2| The ODE l|3TT9j is numerically solved by central difference scheme in time with the time step dt = 10"^. It indeed shows the spectral accuracy of HSM. IV. Application to nonlinear filtering PROBLEMS Recall the brief description of our algorithm in the introduction (and more details in Appendix A), the off- 7 HSM to ID FKE and its application to the NLF problems line computation is to numerically solve the FKE ( |1.4| l repeatedly on each interval [ri,ri+i]. Equation l |1.4| is in the form of ( |3.1| l with r(x,t) \h^/S + Q{gl +ggxx) - fx where Q, S, /, g and h are in {OJ. A. Existence and Uniqueness of the solution to the FKE In this subsection, we interpret the well-posedness theorem (Lemma 1 3. 1^ for general ID FKE in section III in the framework of the NLF problems. Proposition 4.1 (Existence): Let /, g, h in are Holder continuous functions m T) := R x {ta,ti). gx, gxx and fx exist and are also Holder continuous in T>. Assume further that 1) > A > 0, for some A > 0; 2) S > 0; 3) -\h^/S - fx + Q{gl + ggxx) < C, for some constant C, for (x, t) G T). Then there exists a bounded solution u{x, t) to l |3.1^ , if the initial condition uo{x) is continuous and bounded. Proof: Conditions l)-3) in Lemma [3TT] are directly translated into conditions l)-3) in this proposition with C < 0. For C > 0, let v{x,t) = e-'^'*~*»)'u(a;, f), then V satisfies Vt (a;, t) =p{x, t)v^^ {x,t)+q{x, t)v^ {x, t) + {r{x,t)~C)v{x,t), (4.20) for {x,t) G T), with the initial condition v{x,to) = 110(2;). The coefficients of l |4.20^ satisfy the conditions in Lemma [3T| Thus, we apply Lemma [3TT] directly to l |4.20^ . The existence of the solution to \2>A\ follows immediately. ■ Remark 4.3: In practice, the initial data of the condi- tional density function is either compactly supported or exponentially decays as \x\ — >■ +00. So, the assumption on the initial data in Proposition |4.1| is valid. For concise of notations, we give the uniqueness for the equation instead of l |3.1| >. It can be easily trans- formed into each other, due to the bijective transformation Proposition 4.2 (Uniqueness): There exists a unique solution to l |3.4| ( in the class that {u : lim\x\-foo uux = 0} if V{x,t) is bounded from above in V. Proof: Case I: Assume V{x,t) < in 2?. Suppose there exist two distinct solutions to l |3.4^ , say ui and U2. Denote rj :— ui — U2, and 77 satisfies Vt = Vxx + V{x,t)r], (4.21) in 2? with the initial condition rj{x,to) = 0. Use the standard energy estimate, i.e. multiplying ( |4.21^ with rj and integrating with respect to a; in R: 1, / T^xW + / V(x,t)r]''dx < -\\Vx\\ < 0, TABLE 4.2 Trunction error v.s. the "peaking" po of the Gaussian function f{x) PO erroro errors -1 3.3 X 10"" 1.1 X IQ-^ 8.2 X 10-1'' 7.7 X IQ-*' 1 1.6 X 10"^^ 1.8 X 10"^ 2 1.8 X IQ-^ 3.3 X IQ-'-'-^ 3 7.7 X IQ-" 8.2 X 10"-^^ 4 1.1 X IQ-^ 1.6 X IQ-'-'-^ The scaling factor is chosen to be 1 according to the guideline in section II. B and the truncation error is N = 24. The truncation en'ors with different translating factor /3 is denoted as error^, which is defined as ||/ - Yln^o UH^'^^W- by the lim that integration by parts, and the facts that > rjrjx = and V{x,t) < in D. This yields ll'7ll'W< for t £ {to,ti). With the fact that r){x,tQ) = 0, we conclude that 77 = in D, i.e. ui =112. Case II: Assume V{x,t) < C, for some C > 0. We use the strategy in the proof of Proposition |4.1[ Let v{x,t) = e~^^ °'u{x,t), then v satisfies i3.4i with the potential V{x, t) — C < in V. By case I, we conclude the uniqueness of v, so does u. ■ Remark 4.4: The similar conditions as in Proposition |4. 1| are derived to guarantee the well-posedness of the "pathwise-robusf DMZ equation in |22| and to estab- lish the convergence of our algorithm in II7I . They essentially require that h has to grow relatively faster then /. They are not restrictive in the sense that most of the polynomial sensors are included. For example, f(x) = fox\ g{x) = go(l + a;^)''' and h{x) = hox'- , with 5, Q > 0, /o,<7o and fto are constants, j,k,l G N, provided I > max { , 2fc — 1 } . B. Translating factor P and moving-window technique As we mentioned in the introduction, the untranslated Hermite functions with suitable scaling factor could re- solve functions concentrated in the neighborhood of the origin accurately and effectively. However, the states of the NLF problems could be driven to left and right during the on-line experiments. It is not hard to imagine that the "peaking" area of the density function escapes from the current "window". The translating factor /3 is introduced under the cir- cumstance that the function is peaking far away from the "window" covered by the current Hermite functions. We translate the current Hermite functions to the "support" of the function, by letting the translating factor /3 near the "peaking" area of the function. In Table 14.21 we list the truncation error of the Gaus- sian function f{x) = e 2 with various po = — 1, ■ ■ ■ ,4 and different translating factors /? = or 3. According to the guidelines in section II.B, the scaling 8 HSM to ID FKE and its application to the NLF problems u/=o i^L^, + I3j,l3j + L„). For simplicity and clarity, let us assume further that 1) The operator (i — ^h'^S~^h) is not explicitly time-dependent; 2) The time steps are the same, i.e. r^+i — Ti — At. For the storage of the off-line data, on each interval {—L^+Pjjfij+Lw), it requires to store (TV + 1)^ floating point numbers. Hence, the total (J + 1) intervals requires to store (J + 1){N -\- Vf' floating point numbers. As to the number of the flops in the on-line computations, if no moving-window technique is adopted during the experiment, for each time step, it requires 0{{N + 1)^) flops. The number of the flops to complete the experiment during [0,T] = u'^-^[Ti,Ti+i] is 0{k{N + lf). Suppose the number of shifting the windows during [0, T] is P, then the total number of flops is O {{k + P){N + 1)^). Remark 4.5: If either assumption 1) or 2) is not satis- fied, then the real time manner won't be affected. That is, the number of the flops in the on-line experiment remains the same. But the off-line data will take more storage as the trade-off. To be more specific, on each interval (— L„ + /3j, Pj + Lw), it requires to store fc x (A'' + 1)^ floating point numbers, where k is the total number of time steps. Therefore, the total storage is k{J+l){N+l)'^ floating point numbers. C. Numerical simulations In this subsection, we shall solve two NLF problems by our algorithm: the almost linear sensor and the cubic sensor. Since the drift term could always be absorbed into the potential V{x) by the transformation \3.2\ , for simplicity, in our examples, we set / = 0. Our algorithm is compared with the particle filter in both examples. The particle filter is implemented based on the algorithm described in 1 1 1. And the systematic resampling is adopted if the effective sample size drops below 50% of the total number of particles. As we shall see, our algorithm surpasses the particle filter in the real time manner. 1) Almost linear filter: We start from the signal obser- vation model dxt = dvt {Pj}j=o, for some J > 0, need to be pT^ared before- I '^V* = + 0.25co8Xt)dt + dwt, hand, such that [—L,L] C u/=o {—L^ + j3j,l3j where Xt, yt € R, vt, wt are scalar Brownian motion factor is a = 1 and the truncation mode = 24. As shown in the table, the further the function is peaking away from the origin, the larger the error is with untrans- lated Hermite functions. But with appropriate translating factor, the function could be resolved very well with the same scaling factor, for example, error,-? ~ 10"" for f{x) =e-3{— 3)'. Indeed this fact motivates the idea of moving-window technique. The suitable width of the window could be pre- determined if the trunction error of the density function v.s. various "peaking" po is investigated beforehand. To be more precise, suppose we know the asymptotical behavior of the density function of the NLF problem from the asymptotical analysis, say ~ e"''^ , with some p > 0, k > 2. According to the guideline in section II.B, the suitable scaling factor a and the truncation mode with /3 = could be chosen. With these parameters, the similar table as Table |4.2| could be obtained, i.e. the truncation error (erroro) of the function e~*''^~''°' v.s. various po - If the error tolenrance is given, then the appropriate width of the window is obtained according to the table. Take Table |4.2| as a concrete example. If the asymptotical behavior of the density function is e~2^ , then the scaling factor a — 1 and the truncation mode — 24. Suppose we set the error tolerance to be 10~^, then the suitable width of the window would be 3 + 3 = 6, from the first two column of Table [4. 2 1 The window covers the origin would be [-3,3]. Our algorithm with moving-window technique is il- lustrated in the flowchart Fig. |2.6| It reads as follows. Without loss of generality, assume that the expectation of the initial distribution of the state is near 0. During the experimental time, say [0,r], the state remains in- side some bounded interval [— L,L], for some L > 0. We first cover the neighborhood of by the untrans- lated Hermite functions {H"'^^}^^q, where a, N can be chosen according to the guidelines in section II.B. With the given error tolerance, the suitable width of the window could be pre-defined, denoted as L„. If [—L,L] C [— Lu,,Lu,], then no moving- window tech- nique is needed. Hence, the on-line experiment runs always within the left half loop in Fig. |2.6| Otherwise, The off-line data corresponding to different intervals {—Lw+I3j,l3j+Lw) have to be pre-computed and stored ahead of time. During the on-line experiment, if the expectation of the state E[xt] moves accross the boundary of the current "window" (the condition in the rhombic box in Fig. |2.6| is satisfied), the current "window" is shifted to the nearby window where E[xt] falls into. That is, the right half loop in Fig. |2.6| is performed once. Let us analyze the computational cost of our algorithm. Notice that only the storage capacity of the off-line data and the number of the flops for on-line performance need to be taken into consideration in our algorithm. Without loss of generality, let us assume as before E[a;](0) is near and our state is inside [~L,L] C processes with E[dVf dvt 1, E[dwt dwt Suppose the signal at the beginning is somewhere near the origin. The corresponding FKE in this case is Ut = 1 _1 2 ^u^. ^x (1 + COS a; u (4.22) Assume further that the initial distribution of xq is uq{x) — e 2 . This assumption is not crucial at all. The non-Gaussian ones, for example ito(a;) — e 2 , vvill give the similar results as the Gaussian one. It is easv to se e that the asymptotical behavior of the solution to 1 4.22 1 is e 2 . With the guidelines in section II.B, we choose a = 1, /3 = and TV = 25 for the 9 HSM to ID FKE and its application to the NLF problems Almost linear sensor 14 -2 • • • • • • • • • 1 5 10 15 20 25 30 35 40 45 50 time Fig. 4.3. Almost linear filter is investigated with our algorithm and the particle filter with 10 and 50 particles. The total experi- mental time is T = 50s. And the update time is At = 0.01. starting interval. We shall run the experiment for the total time T — 50s. Thus, we expect the density function probably will move out of the starting interval. Table |4.2| suggests that the appropriate width of the window should be 3, if the error tolerance is set to be lO^"". We shall overlap the adjacent windows a little bit to prevent frequent shifting of windows. Let us take the width of the overlaped region to be 0.5. Therefore, as the preparation for the moving-window technique, we shall prepare the off-line data for [-19.5,-13.5], [-14,-8], [-8.5,-2.5], [-3,3], [2.5,8.5], [8,14] and [13.5,19.5]. The correpsonding /3s are -16.5,-11,-5.5,0,5.5,11 and 16.5. The barrier in the rhombic box in the flowchart Fig |2.6| should be 3 (the width of the "window"). Our algorithm is compared with the particle filter with 10 or 50 particles in Fig. |4.3| for the total experimental time T = 50s. The time step is At = 0.01s. All three filters show acceptable experimental results. It is clear (between time 10 to 30) that the particle filter with 50 particles gives closer estimation to our algorithm than that with 10 particles. But as to the efficiency, our algorithm is superior to the particle filter, since the CPU times of particle filter with 10 and 50 particles are 5.00s and 35.75s respectively, while that of our algorithm is only 2.62s. As to the storage, the size of the binary file to keep the off-line data is only 35.5kB. During this particular on- line experiment, the window has been shifted for 13 times, which can't be perceivable from the figure at all. And it seems that the moving-window technique doesn't affect the efficiency of our algorithm. 2) Cubic sensor in the channel: We consider cubic sensor in the channel xt G [—3,3]: dxt ~ dvt 3 (4.23) dyt — Xfdt + dwt, where xt, yt G K, vt, Wt are scalar Brownian motion processes with Eldvfdvt] = 1, Elduufdiut] — 1. Assume the initial state is somewhere near 0. Cubic sensor 5 10 15 20 25 30 35 40 45 50 time Fig. 4.4. Cubic sensor in the channel is experimented for T = 50, with the time step At = 0.01s, by both particle filter and our algorithm. 50 X Fig. 4.5. The normalized density functions are plotted every other Is for the cubic sensor in the channel. The FKE is 1 1 6 Ut = -Uxj: — -X u. (4.24) Furthermore, we assume the initial distribution is uq [x) = g-i /4 gjjj^-g {jjg gf^fg inside the channel, we set our translating factor /3 = and the moving-window technique won't be used. According to section II.B, we choose the scaling factor a ^ 23 (iB^) ' ^ 2.4637, and the truncated mode TV ~ 45. In Fig. |4.4| we compare our algorithm with the particle filter with 50 particles for T — 50s. The observation data come in every 0.01s. Fig. |4.4| reads that both filters work very well. The result of our algorithm nearly overlaps with that of the particle filter all the time. However, the CPU time of our algorithm is 4.90s, while that of particle filter is 37.17s. With our algorithm, the on-line computational time for every estimation of the state is around 0.001s, which is 10 times less than the update time 0.01s. This indicates that our algorithm is indeed a real-time solver. The normalized density functions, which is defined as "^^''l — TT, have been plotted every other Is in Fig max^gj u(x.t] f J o El 10 HSM to ID FKE and its application to the NLF problems V. Conclusions In this paper, we first investigate the HSM applied to the ID FKE. It is well-known that the choice of the scaling factor Q is crucial to the resolution of HSM. We give a practical guidelines to help choosing the suitable one. The convergence rate of the HSM has been shown rigorously and has been verified by a numerical experiment. As an important application, we solve the NLF problem, by using the algorithm in fTTl . in the last section, where solving ID FKE serves as the off-line computation. To capture the state even if it drifts out of the "window", translating factor of Hermite functions and the moving- window technique are introduced. The translating factors help the switch of the windows back and forth easier, according to the "support" of the density function of the state. We analyzed the computational complexity of our algorithm in detail, with respect to the storage capacity of off-line data and the number of flops of the on-line computations. Finally, two online experiments - almost linear filtering and cubic sensor in the channel - are reported. The feasibility and efficiency of our algorithm are verified numerically, which surpasses the particle filter as a real time solver. Appendix A The detailed formulation of our algorithm Starting from the signal model ( |l.l[ l, the DMZ equation is derived for the unnormalized density function a{x, t) of the states Xt conditioned on the observation history Yt = {j/s : < s < f}. In real applications, one is more interested in the robust state estimators. Hence, for given observation path yt, let us make an invertible exponential transformation a{x,t) ^ explh^ {x,t)S~'^ {t)yt]p{x,t). (A.l) The "pathwise-robust" DMZ equation is obtained: f^ix,t) + ^^{h^s-YytPix,t) the robust DMZ equation with yt Ti-i < t < Ti, i — 1,2, - ■ ■ ,k on the interval = exp(-/i^S ^yt) ■ [exp {h^ S''^yt)p{x,t)] , pix,0) ^ ao{x). 2 (A.2) The exact solution to l |A.2| l, generally speaking, doesn't have a closed form. Hence, we developed an efficient algorithm to construct a good approximation in 1 17|. Let us assume that we know the observation time sequence = ro < ri < ■ • ■ < Tk = T apriorily. But the observation data {yr;} at each sampling time r,;, i = 0, ■ ■ ■ ,k are unknown until the on-line experiment runs. We call the computation "off-line", if it can be per- formed without any on-line experimental data (or say pre- computed); otherwise, it is called "on-line" computations. One only concerns the computational complexity of the on-line computations, since this hinges the success of "real time" application. Denote the observation time sequence sls Vk ~ {0 = To < Ti < ■ ■ ■ < Tk = T}. Let Pi be the solution of 2 ^{x,t) + ^^{h^S-^y yr,_,p,{x,t) = exp (^-h^ S~^yT,_-^ ■ \eyip(h^ S~^yr^_^^^ p,{x,t)^ pi(a;,0) = o-o(a;), or _ Pi{x,Ti-i) = pi_i(a;,Ti_i), for i = 2, 3, • Define the norm of Vk by \'Pk\ — supi<;<j.(ri Intuitively, as \'Pk\ — > 0, we have k in some sense, for all < t < T, where p{x,t) is the exact solution of ( |A.2| (. To maintain the real time manner, our algorithm resorts to the following proposition. Proposition 1.3: For each r^-i < t < Ti, i = ■ ,k. (A3) Ti-l). ,■■ ■ ,k, pi{x, t) satisfies i A.3 i if and only if ,{x,t) = exp \h^ {x,t)S'^{t)yr^_,'^p,{x,t), (A.4) satisfies the FKE ( fL4| l. The initial data need to be updated as \i.5\ , followed from JA31. With the observation time sequence known {ri}*Li, we obtain a sequence of two-parameter semigroup {U{t,Ti-i)}*^^i, for Ti-i < t < Ti, generated by the family of operators {L — |/i"^5'^^/i}t>o. The off- line computation in our algorithm is to pre-compute the solutions of \\A) at time t = r^+i, denoted as {U{Ti+i,T,)(l)i}fl^, where {<;/>; (a::)}gi (chosen as the initial data at i = Ti) is a set of complete orthonormal base in L^(R"). These data should be stored in preparation of the on-line computations. The on-line computation in our algorithm is consisted of two parts at each time step r^-i, i = 1, • • • ,k. • Project the initial condition Ui{x,Ti-i) G L^(R") at t = Ti-\ onto the base {(j)i(x)}^-^, i.e., Ui{x,Ti-i) = '^^^Ui^i4>i{x). Hence, the solution to (|1.4|l at t = Ti can be expressed as (A.5) Ui{x,Ti) ^U{Ti,Ti-l)Ui{x,Ti-l) OO = [U{Ti,Ti-l)(jll{x) where {U{Ti,Ti^i)(l}i{x)}fZi have already been computed off-line. Update the initial condition of ^IA\ at n with the new observation y^. Let us specify the observation updates (the initial condition of ^IA\ ) for each time step. For < t < ri, the initial condition is ■ui(x,0) = a-o{x). At time t = ti, when the 11 HSM to ID FKE and its application to the NLF problems observation is available, U2{x, Ti) ^ exp [h'^(x, Tl)S~^{Tl)yrj^]p2{x, n) exp [h''^{x,Ti)S^^{Ti)yri]ui{x, n), with the fact yo = 0. Here, ui{x,ti) = [W(Ti,O)0i(a;)], where {uij}fZi is com- puted in the previous step, and {U{Ti,0)(j)i{x)}'j^i are prepared by off-line computations. Hence, we obtain the initial condition U2{x,ti) of for the next time interval ri < t < T2. Recursively, the initial condition of l|1.4b for r,;_i < t < is and Ui{x,Ti^l) =ex.p[h'^ {x,Ti-l)S ^(Ti_l) (yr,_i - 2/r,_2)]Wi-l(2:,n-l), (A.6) for i — 2,3, ■•■ where Ui_i (a;, Ti_i) = Ui-2,l pl{Ti^l,Ti^2)<t)l{x)]. The approximation of p[x,t), denoted as p{x,t), is ob- tained k P{^,t) = ^XlTi_i,Ti]it)pt{x,t), (A.7) i = l where pi{x,t) is obtained from Ui{x,t) by l|A.4[. And a{x,t) could be recovered by i A.l Appendix B The proof of Theorem I2.1I Proof of Theorem \2.1\ By induction, we first show that for p = Q. For any integer r > 0, y OC II D l|2 V'^ .2 Q ^ — ' n = JV + l y OC yT^ >-r -.r ~2 n = N + l (B.l) Suppose for 1 < < r, ( |2.12^ holds for ^ — 1. We need to show that j2.12| ( is also valid for p. It is clear that \U — Pnu\^ <\dxU — PnOxU]^-! + \PNdxU - dxPNu\^^x. (B.2) On the one hand, due to the assumption for /i — 1, we apply j2.12[ l to dxU and replace p and r with p ~ 1 and r — 1, respectively: \dxu - PNdxu\^-i <a''-''-^N'^\\dxu\\r-i <a""'-5iV^||ti||^, (B.3) where the last inequality holds with the observation that °° 2 a : / udxH^" Jm 20F 2^ (a;)cia; uHl'J^^{x)dx, by (12.6 1 n A 1tn + l 7, — fin-l- 2 ^ 2 On the other hand, by the virtue of \2.()\ PnQxU — OxPnu oo ^PN'^UndxH^''^ {x) - UndxH"''^ {x) n=0 n=0 n=0 ^ iV + 1 n = -2 5Z \/An + lUnH"+i(s) n=0 1 ^ + 2 = ^\/Ajv+i |^'Ujv-H'^'+i(3;) + ujv+i//^'''(x)j This yields that IPnOxU — dxPNu\l,-l <Xm+i {ul\H^iA^)\l.i+ul+,\H%-^{x)\ (B.4) due to the property of seminorms. Moreover, we estimate ul and \H^-'^{x)\l_-^, for k = N,N + l: OO ul! < ill < - Pn-iu\\^ < a~^''N'''\\u\\l, (B.5) by ||rT}. Similarly, -u^^+i < Q-^'^iy'llull^. And <a'^\\H'^''^{x)\\l_i, by Lemma [T2| — l-i/i — 1 ^- — — 1 =Q! Ajv < a Ajv+i, since {H'^'^)^ = 5fejv, for fc £ 2,'^. Simi larly, (B.6) -H'^+iIm-i ^ «"^A^ ,\. Substitute (|B.5l and (|B.6|( into B.4^ , we get IPnOxU - dxPNu\l-l <a~^''~^A*'"''A'i^_|_il|M||r <^2M-2r-l^M-r||^||2^ (B.7) by the fact that \n = 2Na^. Combine jB.2| , |B3 (|B.7^, we arrive the conclusion. and 12 HSM to ID FKE and its application to the NLF problems References [1] M. S. Arulampalam, S. Maskell, N. Gordon and T. Clapp, A tutorial on particle filters for online nonlinear/non- gaussian bayesian tracking, IEEE Trans. Signal Process., 50(2):174-188, 2002. [2] P. Besala, On the existence of a fundamental solution for a parabolic differential equation with unbounded coeffi- cients, Ann. Polonici Math., 29:403-409, 1975. [3] J. Boyd, The rate of convergence of Hermite function series. Math. Comp., 35:1039-1316, 1980. [4] J. Boyd, Asymptotic coefficients of Hermite function se- ries, J. Comput. Phys., 54:382-410, 1984. [5] A. Bensoussan, R. Glowinski and A. Rascanu, Approx- imation of the Zakai equation by the splitting up method, SIAM J. Control Optim., 28: 1420-1431, 1990. [6] A. Bensoussan, R. Glowinski and A. Rascanu, Approx- imation of some stochastic differential equations by the splitting up methods, Appl. Math. Optim., 25:81-106, 1992. [7] T. Duncan, Probability density for diffusion processes with applications to nonlinear filtering theory. Ph. D. thesis, Stanford University, Stanford, CA, 1967. [8] J. Fok, B. Guo and T. Tang, Combined hermite spectral- finite difference method for the fokker-planck equation. Math. Comp., 71(240): 1497-1528, 2001. [9] D. Funaro and O. Kavian, Approximation of some diffu- sion evolution equation in unbounded domains by Hermite function. Math. Comp., 37:597-619, 1991. [10] D. Gottlieb and S. Orszag, Numerical analysis of spectral methods: theory and applications, Soc. In. and Appl. Math., Philadelphia, 1977. [11] B.-Y. Guo, J. Shen and C.-L. Xu, Spectral and pseu- dospectral approximation using Hermite function: Appli- cation in Dirac equation. Adv. Comput. Math., 19:35-55, 2003. [12] I. Gyongy and N. Kiylov, On the splitting-up method and stochastic partial differential equation, Ann. Probab., 31:564-591, 2003. [13] W. E. Hopkins, Jr, Nonlinear filtering of nondegnerate diffusions with unbounded coefficients. Ph. D. disserta- tion. Dep. Elec. Eng., Univ. Maryland, College Park, Nov. 1982. [14] K. Ito, Approximation of the Zakai equation for nonlinear filtering, SIAM J. Control Optim., 34:620-634, 1996. [15] K. Ito and B. Rozovskii, Approximation of the Kushner equation for nonlinear filtering, SIAM J. control Optim., 38:893-915, 2000. [16] S. Lototsky, R. Mikulevicius and B. L. Rozovskii, Nonlin- ear filtering revisited: aspectral approach, SIAM J. Control Optim., 35(2):435-461, 1997. [17] X. Luo and S. S.-T. Yau, Complete Real Time Solution of the General Nonlinear Filtering Problem without Memory, preprint. arXiv: 1208.0962 [18] R. Mortensen, Optimal control of continuous time stochas- tic systems. Ph. D. thesis. University of California, Berke- ley, CA, 1966. [19] N. Nagase, Remarks on nonlinear stochastic partial differ- ential equations: An application of the splitting-up method, SIAM J. Control Optim. 33:1716-1730, 1995. [20] J. W. Schumer and J. P. HoUoway, V/a.sov simulations using velocity-scaled Hermite representations, J. Comp. Phys, 144:626-661, 1998. [21] X.-M. Xiang and Z.-Q. Wang, Generalized Hermite spec- tral method and its applications to problems in unbounded domains, SIAM J. Numer Anal., 48(4): 123 1-1253, 2010. [22] S. T. Yau and S. S.-T. Yau, Real time solution of nonlinear filtering problem without memory 11, SIAM J. Control Optim., 47(l):230-243, 2008. [23] M. Zakai, On the optimal filtering of diffusion processes, Z. Wahrsch. Verw. Gebiete, 11:230-243, 1969. 13 HSM to ID FKE and its application to the NLF problems Start Compute the Her- mite coefficient {Mi,n(Tj)}^=0 the base {H-'^{x)}^^^ Update, i.e. evaluate Uiix,Ti) at +/3}^^o Input Q, 0, and initial data uo Compute E[,x]{0) and Evaluate Ui{x,Ti+i) Evaluate Ui(x, Tj) using {Ui,niTi)}^^o Compute Hermite coefficient {ui,n{Ti)}'^^o under the shifted bases _^ Let/3 = Synchronized with the corresponding part of the off-line data, i.e. the values of {U(Tt+un)H^-P(x)}';^^^ Fig. 2.6. The flowchart of our algorithm, where /3' e {0j}j=o- 14