May  2008, 2(2): 167-185. doi: 10.3934/ipi.2008.2.167

An efficient computational method for total variation-penalized Poisson likelihood estimation

1. 

Department of Mathematical Sciences, University of Montana Missoula, Montana 59812, United States

Received  February 2007 Revised  January 2008 Published  April 2008

Approximating non-Gaussian noise processes with Gaussian models is standard in data analysis. This is due in large part to the fact that Gaussian models yield parameter estimation problems of least squares form, which have been extensively studied both from the theoretical and computational points of view. In image processing applications, for example, data is often collected by a CCD camera, in which case the noise is a Guassian/Poisson mixture with the Poisson noise dominating for a sufficiently strong signal. Even so, the standard approach in such cases is to use a Gaussian approximation that leads to a negative-log likelihood function of weighted least squares type.
    In the Bayesian point-of-view taken in this paper, a negative-log prior (or regularization) function is added to the negative-log likelihood function, and the resulting function is minimized. We focus on the case where the negative-log prior is the well-known total variation function and give a statistical interpretation. Regardless of whether the least squares or Poisson negative-log likelihood is used, the total variation term yields a minimization problem that is computationally challenging. The primary result of this work is the efficient computational method that is presented for the solution of such problems, together with its convergence analysis. With the computational method in hand, we then perform experiments that indicate that the Poisson negative-log likelihood yields a more computationally efficient method than does the use of the least squares function. We also present results that indicate that this may even be the case when the data noise is i.i.d. Gaussian, suggesting that regardless of noise statistics, using the Poisson negative-log likelihood can yield a more computationally tractable problem when total variation regularization is used.
Citation: Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167
References:
[1]

D. P. Bertsekas, On the Goldstein-Levitin-Poljak gradient projection method,, IEEE Transactions on Automatic Control, 21 (1976), 174.  doi: 10.1109/TAC.1976.1101194.  Google Scholar

[2]

Johnathan M. Bardsley and James G. Nagy, Covariance-preconditioned iterative methods for nonnegatively constrained astronomical imaging,, SIAM Journal on Matrix Analysis and Applications, 27 (2006), 1184.  doi: 10.1137/040615043.  Google Scholar

[3]

J. M. Bardsley and C. R. Vogel, A nonnnegatively constrained convex programming method for image reconstruction,, SIAM Journal on Scientific Computing, 25 (2004), 1326.  doi: 10.1137/S1064827502410451.  Google Scholar

[4]

Johnathan M. Bardsley and Aaron Luttman, Total variation-penalized Poisson likelihood estimation for ill-posed problems,, accepted, (2006).   Google Scholar

[5]

P. H. Calamai and J. J. Moré, Projected gradient methods for linearly constrained problems,, Mathematical Programming, 39 (1987), 93.  doi: 10.1007/BF02592073.  Google Scholar

[6]

D. Calvetti, G. Landi, L. Reichel and S. Sgallari, Non-negativity and iterative methods for ill-posed problems,, Inverse Problems, 20 (2004), 1747.  doi: 10.1088/0266-5611/20/6/003.  Google Scholar

[7]

Daniela Calvetti and Erkki Somersalo, A Gaussian hypermodel for recovering blocky objects,, Inverse Problems, 23 (2007), 733.  doi: 10.1088/0266-5611/23/2/016.  Google Scholar

[8]

Torbjørn Eltoft and Taesu Kim, On the multivariate Laplace distribution,, IEEE Signal Processing Letters, 13 (2006), 300.  doi: 10.1109/LSP.2006.870353.  Google Scholar

[9]

J. W. Goodman, "Introduction to Fourier Optics,", 2nd Edition, (1996).   Google Scholar

[10]

M. Green, Statistics of images, the TV algorithm of Rudin-Osher-Fatemi for image denoising, and an improved denoising algorithm,, CAM Report 02-55, (2002), 02.   Google Scholar

[11]

Jinggang Huang and David Mumford, Statistics of natural images and models,, in, (1999), 541.   Google Scholar

[12]

