On the rate of convergence of the image space reconstruction algorithm

Abstract

The Image Space Reconstruction Algorithm (ISRA) of Daube-Witherspoon and Muehllehner is a multiplicative algorithm for solving nonnegative least squares problems. Eggermont has proved the global convergence of this algorithm. In this paper, we analyze its rate of convergence. We show that if at the minimum the strict complementarity condition is satisfied and the reduced Hessian matrix is positive definite, then the ISRA algorithm which converges to it does so at a linear rate of convergence. If, however, the ISRA algorithm converges to a minimum which does not satisfy the strict complementarity condition, then the rate of convergence of the algorithm can degenerate to being sublinear. Our results here therefor hold under more general assumptions than in the work of Archer and Titterington who assume that at a minimum point all Lagrange multipliers are zero.