TY - JOUR

T1 - On large lag smoothing for hidden Markov models

AU - Houssineau, Jeremie

AU - Jasra, Ajay

AU - Singh, Sumeetpal S.

N1 - KAUST Repository Item: Exported on 2021-02-21

PY - 2019/12/3

Y1 - 2019/12/3

N2 - In this article we consider the smoothing problem for hidden Markov models. Given a hidden Markov chain { Xn} n≥ 0 and observations { Yn} n≥ 0, our objective is to compute E[varphi (X0, . ,Xk)| y0, . , yn] for some real-valued, integrable functional varphi and k fixed, k ll n and for some realization (y0, . , yn) of (Y0, . , Yn). We introduce a novel application of the multilevel Monte Carlo method with a coupling based on the Knothe-Rosenblatt rearrangement. We prove that this method can approximate the aforementioned quantity with a mean square error (MSE) of scrO (∈-2) for arbitrary ∈ > 0 with a cost of scrO (∈-2). This is in contrast to the same direct Monte Carlo method, which requires a cost of scrO (n∈-2) for the same MSE. The approach we suggest is, in general, not possible to implement, so the optimal transport methodology of [A. Spantini, D. Bigoni, and Y. Marzouk, J. Mach. Learn. Res., 19 (2018), pp. 2639-2709; M. Parno, T. Moselhy, and Y. Marzouk, SIAM/ASA J. Uncertain. Quantif., 4 (2016), pp. 1160-1190] is used, which directly approximates our strategy. We show that our theoretical improvements are achieved, even under approximation, in several numerical examples.

AB - In this article we consider the smoothing problem for hidden Markov models. Given a hidden Markov chain { Xn} n≥ 0 and observations { Yn} n≥ 0, our objective is to compute E[varphi (X0, . ,Xk)| y0, . , yn] for some real-valued, integrable functional varphi and k fixed, k ll n and for some realization (y0, . , yn) of (Y0, . , Yn). We introduce a novel application of the multilevel Monte Carlo method with a coupling based on the Knothe-Rosenblatt rearrangement. We prove that this method can approximate the aforementioned quantity with a mean square error (MSE) of scrO (∈-2) for arbitrary ∈ > 0 with a cost of scrO (∈-2). This is in contrast to the same direct Monte Carlo method, which requires a cost of scrO (n∈-2) for the same MSE. The approach we suggest is, in general, not possible to implement, so the optimal transport methodology of [A. Spantini, D. Bigoni, and Y. Marzouk, J. Mach. Learn. Res., 19 (2018), pp. 2639-2709; M. Parno, T. Moselhy, and Y. Marzouk, SIAM/ASA J. Uncertain. Quantif., 4 (2016), pp. 1160-1190] is used, which directly approximates our strategy. We show that our theoretical improvements are achieved, even under approximation, in several numerical examples.

UR - http://hdl.handle.net/10754/660989

UR - https://epubs.siam.org/doi/10.1137/18M1198004

UR - http://www.scopus.com/inward/record.url?scp=85076268791&partnerID=8YFLogxK

U2 - 10.1137/18M1198004

DO - 10.1137/18M1198004

M3 - Article

AN - SCOPUS:85076268791

VL - 57

SP - 2812

EP - 2828

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

SN - 0036-1429

IS - 6

ER -