December  2021, 3(4): 701-727. doi: 10.3934/fods.2021020

Learning landmark geodesics using the ensemble Kalman filter

Department of Mathematics, Imperial College London, South Kensington Campus, London SW7 2AZ, UK

* Corresponding author: Andreas Bock

Received  March 2021 Revised  July 2021 Published  December 2021 Early access  August 2021

We study the problem of diffeomorphometric geodesic landmark matching where the objective is to find a diffeomorphism that, via its group action, maps between two sets of landmarks. It is well-known that the motion of the landmarks, and thereby the diffeomorphism, can be encoded by an initial momentum leading to a formulation where the landmark matching problem can be solved as an optimisation problem over such momenta. The novelty of our work lies in the application of a derivative-free Bayesian inverse method for learning the optimal momentum encoding the diffeomorphic mapping between the template and the target. The method we apply is the ensemble Kalman filter, an extension of the Kalman filter to nonlinear operators. We describe an efficient implementation of the algorithm and show several numerical results for various target shapes.

Citation: Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021, 3 (4) : 701-727. doi: 10.3934/fods.2021020
References:
[1]

M. F. BegM. I. MillerA. Trouvé and L. Younes, Computing large deformation metric mappings via geodesic flows of diffeomorphisms, Int. J. Comput. Vis., 61 (2005), 139-157.  doi: 10.1023/B:VISI.0000043755.93987.aa.

[2]

N. K. Chada, M. A. Iglesias, L. Roininen and A. M. Stuart, Parameterizations for ensemble Kalman inversion, Inverse Problems, 34 (2018), 31pp. doi: 10.1088/1361-6420/aab6d9.

[3]

B. Charlier, J. Feydy, J. A. Glaunès, F.-D. Collin and G. Durif, Kernel operations on the GPU, with autodiff, without memory overflows, preprint, arXiv: 2004.11127.

[4]

C. J. Cotter, S. L. Cotter and F.-X. Vialard, Bayesian data assimilation in shape registration, Inverse Problems, 29 (2013), 21pp. doi: 10.1088/0266-5611/29/4/045011.

[5]

S. L. CotterM. Dashti and A. M. Stuart, Approximation of Bayesian inverse problems for PDEs, SIAM J. Numer. Anal., 48 (2010), 322-345.  doi: 10.1137/090770734.

[6]

P. DupuisU. Grenander and M. I. Miller, Variational problems on flows of diffeomorphisms for image matching, Quart. Appl. Math., 56 (1998), 587-600.  doi: 10.1090/qam/1632326.

[7]

G. Evensen, Sequential data assimilation with a nonlinear quasi-geostrophic model using Monte Carlo methods to forecast error statistics, J. Geophys. Res.-Oceans, 99 (1994), 10143-10162.  doi: 10.1029/94JC00572.

[8]

U. Grenander and M. I. Miller, Computational anatomy: An emerging discipline, Quart. Appl. Math., 56 (1998), 617-694.  doi: 10.1090/qam/1668732.

[9]

U. Grenander and M. I. Miller, Representations of knowledge in complex systems, J. Roy. Statist. Soc. Ser. B, 56 (1994), 549-603.  doi: 10.1111/j.2517-6161.1994.tb02000.x.

[10]

S. J. GreybushE. KalnayT. MiyoshiK. Ide and B. R. Hunt, Balance and ensemble Kalman filter localization techniques, Monthly Weather Review, 139 (2011), 511-522.  doi: 10.1175/2010MWR3328.1.

[11]

D. D. HolmA. Trouvé and L. Younes, The Euler-Poincaré theory of metamorphosis, Quart. Appl. Math., 67 (2009), 661-685.  doi: 10.1090/S0033-569X-09-01134-2.

[12]

M. A. Iglesias, A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems, Inverse Problems, 32 (2016), 45pp. doi: 10.1088/0266-5611/32/2/025002.

[13]

M. A. Iglesias, K. J. H. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2013), 20pp. doi: 10.1088/0266-5611/29/4/045001.

