×

The ML-EM algorithm in continuum: sparse measure solutions. (English) Zbl 1436.62392

Authors’ abstract: Linear inverse problems \(A\mu=y\) with Poisson noise and non-negative unknown \(\mu\geq 0\) are ubiquitous in applications, for instance in positron emission tomography (PET) in medical imaging. The associated maximum likelihood problem is routinely solved using an expectation-maximisation algorithm (ML-EM). This typically results in images which look spiky, even with early stopping. We give an explanation for this phenomenon. We first regard the image \(\mu\) as a measure. We prove that if the measurements \(y\) are not in the cone \(\{A\mu,\mu\geqslant 0\}\), which is typical of low injected dose, likelihood maximisers must be sparse, i.e., typically a sum of point masses. We also show a weak sparsity result for cluster points of ML-EM. On the other hand, in the low noise regime, we prove that cluster points of ML-EM are optimal measures with full support. Finally, we provide concentration bounds for the probability to be in the sparse case, and a set of numerical experiments supporting our claims.

MSC:

62L15 Optimal stopping in statistics
65J22 Numerical solution to inverse problems in abstract spaces
62H35 Image analysis in multivariate analysis
92C55 Biomedical imaging and signal processing
62P10 Applications of statistics to biology and medical sciences; meta analysis
62H30 Classification and discrimination; cluster analysis (statistical aspects)

Software:

ODL; GitHub; MLEM

References:

