title: Limited-memory fast gradient descent method for graph regularized nonnegative matrix factorization.
abstract: Graph regularized nonnegative matrix factorization (GNMF) decomposes a nonnegative data matrix X[Symbol:see text]R(m x n) to the product of two lower-rank nonnegative factor matrices, i.e.,W[Symbol:see text]R(m x r) and H[Symbol:see text]R(r x n) (r < min {m,n}) and aims to preserve the local geometric structure of the dataset by minimizing squared Euclidean distance or Kullback-Leibler (KL) divergence between X and WH. The multiplicative update rule (MUR) is usually applied to optimize GNMF, but it suffers from the drawback of slow-convergence because it intrinsically advances one step along the rescaled negative gradient direction with a non-optimal step size. Recently, a multiple step-sizes fast gradient descent (MFGD) method has been proposed for optimizing NMF which accelerates MUR by searching the optimal step-size along the rescaled negative gradient direction with Newton's method. However, the computational cost of MFGD is high because 1) the high-dimensional Hessian matrix is dense and costs too much memory; and 2) the Hessian inverse operator and its multiplication with gradient cost too much time. To overcome these deficiencies of MFGD, we propose an efficient limited-memory FGD (L-FGD) method for optimizing GNMF. In particular, we apply the limited-memory BFGS (L-BFGS) method to directly approximate the multiplication of the inverse Hessian and the gradient for searching the optimal step size in MFGD. The preliminary results on real-world datasets show that L-FGD is more efficient than both MFGD and MUR. To evaluate the effectiveness of L-FGD, we validate its clustering performance for optimizing KL-divergence based GNMF on two popular face image datasets including ORL and PIE and two text corpora including Reuters and TDT2. The experimental results confirm the effectiveness of L-FGD by comparing it with the representative GNMF solvers.
authors.affiliation: National Key Laboratory of Parallel and Distributed Processing, School of Computer Science, National University of Defense Technology, Changsha, Hunan, China.
authors.forename: Naiyang
authors.initials: N
authors.lastname: Guan
authors.forename: Lei
authors.initials: L
authors.lastname: Wei
authors.forename: Zhigang
authors.initials: Z
authors.lastname: Luo
authors.forename: Dacheng
authors.initials: D
authors.lastname: Tao
mesh_terms: D000465:Algorithms; D003627:Data Interpretation, Statistical; D016206:Databases, Bibliographic; D016208:Databases, Factual; D005145:Face / Q000033:anatomy & histology; D006801:Humans; D010363:Pattern Recognition, Automated / Q000706:statistics & numerical data*; D014584:User-Computer Interface