[14]

S. C. Joshi and M. I. Miller, Landmark matching via large deformation diffeomorphisms, IEEE Trans. Image Process., 9 (2000), 1357-1370.  doi: 10.1109/83.855431.

[15]

J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Applied Mathematical Sciences, 160, Springer-Verlag, New York, 2005. doi: 10.1007/b138659.

[16]

R. E. Kalman, A new approach to linear filtering and prediction problems, Trans. ASME Ser. D. J. Basic Engrg., 82 (1960), 35-45.  doi: 10.1115/1.3662552.

[17]

L. KühnelS. Sommer and A. Arnaudon, Differential geometry and stochastic dynamics with deep learning numerics, Appl. Math. Comput., 356 (2019), 411-437.  doi: 10.1016/j.amc.2019.03.044.

[18]

F. Le Gland, V. Monbet and V.-D. Tran, Large sample asymptotics for the ensemble Kalman filter, in The Oxford Handbook of Nonlinear Filtering, Oxford Univ. Press, Oxford, 2011, 598-631.

[19]

J. MaM. I. MillerA. Trouvé and L. Younes, Bayesian template estimation in computational anatomy, NeuroImage, 42 (2008), 252-261.  doi: 10.1016/j.neuroimage.2008.03.056.

[20]

J. MandelL. Cobb and J. D. Beezley, On the convergence of the ensemble Kalman filter, Appl. Math., 56 (2011), 533-541.  doi: 10.1007/s10492-011-0031-2.

[21]

M. I. MillerA. Trouvé and L. Younes, Geodesic shooting for computational anatomy, J. Math. Imaging Vision, 24 (2006), 209-228.  doi: 10.1007/s10851-005-3624-0.

[22]

D. Mumford, Pattern theory: The mathematics of perception, in Proceedings of the International Congress of Mathematicians, Vol. I, Higher Ed. Press, Beijing, 2002,401-422.

[23] D. S. OliverA. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008.  doi: 10.1017/CBO9780511535642.
[24]

A. Paszke, S. Gross, F. Massa, A. Lerer and J. Bradbury, et al., PyTorch: An imperative style, high-performance deep learning library, preprint, arXiv: 1912.01703

[25] S. Reich and C. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.
[26]

Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), 856-869.  doi: 10.1137/0907058.

[27]

C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM J. Numer. Anal., 55 (2017), 1264-1290.  doi: 10.1137/16M105959X.

[28]

T. SchneiderS. LanA. Stuart and J. Teixeira, Earth system modeling 2.0: A blueprint for models that learn from observations and targeted high-resolution simulations, Geophysical Research Letters, 44 (2017), 12396-12417.  doi: 10.1002/2017GL076101.

[29]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numer., 19 (2010), 451-559.  doi: 10.1017/S0962492910000061.

[30]

A. Trouvé, Diffeomorphisms groups and pattern matching in image analysis, Int. J. Comput. Vis., 28 (1998), 213-221.  doi: 10.1023/A:1008001603737.

[31]

A. Trouvé, An infinite dimensional group approach for physics based models in pattern recognition, (1995).

[32]

A. Trouvé and L. Younes, Metamorphoses through Lie group action, Found. Comput. Math., 5 (2005), 173-198.  doi: 10.1007/s10208-004-0128-z.

[33]

R. Van Der Merwe, A. Doucet, N. De Freitas and E. A. Wan, The unscented particle filter, in Advances in Neural Information Processing Systems, 2000,584–590.

[34]

C. R. Vogel, Computational Methods for Inverse Problems, Frontiers in Applied Mathematics, 23, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. doi: 10.1137/1.9780898717570.

[35]

L. Younes, Shapes and Diffeomorphisms, Applied Mathematical Sciences, 171, Springer-Verlag, Berlin, 2010 doi: 10.1007/978-3-642-12055-8.

show all references

References:
[1]