[1] Adler J, Kohr H and Öktem O 2017 ODL-a Python framework for rapid prototyping in inverse problems R. Inst. Technol.
[2] Baumeister J and Leitão A 2017 Topics in Inverse Problems
[3] Benvenuto F and Piana M 2014 Regularization of multiplicative iterative algorithms with nonnegative constraint Inverse Problems30 035012 · Zbl 1368.65083 · doi:10.1088/0266-5611/30/3/035012
[4] Berend D and Tassa T 2010 Improved bounds on Bell numbers and on moments of sums of random variables Probab. Math. Statistics30 185-205 · Zbl 1230.60014
[5] Bertero M and Boccacci P 1998 Introduction to Inverse Problems in Imaging (Boca Raton, FL: CRC Press) · Zbl 0914.65060 · doi:10.1887/0750304359
[6] Boyd S and Vandenberghe L 2004 Convex Optimization (Cambridge: Cambridge University Press) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[7] Byrne C 1993 Iterative image reconstruction algorithms based on cross-entropy minimization IEEE Trans. Image Process.2 96-103 · doi:10.1109/83.210869
[8] Byrne C 1995 Erratum and addendum to “Iterative image-reconstruction algorithms based on cross-entropy minimization” (New York: Springer)
[9] Byrne C 1996 Iterative reconstruction algorithms based on cross-entropy minimization Image Models (and their Speech Model Cousins) (Berlin: Springer) pp 1-11 · Zbl 0925.62030 · doi:10.1007/978-1-4612-4056-3_1
[10] Cavalcanti Y C, Oberlin T, Dobigeon N, Févotte C, Stute S, Ribeiro M-J and Tauber C 2019 Factor analysis of dynamic PET images: beyond Gaussian noise IEEE Trans. Med. Imag. · doi:10.1109/icassp.2019.8683384
[11] Csiszár I 1984 Information Geometry and Alternating Minimization Procedures Statistics and Decisions vol 1 pp 205-37 · Zbl 0547.60004
[12] Dempster A P, Laird N M and Rubin D B 1977 Maximum likelihood from incomplete data via the EM algorithm J. R. Stat. Soc. Ser. B Methodol.39 1-22 · Zbl 0364.62022 · doi:10.1111/j.2517-6161.1977.tb01600.x
[13] Fessler J A, Clinthome N H and Rogers W L 1993 On complete-data spaces for PET reconstruction algorithms IEEE Trans. Nuc. Sci.40 1055-61 · doi:10.1109/23.256712
[14] Georgiou T T 2005 Solution of the general moment problem via a one-parameter imbedding IEEE Trans. Autom. Control50 811-26 · Zbl 1365.93096 · doi:10.1109/tac.2005.849212
[15] Hinkle J, Szegedi M, Wang B, Salter B and Joshi S 2012 4D CT image reconstruction with diffeomorphic motion model Med. Image Anal.16 1307-16 · doi:10.1016/j.media.2012.05.013
[16] Hudson H M and Larkin R S 1994 Accelerated image reconstruction using ordered subsets of projection data IEEE Trans. Med. Imag.13 601-9 · doi:10.1109/42.363108
[17] Iusem A N 1992 A short convergence proof of the EM algorithm for a specific poisson model Braz. J. Probab. Statistics 57-67 · Zbl 0768.62019
[18] Jacobson M and Fessler J A 2003 Joint estimation of image and deformation parameters in motion-corrected PET 2003 IEEE Nuclear Science Symposium. Conference Record (IEEE Cat. No. 03CH37515)vol 5 (Piscataway, NJ: IEEE) pp 3290-4
[19] Last G and Penrose M 2017 Lectures on the Poisson Process vol 7 (Cambridge: Cambridge University Press) · Zbl 1392.60004 · doi:10.1017/9781316104477
[20] Lucy L B 1974 An iterative technique for the rectification of observed distributions Astron. J.79 745 · doi:10.1086/111605
[21] Mair B, Rao M and Anderson J 1996 Positron emission tomography, Borel measures and weak convergence Inverse Problems12 965 · Zbl 0862.60098 · doi:10.1088/0266-5611/12/6/011
[22] Mardia J, Jiao J, Tánczos E, Nowak R D and Weissman T 2018 Concentration inequalities for the empirical distribution arXiv:1809.06522
[23] Mülthei H 1992 Iterative continuous maximum-likelihood reconstruction method Math. Methods Appl. Sci.15 275-86 · Zbl 0912.65112 · doi:10.1002/mma.1670150405
[24] Mülthei H, Schorr B and Törnig W 1987 On an iterative method for a class of integral equations of the first kind Math. Methods Appl. Sci.9 137-68 · Zbl 0628.65130 · doi:10.1002/mma.1670090112
[25] Mülthei H, Schorr B and Törnig W 1989 On properties of the iterative maximum likelihood reconstruction method Math. Methods Appl. Sci.11 331-42 · Zbl 0667.65099 · doi:10.1002/mma.1670110303
[26] Natterer F and Wübbeling F 2001 Mathematical Methods in Image Reconstruction vol 5 (Philadelphia, PA: SIAM) · Zbl 0974.92016 · doi:10.1137/1.9780898718324
[27] Öktem O, Pouchol C and Verdier O 2019 Spatiotemporal PET reconstruction using ML-EM with learned diffeomorphic deformation in International Workshop on Machine Learning for Medical Image Reconstruction (Berlin: Springer) pp 151-62 · doi:10.1007/978-3-030-33843-5_14
[28] Ollinger J M and Fessler J A 1997 Positron-emission tomography IEEE Signal Process. Mag.14 43-55 · doi:10.1109/79.560323
[29] O’Sullivan F 1995 A study of least squares and maximum likelihood for image reconstruction in positron emission tomography Ann. Statistics 1267-300 · Zbl 0839.62035
[30] Posner E 1975 Random coding strategies for minimum entropy IEEE Trans. Inf. Theory21 388-91 · Zbl 0319.94012 · doi:10.1109/tit.1975.1055416
[31] Pouchol C and Verdier O MLEM Experiment Notebook https://github.com/olivierverdier/mlem_notebook
[32] Qi J and Leahy R M 2006 Iterative reconstruction techniques in emission computed tomography Phys. Med. Biol.51 R541 · doi:10.1088/0031-9155/51/15/r01
[33] Resmerita E, Engl H W and Iusem A N 2007 The expectation-maximization algorithm for ill-posed integral equations: a convergence analysis Inverse Problems23 2575 · Zbl 1282.65173 · doi:10.1088/0266-5611/23/6/019
[34] Richardson W H 1972 Bayesian-based iterative method of image restoration JoSA62 55-9 · doi:10.1364/josa.62.000055
[35] Rudin W 1991 Functional analysis International Series in Pure and Applied Mathematics 2nd edn (New York: McGraw-Hill) · Zbl 0867.46001
[36] Sanov I N 1961 On the probability of large deviations of random variables Sel. Transl. Math. Statistics Probab.1 213-44 · Zbl 0112.10106
[37] Shepp L A and Vardi Y 1982 Maximum likelihood reconstruction for emission tomography IEEE Trans. Med. Imaging1 113-22 · doi:10.1109/tmi.1982.4307558
[38] Silverman B, Jones M, Wilson J and Nychka D 1990 A smoothed EM approach to indirect estimation problems, with particular reference to stereology and emission tomography J. R. Stat. Soc. Ser. B Methodol.52 271-303 · Zbl 0703.62105 · doi:10.1111/j.2517-6161.1990.tb01788.x
[39] Vardi Y, Shepp L and Kaufman L 1985 A statistical model for positron emission tomography J. Am. Stat. Assoc.80 8-20 · Zbl 0561.62094 · doi:10.1080/01621459.1985.10477119
[40] Wong R 2001 Asymptotic Approximations of Integrals vol 34 (Philadelphia, PA: SIAM) · Zbl 1078.41001 · doi:10.1137/1.9780898719260
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.