TY - JOUR
T1 - On the rate of convergence of the image space reconstruction algorithm
AU - Han, Jian
AU - Han, Lixing
AU - Neumann, Michael
AU - Prasad, Upendra
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - ISRA (Image Space Reconstruction Algorithm)
KW - Nonnegative least squares
KW - Nonnegative matrix factorization
KW - Rate of convergence
UR - http://www.scopus.com/inward/record.url?scp=77956285552&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77956285552&partnerID=8YFLogxK
U2 - 10.7153/oam-03-02
DO - 10.7153/oam-03-02
M3 - Article
AN - SCOPUS:77956285552
SN - 1846-3886
VL - 3
SP - 41
EP - 58
JO - Operators and Matrices
JF - Operators and Matrices
IS - 1
ER -