M. F. BegM. I. MillerA. Trouvé and L. Younes, Computing large deformation metric mappings via geodesic flows of diffeomorphisms, Int. J. Comput. Vis., 61 (2005), 139-157.  doi: 10.1023/B:VISI.0000043755.93987.aa.

[2]

N. K. Chada, M. A. Iglesias, L. Roininen and A. M. Stuart, Parameterizations for ensemble Kalman inversion, Inverse Problems, 34 (2018), 31pp. doi: 10.1088/1361-6420/aab6d9.

[3]

B. Charlier, J. Feydy, J. A. Glaunès, F.-D. Collin and G. Durif, Kernel operations on the GPU, with autodiff, without memory overflows, preprint, arXiv: 2004.11127.

[4]

C. J. Cotter, S. L. Cotter and F.-X. Vialard, Bayesian data assimilation in shape registration, Inverse Problems, 29 (2013), 21pp. doi: 10.1088/0266-5611/29/4/045011.

[5]

S. L. CotterM. Dashti and A. M. Stuart, Approximation of Bayesian inverse problems for PDEs, SIAM J. Numer. Anal., 48 (2010), 322-345.  doi: 10.1137/090770734.

[6]

P. DupuisU. Grenander and M. I. Miller, Variational problems on flows of diffeomorphisms for image matching, Quart. Appl. Math., 56 (1998), 587-600.  doi: 10.1090/qam/1632326.

[7]

G. Evensen, Sequential data assimilation with a nonlinear quasi-geostrophic model using Monte Carlo methods to forecast error statistics, J. Geophys. Res.-Oceans, 99 (1994), 10143-10162.  doi: 10.1029/94JC00572.

[8]

U. Grenander and M. I. Miller, Computational anatomy: An emerging discipline, Quart. Appl. Math., 56 (1998), 617-694.  doi: 10.1090/qam/1668732.

[9]

U. Grenander and M. I. Miller, Representations of knowledge in complex systems, J. Roy. Statist. Soc. Ser. B, 56 (1994), 549-603.  doi: 10.1111/j.2517-6161.1994.tb02000.x.

[10]

S. J. GreybushE. KalnayT. MiyoshiK. Ide and B. R. Hunt, Balance and ensemble Kalman filter localization techniques, Monthly Weather Review, 139 (2011), 511-522.  doi: 10.1175/2010MWR3328.1.

[11]

D. D. HolmA. Trouvé and L. Younes, The Euler-Poincaré theory of metamorphosis, Quart. Appl. Math., 67 (2009), 661-685.  doi: 10.1090/S0033-569X-09-01134-2.

[12]

M. A. Iglesias, A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems, Inverse Problems, 32 (2016), 45pp. doi: 10.1088/0266-5611/32/2/025002.

[13]

M. A. Iglesias, K. J. H. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2013), 20pp. doi: 10.1088/0266-5611/29/4/045001.

[14]

S. C. Joshi and M. I. Miller, Landmark matching via large deformation diffeomorphisms, IEEE Trans. Image Process., 9 (2000), 1357-1370.  doi: 10.1109/83.855431.

[15]

J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Applied Mathematical Sciences, 160, Springer-Verlag, New York, 2005. doi: 10.1007/b138659.

[16]

R. E. Kalman, A new approach to linear filtering and prediction problems, Trans. ASME Ser. D. J. Basic Engrg., 82 (1960), 35-45.  doi: 10.1115/1.3662552.

[17]

L. KühnelS. Sommer and A. Arnaudon, Differential geometry and stochastic dynamics with deep learning numerics, Appl. Math. Comput., 356 (2019), 411-437.  doi: 10.1016/j.amc.2019.03.044.

[18]

F. Le Gland, V. Monbet and V.-D. Tran, Large sample asymptotics for the ensemble Kalman filter, in The Oxford Handbook of Nonlinear Filtering, Oxford Univ. Press, Oxford, 2011, 598-631.

[19]

J. MaM. I. MillerA. Trouvé and L. Younes, Bayesian template estimation in computational anatomy, NeuroImage, 42 (2008), 252-261.  doi: 10.1016/j.neuroimage.2008.03.056.

