Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Linear Inverse Problems Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

EM Algorithms

verfasst von : Charles Byrne, Paul P. B. Eggermont

Erschienen in: Handbook of Mathematical Methods in Imaging

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Expectation-maximization algorithms, or em algorithms for short, are iterative algorithms designed to solve maximum likelihood estimation problems. The general setting is that one observes a random sample Y 1, Y 2, …, Y n of a random variable Y whose probability density function (pdf) \(f(\,\cdot \,\vert \,x_{o})\) with respect to some (known) dominating measure is known up to an unknown “parameter” x o . The goal is to estimate x o and, one might add, to do it well. In this chapter, that means to solve the maximum likelihood problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Duality and Convex Programming
Nächstes Kapitel EM Algorithms from a Non-stochastic Perspective
Literatur
1.
Aronszajn, N., Smith, K.T.: Theory of Bessel potentials. I. Ann. Inst. Fourier (Grenoble) 11, 385–475 (1961). www.​numdam.​org
2.
3.
Bardsley, J.M., Luttman, A.: Total variation-penalized Poisson likelihood estimation for ill-posed problems. Adv. Comput. Math. 31, 35–39 (2009)CrossRefMATHMathSciNet
4.
Bertero, M., Bocacci, P., Desiderá, G., Vicidomini, G.: Image de-blurring with Poisson data: from cells to galaxies. Inverse Probl. 25(123006), 26 (2009)
5.
Browne, J., De Pierro, A.R.: A row-action alternative to the EM algorithm for maximizing likelihoods in emission tomography. IEEE Trans. Med. Imaging 15, 687–699 (1996)CrossRef
6.
Brune, C., Sawatzky, A., Burger, M.: Bregman-EM-TV methods with application to optical nanoscopy. In: Second International Conference on Scale Space and Variational Methods in Computer Vision, Voss. Lecture Notes in Computer Science, vol. 5567, pp. 235–246. Springer, Berlin (2009)
7.
Byrne, C.L.: Iterative image reconstruction algorithms based on cross-entropy minimization. IEEE Trans. Image Process. 2, 96–103 (1993)CrossRef
8.
Byrne, C.L.: Block-iterative methods for image reconstruction from projections. IEEE Trans. Image Process. 5, 792–794 (1996)CrossRef
9.
Byrne, C.L.: Accelerating the EMML algorithm and related iterative algorithms by rescaled block-iterative methods. IEEE Trans. Image Process. 7, 792–794 (1998)CrossRefMathSciNet
10.
Byrne, C.L.: Likelihood maximization for list-mode emission tomographic image reconstruction. IEEE Trans. Med. Imaging 20, 1084–1092 (2001)CrossRef
11.
Byrne, C.L.: Choosing parameters in block-iterative or ordered subset reconstruction algorithms. IEEE Trans. Image Process. 14, 321–327 (2005)CrossRefMathSciNet
12.
Byrne, C.L.: Signal Processing: A Mathematical Approach. AK Peters, Wellesley (2005)
13.
Byrne, C.L.: Applied Iterative Methods. AK Peters, Wellesley (2008)MATH
14.
Byrne, C.L., Fiddy, M.A.: Images as power spectra; reconstruction as a Wiener filter approximation. Inverse Probl. 4, 399–409 (1988)CrossRefMATHMathSciNet
15.
Cao, Y.u., Eggermont, P.P.B., Terebey, S.: Cross Burg entropy maximization and its application to ringing suppression in image reconstruction. IEEE Trans. Image Process. 8, 286–292 (1999)
16.
Censor, Y., Eggermont, P.P.B., Gordon, D.: Strong under relaxation in Kaczmarz’s method for inconsistent systems. Numer. Math. 41, 83–92 (1983)CrossRefMATHMathSciNet
17.
Censor, Y., Lent, A.H.: Optimization of “log x” entropy over linear equality constraints. SIAM J. Control. Optim. 25, 921–933 (1987)CrossRefMATHMathSciNet
18.
Censor, Y., Segman, J.: On block-iterative entropy maximization. J. Inf. Optim. Sci. 8, 275–291 (1987)MATHMathSciNet
19.
20.
21.
Crowther, R.A., DeRosier, D.J., Klug, A.: The reconstruction of three-dimensional structure from projections and its application to electron microscopy. Proc. R. Soc. Lond. A Math. Phys. Sci. 317(3), 19–340 (1971)
22.
Csiszár, I.: I-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3, 146–158 (1975)CrossRefMATH
23.
Csiszár, I., Tusnády, G.: Information geometry and alternating minimization procedures. Stat. Decis. 1(Supplement 1), 205–237 (1984)
24.
Daley, D.J., Vere-Jones, D.: An Introduction to the Theory of Point Processes. Springer, New York (2003)MATH
25.
26.
Daube-Witherspoon, M.E., Muehllehner, G.: An iterative space reconstruction algorithm suitable for volume ECT. IEEE Trans. Med. Imaging 5, 61–66 (1986)CrossRef
27.
Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. B 37, 1–38 (1977)MathSciNet
28.
De Pierro, A.R.: On the convergence of the iterative image space reconstruction algorithm for volume ECT. IEEE Trans. Med. Imaging 6, 174–175 (1987)CrossRef
29.
De Pierro, A.R.: A modified expectation maximization algorithm for penalized likelihood estimation in emission tomography. IEEE Trans. Med. Imaging 14, 132–137 (1995)CrossRef
30.
De Pierro, A., Yamaguchi, M.: Fast EM-like methods for maximum a posteriori estimates in emission tomography. Trans. Med. Imaging 20, 280–288 (2001)CrossRef
31.
Dey, N., Blanc-Ferraud, L., Zimmer, Ch., Roux, P., Kam, Z., Olivo-Martin, J.-Ch., Zerubia, J.: Richardson-Lucy algorithm with total variation regularization for 3D confocal microscope deconvolution. Microsc. Res. Tech. 69, 260–266 (2006)CrossRef
32.
Duijster, A., Scheunders, P., De Backer, S.: Wavelet-based EM algorithm for multispectral-image restoration. IEEE Trans. Geosci. Remote Sens. 47, 3892–3898 (2009)CrossRef
33.
34.
Eggermont, P.P.B.: Nonlinear smoothing and the EM algorithm for positive integral equations of the first kind. Appl. Math. Optim. 39, 75–91 (1999)CrossRefMATHMathSciNet
35.
Eggermont, P.P.B., Herman, G.T., Lent, A.H.: Iterative algorithms for large partitioned linear systems with applications to image reconstruction. Linear Algebra Appl. 40, 37–67 (1981)CrossRefMATHMathSciNet
36.
Eggermont, P.P.B., LaRiccia, V.N.: Smoothed maximum likelihood density estimation for inverse problems. Ann. Stat. 23, 199–220 (1995)CrossRefMATHMathSciNet
37.
Eggermont, P.P.B., LaRiccia, V.N.: Maximum penalized likelihood estimation and smoothed EM algorithms for positive integral equations of the first kind. Numer. Funct. Anal. Optim. 17, 737–754 (1997)CrossRefMathSciNet
38.
Eggermont, P.P.B., LaRiccia, V.N.: On EM-like algorithms for minimum distance estimation. Manuscript, University of Delaware (1998)
39.
Eggermont, P.P.B., LaRiccia, V.N.: Maximum Penalized Likelihood Estimation, I: Density Estimation. Springer, New York (2001)
40.
41.
Fessler, J.A., Ficaro, E.P., Clinthorne, N.H., Lange, K.: Grouped coordinate ascent algorithms for penalized log-likelihood transmission image reconstruction. IEEE Trans. Med. Imaging 16, 166–175 (1997)CrossRef
42.
Fessler, J.A., Hero, A.O.: Penalized maximum-likelihood image reconstruction using space-alternating generalized EM algorithms. IEEE Trans. Image Process. 4, 1417–1429 (1995)CrossRef
43.
Figueiredo, M.A.T., Nowak, R.D.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12, 906–916 (2003)CrossRefMATHMathSciNet
44.
Frank, J.: Three-Dimensional Electron Microscopy of Macromolecular Assemblies, 2nd edn. Oxford University Press, New York (2006)CrossRef
45.
Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984)CrossRefMATH
46.
Geman, S., McClure, D.E.: Bayesian image analysis, an application to single photon emission tomography. In: Proceedings of the Statistical Computing Section, Las Vegas, pp. 12–18. American Statistical Association (1985)
47.
Good, I.J.: A nonparametric roughness penalty for probability densities. Nature 229, 29–30 (1971)
48.
Gordon, R., Bender, R., Herman, G.T.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29, 471–482 (1970)CrossRef
49.
Green, P.J.: Bayesian reconstructions from emission tomography data using a modified EM algorithm. IEEE Trans. Med. Imaging 9, 84–93 (1990)CrossRef
50.
Guillaume, M., Melon, P., Réfrégier, P.: Maximum-likelihood estimation of an astronomical image from a sequence at low photon levels. J. Opt. Soc. Am. A 15, 2841–2848 (1998)CrossRef
51.
Haltmeier, M., Leitão, A., Resmerita, E.: On regularization methods of EM-Kaczmarz type. Inverse Probl. 25(075008), 17 (2009)
52.
53.
Hartley, H.O.: Maximum likelihood estimation from incomplete data. Biometrics 14, 174–194 (1958)CrossRefMATH
54.
Hebert, T., Leahy, R.: A generalized EM algorithm for 3-D Bayesian reconstruction from Poisson data using Gibbs priors. IEEE Trans. Med. Imaging 8, 194–202 (1989)CrossRef
55.
Herman, G.T.: Fundamentals of Computerized Tomography: Image Reconstruction from Projections. Springer, New York (2009)CrossRef
56.
Herman, G.T., Meyer, L.B.: Algebraic reconstruction techniques can be made computationally efficient. IEEE Trans. Med. Imaging 12, 600–609 (1993)CrossRef
57.
Holte, S., Schmidlin, P., Lindén, A., Rosenqvist, G., Eriksson, L.: Iterative image reconstruction for positron emission tomography: a study of convergence and quantitation problems. IEEE Trans. Nucl. Sci. 37, 629–635 (1990)CrossRef
58.
Horváth, I., Bagoly, Z., Balász, L.G., de Ugarte Postigo, A., Veres, P., Mészáros, A.: Detailed classification of Swift’s Gamma-ray bursts. J. Astrophys. 713, 552–557 (2010)CrossRef
59.
Hudson, H.M., Larkin, R.S.: Accelerated image reconstruction using ordered subsets of projection data. IEEE Trans. Med. Imaging 13, 601–609 (1994)CrossRef
60.
Kamphuis, C., Beekman, F.J., Viergever, M.A.: Evaluation of OS-EM vs. EM-ML for 1D, 2D and fully 3D SPECT reconstruction. IEEE Trans. Nucl. Sci. 43, 2018–2024 (1996)
61.
Kondor, A.: Method of convergent weights – an iterative procedure for solving Fredholm’s integral equations of the first kind. Nucl. Instrum. Methods 216, 177–181 (1983)CrossRef
62.
Lange, K.: Convergence of EM image reconstruction algorithms with Gibbs smoothing. IEEE Trans. Med. Imaging 9, 439–446 (1990)CrossRef
63.
Lange, K., Bahn, M., Little, R.: A theoretical study of some maximum likelihood algorithms for emission and transmission tomography. IEEE Trans. Med. Imaging 6, 106–114 (1987)CrossRef
64.
Lange, K., Carson, R.: EM reconstruction algorithms for emission and transmission tomography. J. Comput. Assist. Tomogr. 8, 306–316 (1984)
65.
66.
Levitan, E., Chan, M., Herman, G.T.: Image-modeling Gibbs priors. Graph. Models Image Process. 57, 117–130 (1995)CrossRef
67.
Lewitt, R.M., Muehllehner, G.: Accelerated iterative reconstruction in PET and TOFPET. IEEE Trans. Med. Imaging 5, 16–22 (1986)CrossRef
68.
Liu, C., Rubin, H.: The ECME algorithm: a simple extension of EM and ECM with faster monotone convergence. Biometrika 81, 633–648 (1994)CrossRefMATHMathSciNet
69.
Llacer, J., Veklerov, E.: Feasible images and practical stopping rules for iterative algorithms in emission tomography. IEEE Trans. Med. Imaging 8, 186–193 (1989)CrossRef
70.
Lucy, L.B.: An iterative technique for the rectification of observed distributions. Astron. J. 79, 745–754 (1974)CrossRef
71.
McLachlan, G.J., Krishnan, T.: The EM Algorithm and Its Extensions. Wiley, Hoboken (2008)CrossRef
72.
Meidunas, E.: Re-scaled block iterative expectation maximization maximum likelihood (RBI-EMML) abundance estimation and sub-pixel material identification in hyperspectral imagery. MS thesis, Department of Electrical Engineering, University of Massachusetts Lowell (2001)
73.
Miller, M.I., Roysam, B.: Bayesian image reconstruction for emission tomography incorporating Good’s roughness prior on massively parallel processors. Proc. Natl. Acad. Sci. U.S.A. 88, 3223–3227 (1991)CrossRef
74.
Mülthei, H.N., Schorr, B.: On an iterative method for a class of integral equations of the first kind. Math. Methods Appl. Sci. 9, 137–168 (1987)CrossRefMATHMathSciNet
75.
Mülthei, H.N., Schorr, B.: On properties of the iterative maximum likelihood reconstruction method. Math. Methods Appl. Sci. 11, 331–342 (1989)CrossRefMATHMathSciNet
76.
Nielsen, S.F.: The stochastic EM algorithm: estimation and asymptotic results. Bernoulli 6, 457–489 (2006)CrossRef
77.
Parra, L., Barrett, H.: List-mode likelihood: EM algorithm and image quality estimation demonstrated on 2-D PET. IEEE Trans. Med. Imaging 17, 228–235 (1998)CrossRef
78.
Penczek, P., Zhu, J., Schroeder, R., Frank, J.: Three-dimensional reconstruction with contrast transfer function compensation. Scanning Microsc. 11, 147–154 (1997)
79.
80.
Resmerita, E., Engl, H.W., Iusem, A.N.: The expectation-maximization algorithm for ill-posed integral equations: a convergence analysis. Inverse Probl. 23, 2575–2588 (2007)CrossRefMATHMathSciNet
81.
Richardson, W.H.: Bayesian based iterative method of image restoration. J. Opt. Soc. Am. 62, 55–59 (1972)CrossRef
82.
Rockmore, A., Macovski, A.: A maximum likelihood approach to emission image reconstruction from projections. IEEE Trans. Nucl. Sci. 23, 1428–1432 (1976)CrossRef
83.
Scheres, S.H.W., Gao, H.X., Valle, M., Herman, G.T., Eggermont, P.P.B., Frank, J., Carazo, J.-M.: Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization. Nat. Methods 4, 27–29 (2007)CrossRef
84.
Scheres, S.H.W., Núñez-Ramírez, R., Gómez-Llorente, Y., San Martín, C., Eggermont, P.P.B., Carazo, J.-M.: Modeling experimental image formation for likelihood-based classification of electron microscopy. Structure 15, 1167–1177 (2007)CrossRef
85.
Scheres, S.H.W., Valle, M., Núñez, R., Sorzano, C.O.S., Marabini, R., Herman, G.T., Carazo, J.-M.: Maximum-likelihood multi-reference refinement for electron microscopy images. J. Mol. Biol. 348, 139–149 (2005)CrossRef
86.
Schmidlin, P.: Iterative separation of tomographic scintigrams. Nuklearmedizin 11, 1–16 (1972)
87.
Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21, 193–199 (2010)CrossRef
88.
Shepp, L.A., Vardi, Y.: Maximum likelihood reconstruction in emission tomography. IEEE Trans. Med. Imaging 1, 113–122 (1982)CrossRef
89.
Sigworth, F.J.: A maximum-likelihood approach to single-particle image refinement. J. Struct. Biol. 122, 328–339 (1998)CrossRef
90.
Silverman, B.W., Jones, M.C., Wilson, J.D., Nychka, D.W.: A smoothed EM algorithm approach to indirect estimation problems, with particular reference to stereology and emission tomography (with discussion). J. R. Stat. Soc. B 52, 271–324 (1990)MATHMathSciNet
91.
Sun, Y., Walker, J.G.: Maximum likelihood data inversion for photon correlation spectroscopy. Meas. Sci. Technol. 19(115302), 8 (2008)
92.
Tanaka, E., Kudo, H.: Optimal relaxation parameters of DRAMA (dynamic RAMLA) aiming at one-pass image reconstruction for 3D-PET. Phys. Med. Biol. 55, 2917–2939 (2010)CrossRef
93.
Tarasko, M.Z.: On a method for solution of the linear system with stochastic matrices (in Russian), Report Physics and Energetics Institute, Obninsk PEI-156 (1969)
94.
95.
van der Sluis, A., van der Vorst, H.A.: SIRT- and CG-type methods for the iterative solution of sparse linear least-squares problems. Linear algebra in image reconstruction from projections. Linear Algebra Appl. 130, 257–303 (1990)MATH
96.
Vardi, Y., Shepp, L.A., Kaufman, L.: A statistical model for positron emission tomography (with discussion). J. Am. Stat. Assoc. 80, 8–38 (1985)CrossRefMATHMathSciNet
97.
Wernick, M., Aarsvold, J.: Emission Tomography: The Fundamentals of PET and SPECT. Elsevier Academic, San Diego (2004)
98.
Wu, C.F.J.: On the convergence properties of the EM algorithm. Ann. Stat. 11, 95–103 (1983)CrossRefMATH
99.
Yu, S., Latham, G.A., Anderssen, R.S.: Stabilizing properties of maximum penalized likelihood estimation for additive Poisson regression. Inverse Probl. 10, 1199–1209 (1994)CrossRefMATHMathSciNet
100.
Yuan, J., Yu, J.: Median-prior tomography reconstruction combined with nonlinear anisotropic diffusion filtering. J. Opt. Soc. Am. A 24, 1026–1033 (2007)CrossRef
Metadaten
Titel
EM Algorithms
verfasst von
Charles Byrne
Paul P. B. Eggermont
Copyright-Jahr
2015
Verlag
Springer New York
Buch
Handbook of Mathematical Methods in Imaging

Print ISBN: 978-1-4939-0789-2

Electronic ISBN: 978-1-4939-0790-8

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-1-4939-0790-8_8