Efficient alternating gradient-type algorithms for the approximate non-negative matrix factorization problem

摘要

The approximate non-negative matrix factorization problem (ANMF) seeks to interpret a given set of non-negative data vectors, where the non-negativity is physically meaningful, through the extraction of a sufficiently small set of non-negative "features". Each data vector is then approximated by a non-negative composition of the extracted features. Mathematically, this process is equivalent to approximating a non-negative matrix A by the product of two non-negative matrices, i.e. A ≈ WH, where W ∈ realsm xp and H ∈ reals pxn, and where p is typically chosen to be significantly smaller than m and n.A standard approach for solving the ANMF problem is to use a alternating gradient-type algorithm that keeps the iterates strictly positive. Lee and Seung have proposed what is arguably the most popular of these alternating gradient approaches. In this study we propose several variations of this particular Lee and Seung algorithm with notably improved performance. One of the proposed algorithms optimizes the step-length parameter to achieve greater reduction in the objective function, while another uses different weights derived from the first order necessary conditions of the ANMF problem. The latter has exhibited better empirical performance than the former, while both perform better in practice than the original Lee and Seung algorithm.Theoretical questions concerning the convergence of these feasible alternating gradient-type algorithms have remained unresolved. Hence, from an optimization point of view, these approaches may be seen as unsatisfactory. Our research has contributed to solving these theoretical questions by proving that a class of these algorithms will converge to a continuum, and in specific cases, to a KKT point. These convergence results are applicable to multiple variations of the popular Lee and Seung algorithm.A low-rank Singular Value Decomposition (SVD) of a given matrix A is an optimal approximation under the Frobenius norm whose fundamental subspaces are most relevant within the given measure. In this study we utilize these subspaces to produce a compact reformulation of the ANMF problem to a lower dimensional optimization problem. We introduce an alternating algorithmic approach for this reformulation that is extremely efficient and competitive when producing a low rank ANMF.