Faster maximum-likelihood reconstruction via explicit conjugation of search directions

Conjugate gradient (CG) is useful to perform maximum-likelihood (ML) reconstruction in positron emission tomography (PET). Although first derived to solve linear systems of equations, CG has been used for non-quadratic objectives. For the log-likelihood of inhomogeneous Poisson processes, the search directions generated by the generic Polak-Ribière formulation are not quite conjugate. We investigated a new CG formulation specific to the ML criterion in PET that preserves the conjugation. We first established a new relationship between the search direction and the image residual. We then derived a new method to generate a basis of search directions conjugate in the ML sense. Conjugation was enforced explicitly by forming the new search direction from a linear combination of the gradient and all the past search directions. The new formulation converges faster to the ML optimal solution. The equivalent of 50 Polak-Ribière iterations is reached in 39 iterations (1.3× faster) and the equivalent of 2000 Polak-Ribière iterations is reached in 451 iterations (4.4× faster). The truncation of the new formulation converges at the same rate as the Polak-Ribière method. The new formulation requires only a negligible amount of extra computation, but very large amounts of memory to store past search directions.