Talk by Dr. Ning Zheng (Researcher at NII)

Title:
Efficient Iterative Solution of Nonnegative Constrained Least Squares Problem and Nonnegative Matrix Factorization and their Applications

Abstract:
Large sparse nonnegative constrained least squares (NNLS) problems arise in many scientific computing and engineering applications, e.g., image restoration and tomography, etc. We propose a new iterative method which uses the CGLS method for the inner iterations and the modulus iterative method for the outer iterations to solve the linear complementarity problem resulting from the Karush–Kuhn–Tucker conditions of the NNLS problem. Theoretical convergence analysis including the optimal choice of the parameter matrix is presented for the proposed method. In addition, the method can be further enhanced by incorporating the active set strategy, which contains two stages; the first stage consists of modulus iterations to identify the active set, while the second stage solves the reduced unconstrained least squares problems only on the inactive variables, and projects the solution into the nonnegative region. Also, we further extend the algorithms for solving nonnegative matrix factorization, which is a low rank matrix approximation problem with nonnegative constraints. Numerical experiments show the efficiency of the proposed methods compared to projection gradient–type methods with fewer iteration steps and less CPU time.

Speaker: Ning Zheng