Jari Kaipio and Erkki Somersalo, "Satistical and Computational Inverse Problems,", Applied Mathematical Sciences, (2005).   Google Scholar

[13]

C. T. Kelley, "Iterative Methods for Optimization,", Frontiers in Applied Mathematics, (1999).   Google Scholar

[14]

J. J. Moré and G. Toraldo, On the solution of large quadratic programming problems with bound constraints,, SIAM Journal on Optimization, 1 (1991), 93.  doi: 10.1137/0801008.  Google Scholar

[15]

J. Nagy and Z. Strakoš, Enforcing nonnegativity in image reconstruction algorithms,, Mathematical Modeling, 4121 (2000), 182.   Google Scholar

[16]

J. Nocedal and S. Wright, "Numerical Optimization,", Series in Operations Research. Springer-Verlag, (1999).  doi: 10.1007/b98874.  Google Scholar

[17]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970).   Google Scholar

[18]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[19]

D. L. Snyder, A. M. Hammoud and R. L. White, Image recovery from data acquired with a charge-coupled-device camera,, Journal of the Optical Society of America A, 10 (1993), 1014.  doi: 10.1364/JOSAA.10.001014.  Google Scholar

[20]

C. R. Vogel, Computational methods for inverse problems,, With a foreword by H. T. Banks. Frontiers in Applied Mathematics, (2002).   Google Scholar

[21]

C. R. Vogel and M. E. Oman, Fast, robust total variation-based reconstruction of noisy, blurred images,, IEEE Transactions on Image Processing, 7 (1998), 813.  doi: 10.1109/83.679423.  Google Scholar

show all references

References:
[1]

D. P. Bertsekas, On the Goldstein-Levitin-Poljak gradient projection method,, IEEE Transactions on Automatic Control, 21 (1976), 174.  doi: 10.1109/TAC.1976.1101194.  Google Scholar

[2]

Johnathan M. Bardsley and James G. Nagy, Covariance-preconditioned iterative methods for nonnegatively constrained astronomical imaging,, SIAM Journal on Matrix Analysis and Applications, 27 (2006), 1184.  doi: 10.1137/040615043.  Google Scholar

[3]

J. M. Bardsley and C. R. Vogel, A nonnnegatively constrained convex programming method for image reconstruction,, SIAM Journal on Scientific Computing, 25 (2004), 1326.  doi: 10.1137/S1064827502410451.  Google Scholar

[4]

Johnathan M. Bardsley and Aaron Luttman, Total variation-penalized Poisson likelihood estimation for ill-posed problems,, accepted, (2006).   Google Scholar

[5]

P. H. Calamai and J. J. Moré, Projected gradient methods for linearly constrained problems,, Mathematical Programming, 39 (1987), 93.  doi: 10.1007/BF02592073.  Google Scholar

[6]

D. Calvetti, G. Landi, L. Reichel and S. Sgallari, Non-negativity and iterative methods for ill-posed problems,, Inverse Problems, 20 (2004), 1747.  doi: 10.1088/0266-5611/20/6/003.  Google Scholar

[7]

Daniela Calvetti and Erkki Somersalo, A Gaussian hypermodel for recovering blocky objects,, Inverse Problems, 23 (2007), 733.  doi: 10.1088/0266-5611/23/2/016.  Google Scholar

[8]

Torbjørn Eltoft and Taesu Kim, On the multivariate Laplace distribution,, IEEE Signal Processing Letters, 13 (2006), 300.  doi: 10.1109/LSP.2006.870353.  Google Scholar

[9]

J. W. Goodman, "Introduction to Fourier Optics,", 2nd Edition, (1996).   Google Scholar

[10]

M. Green, Statistics of images, the TV algorithm of Rudin-Osher-Fatemi for image denoising, and an improved denoising algorithm,, CAM Report 02-55, (2002), 02.   Google Scholar

[11]

Jinggang Huang and David Mumford, Statistics of natural images and models,, in, (1999), 541.   Google Scholar

[12]

