On the rate of convergence of the image space reconstruction algorithm

Jian Han, Lixing Han, Michael Neumann, Upendra Prasad

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

The Image Space Reconstruction Algorithm (ISRA) of Daube-Witherspoon and Muehllehner is a multiplicative algorithm for solving nonnegative least squares problems. Eg-germont 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 there for hold under more general assumptions than in the work of Archer and Tittering ton who assume that at a minimum point all Lagrange multipliers are zero. We provide numerical examples to illustrate our rate of convergence results and to explain why the ISRA algorithm usually appears to converge slowly. Our work here heuristically justifies why the Lee-Seung algorithm for solving nonnegative matrix factorization problems has a slow rate of convergence.

Original languageEnglish
Pages (from-to)41-58
Number of pages18
JournalOperators and Matrices
Volume3
Issue number1
DOIs
StatePublished - 2009

Keywords

  • ISRA (Image Space Reconstruction Algorithm)
  • Nonnegative least squares
  • Nonnegative matrix factorization
  • Rate of convergence

Fingerprint

Dive into the research topics of 'On the rate of convergence of the image space reconstruction algorithm'. Together they form a unique fingerprint.

Cite this