Research On Orthogonal Non-Negative Locally Linear Embedding And Its Optimization Algorithms

With the development of science and technology, people can contact and get more and more data with increasing scale, such as Internet information, meteorological data and so on. On the one hand, they bring great convenience for society and life, on the other hand they bring challenge. That is how to extract the effective information from large scale data in order to reflect the intrinsical characteristics of the data. As a kind of efficient data processing methods, dimension reduction emerges as the times require. Traditional dimension reduction methods such as principal component analysis, linear discriminant analysis have been widely used in many applications. But they produce negative entries and such negativity often lacks reasonable explanation in practice. Nonnegative matrix factorization(NMF) which restrains nonnegative characteristic gets extensive attention and has a wide application prospect.NMF decomposes a nonnegative matrix m nV R?? into two lower-rank nonnegative factor matrices, i.e. m rW R?? and r nH R??, by minimizing the distance between V and WH. The visual interpretation of nonnegative constraints over W and H is that learning the parts to form a whole. NMF has been widely used in pattern recognition, data mining and computer vision. However, original NMF ignores geometric structure of dataset because high-dimensional data may distribute on the surface of low dimensional manifold. To consider the geometric structure of dataset, researchers propose manifold-regularized NMF model and its extensions. On the basis of previous works, we propose a new manifold-regularized NMF model called orthogonal nonnegative locally linear embedding(ONLLE). We propose two efficient algorithms to optimizing ONLLE. The main works of this thesis includes:(1) Orthogonal nonnegative locally linear embedding(ONLLE). ONLLE assumes that each example embeds in the scope of its nearest neighbors and keeps such relationship of the nearest neighbors in the learned subspace so that it maintains the geometric structure of a dataset. For the purpose of learning parts-based sparse representation, ONLLE explicitly incorporates an orthogonality constraint on the learned basis to keep its spatial locality. We conduct both face recognition and image clustering on some datasets by comparing with other representative NMF methods. The experimental results show that the performance of ONLLE is better than tradiontional algorithms like NMF, NPNMF and GNMF.(2) Fast gradient descent method on Stiefel manifold. The multiplicative update rule(MUR) is a popular algorithm to optimize NMF. But it suffers from the problem of slow-convergence because it intrinsically advances one step along the rescaled negative gradient direction with a constant step size of 1. To accelerate the speed of ONLLE, we search the target of basis matrix on Stiefel manifold and propose MUR of ONLLE on Stiefel manifold. To overcome the disadvantage of MUR, we design an efficient fast gradient descent(FGD) method on Stiefel manifold which accelerates MUR. And the experimental results show that on FGD on Stiefel manifold converges much faster than MUR.(3) Limited-memory fast gradient descent method. FGD has the risk of shrinking to MUR. A multiple step-sizes fast gradient descent(MFGD) method has been proposed for optimizing NMF by searching the optimal step size with multivariate Newton’s method along the rescaled negative gradient direction. However, MFGD has the following two shortcomings: 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 the deficiencies of MFGD, we propose an efficient limited-memory FGD(L-FGD) method. 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. To evaluate the effectiveness of L-FGD, we test its efficiency and clustering performance on two face image datasets including ORL and PIE and two document corpora including Reuters and TDT2. The experimental results show that L-FGD converges significantly faster than MFGD and MUR with nearly the same clustering performance. And the memory cost of L-FGD is much less than that of MFGD.