Jari Kaipio and Erkki Somersalo, "Satistical and Computational Inverse Problems,", Applied Mathematical Sciences, (2005).   Google Scholar

[13]

C. T. Kelley, "Iterative Methods for Optimization,", Frontiers in Applied Mathematics, (1999).   Google Scholar

[14]

J. J. Moré and G. Toraldo, On the solution of large quadratic programming problems with bound constraints,, SIAM Journal on Optimization, 1 (1991), 93.  doi: 10.1137/0801008.  Google Scholar

[15]

J. Nagy and Z. Strakoš, Enforcing nonnegativity in image reconstruction algorithms,, Mathematical Modeling, 4121 (2000), 182.   Google Scholar

[16]

J. Nocedal and S. Wright, "Numerical Optimization,", Series in Operations Research. Springer-Verlag, (1999).  doi: 10.1007/b98874.  Google Scholar

[17]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1970).   Google Scholar

[18]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[19]

D. L. Snyder, A. M. Hammoud and R. L. White, Image recovery from data acquired with a charge-coupled-device camera,, Journal of the Optical Society of America A, 10 (1993), 1014.  doi: 10.1364/JOSAA.10.001014.  Google Scholar

[20]

C. R. Vogel, Computational methods for inverse problems,, With a foreword by H. T. Banks. Frontiers in Applied Mathematics, (2002).   Google Scholar

[21]

C. R. Vogel and M. E. Oman, Fast, robust total variation-based reconstruction of noisy, blurred images,, IEEE Transactions on Image Processing, 7 (1998), 813.  doi: 10.1109/83.679423.  Google Scholar

[1]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547

[2]

Lacramioara Grecu, Constantin Popa. Constrained SART algorithm for inverse problems in image reconstruction. Inverse Problems & Imaging, 2013, 7 (1) : 199-216. doi: 10.3934/ipi.2013.7.199

[3]

Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems & Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008

[4]

Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems & Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031

[5]

Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems & Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064

[6]

Sören Bartels, Marijo Milicevic. Iterative finite element solution of a constrained total variation regularized model problem. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1207-1232. doi: 10.3934/dcdss.2017066

[7]

Adriana González, Laurent Jacques, Christophe De Vleeschouwer, Philippe Antoine. Compressive optical deflectometric tomography: A constrained total-variation minimization approach. Inverse Problems & Imaging, 2014, 8 (2) : 421-457. doi: 10.3934/ipi.2014.8.421

[8]

Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022

[9]

Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems & Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455

[10]

Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems & Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028

[11]

Mila Nikolova. Model distortions in Bayesian MAP reconstruction. Inverse Problems & Imaging, 2007, 1 (2) : 399-422. doi: 10.3934/ipi.2007.1.399

[12]

Ke Chen, Yiqiu Dong, Michael Hintermüller. A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration. Inverse Problems & Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323

[13]

Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191

[14]

Juan Carlos De los Reyes, Carola-Bibiane Schönlieb. Image denoising: Learning the noise model via nonsmooth PDE-constrained optimization. Inverse Problems & Imaging, 2013, 7 (4) : 1183-1214. doi: 10.3934/ipi.2013.7.1183

[15]

Nicolas Lermé, François Malgouyres, Dominique Hamoir, Emmanuelle Thouin. Bayesian image restoration for mosaic active imaging. Inverse Problems & Imaging, 2014, 8 (3) : 733-760. doi: 10.3934/ipi.2014.8.733

[16]

Rinaldo M. Colombo, Francesca Monti. Solutions with large total variation to nonconservative hyperbolic systems. Communications on Pure & Applied Analysis, 2010, 9 (1) : 47-60. doi: 10.3934/cpaa.2010.9.47

[17]

Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems & Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010

[18]

Wenxiang Cong, Ge Wang, Qingsong Yang, Jia Li, Jiang Hsieh, Rongjie Lai. CT image reconstruction on a low dimensional manifold. Inverse Problems & Imaging, 2019, 13 (3) : 449-460. doi: 10.3934/ipi.2019022

[19]

Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems & Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273

[20]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (17)

Other articles
by authors

[Back to Top]