[20]

J. MandelL. Cobb and J. D. Beezley, On the convergence of the ensemble Kalman filter, Appl. Math., 56 (2011), 533-541.  doi: 10.1007/s10492-011-0031-2.

[21]

M. I. MillerA. Trouvé and L. Younes, Geodesic shooting for computational anatomy, J. Math. Imaging Vision, 24 (2006), 209-228.  doi: 10.1007/s10851-005-3624-0.

[22]

D. Mumford, Pattern theory: The mathematics of perception, in Proceedings of the International Congress of Mathematicians, Vol. I, Higher Ed. Press, Beijing, 2002,401-422.

[23] D. S. OliverA. C. Reynolds and N. Liu, Inverse Theory for Petroleum Reservoir Characterization and History Matching, Cambridge University Press, 2008.  doi: 10.1017/CBO9780511535642.
[24]

A. Paszke, S. Gross, F. Massa, A. Lerer and J. Bradbury, et al., PyTorch: An imperative style, high-performance deep learning library, preprint, arXiv: 1912.01703

[25] S. Reich and C. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.
[26]

Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), 856-869.  doi: 10.1137/0907058.

[27]

C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM J. Numer. Anal., 55 (2017), 1264-1290.  doi: 10.1137/16M105959X.

[28]

T. SchneiderS. LanA. Stuart and J. Teixeira, Earth system modeling 2.0: A blueprint for models that learn from observations and targeted high-resolution simulations, Geophysical Research Letters, 44 (2017), 12396-12417.  doi: 10.1002/2017GL076101.

[29]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numer., 19 (2010), 451-559.  doi: 10.1017/S0962492910000061.

[30]

A. Trouvé, Diffeomorphisms groups and pattern matching in image analysis, Int. J. Comput. Vis., 28 (1998), 213-221.  doi: 10.1023/A:1008001603737.

[31]

A. Trouvé, An infinite dimensional group approach for physics based models in pattern recognition, (1995).

[32]

A. Trouvé and L. Younes, Metamorphoses through Lie group action, Found. Comput. Math., 5 (2005), 173-198.  doi: 10.1007/s10208-004-0128-z.

[33]

R. Van Der Merwe, A. Doucet, N. De Freitas and E. A. Wan, The unscented particle filter, in Advances in Neural Information Processing Systems, 2000,584–590.

[34]

C. R. Vogel, Computational Methods for Inverse Problems, Frontiers in Applied Mathematics, 23, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. doi: 10.1137/1.9780898717570.

[35]

L. Younes, Shapes and Diffeomorphisms, Applied Mathematical Sciences, 171, Springer-Verlag, Berlin, 2010 doi: 10.1007/978-3-642-12055-8.

Figure 1.  A matching between landmarks where the geodesics are shown
Figure 2.  Template-target configurations for different values of $ M $. Left to right: 10, 50, 150. Linear interpolation has been used between the landmarks to improve the visualisation
Figure 3.  Log data misfits for $ M = N_E = 50 $ for different values of $ \xi $ using three different targets
Figure 4.  Progression of Algorithm 1 for various targets using $ M = 10 $ and $ N_E = 10 $. Computation times for 50 iterations: 6s for each configuration
Figure 5.  Progression of Algorithm 1 for various targets using $M = 50$ and $N_E = 50$. Computation times for 50 iterations (top to bottom): 2m8s, 2m9s, 1m29s
Figure 6.  Progression of Algorithm 1 for various targets using $ M = 150 $ and $ N_E = 100 $. Computation times for 50 iterations (top to bottom): 5m22s, 5m23s, 5m23s
Figure 7.  Convergence of $ E^k $ where $ M = 10 $
Figure 8.  Convergence of $ E^k $ where $ M = 50 $
Figure 9.  Convergence of $ E^k $ where $ M = 150 $
Figure 10.  Evolution of the relative error $ \mathcal{R}^k $ corresponding to the misfits in Figure 7 where $ M = 10 $
Figure 11.  Evolution of the relative error $ \mathcal{R}^k $ corresponding to the misfits in Figure 8 where $ M = 150 $
Figure 12.  Evolution of the relative error $ \mathcal{R}^k $ corresponding to the misfits in Figure 9 where $ M = 50 $
Table 1.  Global parameters used for Algorithm 1
Variable Value Description
$ n $ 50 Kalman iterations
$ T $ 15 time steps
$ \tau $ 1 landmark size (cf. (2))
$ \epsilon $ 1e-05 absolute error tolerance
Variable Value Description
$ n $ 50 Kalman iterations
$ T $ 15 time steps
$ \tau $ 1 landmark size (cf. (2))
$ \epsilon $ 1e-05 absolute error tolerance
Table 2.  Relative error at the last iteration of algorithm 1 for different values of $ N_E $ for fixed $ M = 10 $. The rows correspond to the configurations in Figure 4
Table 3.  Relative error at the last iteration of algorithm 1 for different values of $ N_E $ for fixed $ M = 50 $. The rows correspond to the configurations in Figure 5
Table 4.  Relative error at the last iteration of algorithm 1 for different values of $ N_E $ for fixed $ M = 150 $. The rows correspond to the configurations in Figure 6
[1]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[2]

Gaohang Yu. A derivative-free method for solving large-scale nonlinear systems of equations. Journal of Industrial and Management Optimization, 2010, 6 (1) : 149-160. doi: 10.3934/jimo.2010.6.149

[3]

Yigui Ou, Wenjie Xu. A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021125

[4]

Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030

[5]

Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 837-850. doi: 10.3934/dcdss.2021045

[6]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[7]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[8]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[9]

Dong-Hui Li, Xiao-Lin Wang. A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 71-82. doi: 10.3934/naco.2011.1.71

[10]

Jun Takaki, Nobuo Yamashita. A derivative-free trust-region algorithm for unconstrained optimization with controlled error. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 117-145. doi: 10.3934/naco.2011.1.117

[11]

Alexander Bibov, Heikki Haario, Antti Solonen. Stabilized BFGS approximate Kalman filter. Inverse Problems and Imaging, 2015, 9 (4) : 1003-1024. doi: 10.3934/ipi.2015.9.1003

[12]

Russell Johnson, Carmen Núñez. The Kalman-Bucy filter revisited. Discrete and Continuous Dynamical Systems, 2014, 34 (10) : 4139-4153. doi: 10.3934/dcds.2014.34.4139

[13]

Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177

[14]

Fabrizio Colombo, Irene Sabadini, Frank Sommen. The inverse Fueter mapping theorem. Communications on Pure and Applied Analysis, 2011, 10 (4) : 1165-1181. doi: 10.3934/cpaa.2011.10.1165

[15]

Jiangfeng Huang, Zhiliang Deng, Liwei Xu. A Bayesian level set method for an inverse medium scattering problem in acoustics. Inverse Problems and Imaging, 2021, 15 (5) : 1077-1097. doi: 10.3934/ipi.2021029

[16]

Neil K. Chada, Claudia Schillings, Simon Weissmann. On the incorporation of box-constraints for ensemble Kalman inversion. Foundations of Data Science, 2019, 1 (4) : 433-456. doi: 10.3934/fods.2019018

[17]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017

[18]

Le Yin, Ioannis Sgouralis, Vasileios Maroulas. Topological reconstruction of sub-cellular motion with Ensemble Kalman velocimetry. Foundations of Data Science, 2020, 2 (2) : 101-121. doi: 10.3934/fods.2020007

[19]

Marc Bocquet, Alban Farchi, Quentin Malartic. Online learning of both state and dynamics using ensemble Kalman filters. Foundations of Data Science, 2021, 3 (3) : 305-330. doi: 10.3934/fods.2020015

[20]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2021, 3 (3) : 371-411. doi: 10.3934/fods.2020018

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]