Efficient Nonnegative Matrix Factorization via projected Newton method

Nonnegative Matrix Factorization (NMF) is a popular decomposition technique in pattern analysis, document clustering, image processing and related fields. In this paper, we propose a fast NMF algorithm via Projected Newton Method (PNM). First, we propose PNM to efficiently solve a nonnegative least squares problem, which achieves a quadratic convergence rate under appropriate assumptions. Second, in the framework of an alternating optimization method, we adopt PNM as an essential subroutine to efficiently solve the NMF problem. Moreover, by exploiting the low rank assumption of NMF, we make PNM very suitable for solving NMF efficiently. Empirical studies on both synthetic and real-world (text and image) data demonstrate that PNM is quite efficient to solve NMF compared with several state of the art algorithms.     

Robust embedded projective nonnegative matrix factorization for image analysis and feature extraction

Nonnegative matrix factorization (NMF) is an unsupervised learning method for decomposing high-dimensional nonnegative data matrices and extracting basic and intrinsic features. Since image data are described and stored as nonnegative matrices, the mining and analysis process usually involves the use of various NMF strategies. NMF methods have well-known applications in face recognition, image reconstruction, handwritten digit recognition, image denoising and feature extraction. Recently, several projective NMF (P-NMF) methods based on positively constrained projections have been proposed and were found to perform better than the standard NMF approach in some aspects. However, some drawbacks still affect the existing NMF and P-NMF algorithms; these include dense factors, slow convergence, learning poor local features, and low reconstruction accuracy. The aim of this paper is to design algorithms that address the aforementioned issues. In particular, we propose two embedded P-NMF algorithms: the first method combines the alternating least squares (ALS) algorithm with the P-NMF update rules of the Frobenius norm and the second one embeds ALS with the P-NMF update rule of the Kullback–Leibler divergence. To assess the performances of the proposed methods, we conducted various experiments on four well-known data sets of faces. The experimental results reveal that the proposed algorithms outperform other related methods by providing very sparse factors and extracting better localized features. In addition, the empirical studies show that the new methods provide highly orthogonal factors that possess small entropy values.     

Combined new nonnegative matrix factorization algorithms with two-dimensional nonnegative matrix factorization for image processing

In recent years, nonnegative matrix factorization (NMF) has attracted significant amount of attentions in image processing, text mining, speech processing and related fields. Although NMF has been applied in several application successfully, its simple application on image processing has a few caveats. For example, NMF costs considerable computational resources when performing on large databases. In this paper, we propose two enhanced NMF algorithms for image processing to save the computational costs. One is modified rank-one residue iteration (MRRI) algorithm , the other is element-wisely residue iteration (ERI) algorithm. Here we combine CAPG (a NMF algorithm proposed by Lin), MRRI and ERI with two-dimensional nonnegative matrix factorization (2DNMF) for image processing. The main difference between NMF and 2DNMF is that the former first aligns images into one-dimensional (1D) vectors and then represents them with a set of 1D bases, while the latter regards images as 2D matrices and represents them with a set of 2D bases. The three combined algorithms are named CAPG-2DNMF, MRRI-2DNMF and ERI-2DNMF. The computational complexity and convergence analyses of proposed algorithms are also presented in this paper. Three public databases are used to test the three NMF algorithms and the three combinations, the results of which show the enhancement performance of our proposed algorithms (MRRI and ERI algorithms) over the CAPG algorithm. MRRI and ERI have similar performance. The three combined algorithms have better image reconstruction quality and less running time than their corresponding 1DNMF algorithms under the same compression ratio. We also do some experiments on a real-captured image database and get similar conclusions.     

Extended HALS algorithm for nonnegative Tucker decomposition and its applications for multiway analysis and classification

Analysis of high dimensional data in modern applications, such as neuroscience, text mining, spectral analysis, chemometrices naturally requires tensor decomposition methods. The Tucker decompositions allow us to extract hidden factors (component matrices) with different dimension in each mode, and investigate interactions among various modalities. The alternating least squares (ALS) algorithms have been confirmed effective and efficient in most of tensor decompositions, especially Tucker with orthogonality constraints. However, for nonnegative Tucker decomposition (NTD), standard ALS algorithms suffer from unstable convergence properties, demand high computational cost for large scale problems due to matrix inverse, and often return suboptimal solutions. Moreover they are quite sensitive with respect to noise, and can be relatively slow in the special case when data are nearly collinear. In this paper, we propose a new algorithm for nonnegative Tucker decomposition based on constrained minimization of a set of local cost functions and hierarchical alternating least squares (HALS). The developed NTD-HALS algorithm sequentially updates components, hence avoids matrix inverse, and is suitable for large-scale problems. The proposed algorithm is also regularized with additional constraint terms such as sparseness, orthogonality, smoothness, and especially discriminant. Extensive experiments confirm the validity and higher performance of the developed algorithm in comparison with other existing algorithms.     

Spatially-weighted nonnegative matrix factorization with application to temporal psychovisual modulation

Nonnegative Matrix Factorization (NMF), which decomposes a target matrix into the product of two matrices with nonnegative elements, has been widely used in various fields of signal processing. In visual signal processing, the spatially nonuniformed distribution of perceptually meaningful information in image and video frames calls for a kind of Spatially-Weighted NMF (swNMF) that applies location dependent weights into the decomposition problem. In this paper we introduce swNMF solution based on the hierarchical alternating least squares (HALS) approach. Then we exemplify its application to a new information display diagram named temporal psychovisual modulation (TPVM) with comparison with traditional HALS method and baseline algorithm of multiplicative update (MU).     

Solving non-negative matrix factorization by alternating least squares with a modified strategy

Non-negative matrix factorization (NMF) is a method to obtain a representation of data using non-negativity constraints. A popular approach is alternating non-negative least squares (ANLS). As is well known, if the sequence generated by ANLS has at least one limit point, then the limit point is a stationary point of NMF. However, no evdience has shown that the sequence generated by ANLS has at least one limit point. In order to overcome this shortcoming, we propose a modified strategy for ANLS in this paper. The modified strategy can ensure the sequence generated by ANLS has at least one limit point, and this limit point is a stationary point of NMF. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

Initialization enhancer for non-negative matrix factorization

Non-negative matrix factorization (NMF), proposed recently by Lee and Seung, has been applied to many areas such as dimensionality reduction, image classification image compression, and so on. Based on traditional NMF, researchers have put forward several new algorithms to improve its performance. However, particular emphasis has to be placed on the initialization of NMF because of its local convergence, although it is usually ignored in many documents. In this paper, we explore three initialization methods based on principal component analysis (PCA), fuzzy clustering and Gabor wavelets either for the consideration of computational complexity or the preservation of structure. In addition, the three methods develop an efficient way of selecting the rank of the NMF in low-dimensional space.     

PARAFAC algorithms for large-scale problems

Parallel factor analysis (PARAFAC) is a tensor (multiway array) factorization method which allows to find hidden factors (component matrices) from a multidimensional data. Most of the existing algorithms for the PARAFAC, especially the alternating least squares (ALS) algorithm need to compute Khatri-Rao products of tall factors and multiplication of large matrices, and due to this require high computational cost and large memory and are not suitable for very large-scale-problems. Hence, PARAFAC for large-scale data tensors is still a challenging problem. In this paper, we propose a new approach based on a modified ALS algorithm which computes Hadamard products, instead Khatri-Rao products, and employs relatively small matrices. The new algorithms are able to process extremely large-scale tensors with billions of entries. Extensive experiments confirm the validity and high performance of the developed algorithm in comparison with other well-known algorithms.     

三维非负矩阵因子分解代谢组学数据解析

多维数据解析方法越来越引起人们的重视,非负矩阵因子分解算法已较广泛地用于图像分析。基于PARAFAC模型,将非负矩阵因子分解算法拓展为三维非负矩阵因子分解算法(three dimension non-negative matrix factorization,NMF3)。其原理简明,算法易于执行。与基于向量计算的其他三维化学计量学算法不同,NMF3基于矩阵计算单个元素,所以不必将三维数据平铺处理,就可直接解析,为三维数据解析研究提供了一种全新的思路和方法。应用NMF3解析模拟三维数据和代谢组学数据,结果令人满意。     

Algorithms and applications for approximate nonnegative matrix factorization

The development and use of low-rank approximate nonnegative matrix factorization (NMF) algorithms for feature extraction and identification in the fields of text mining and spectral data analysis are presented. The evolution and convergence properties of hybrid methods based on both sparsity and smoothness constraints for the resulting nonnegative matrix factors are discussed. The interpretability of NMF outputs in specific contexts are provided along with opportunities for future work in the modification of NMF algorithms for large-scale and time-varying data sets.     

Using underapproximations for sparse nonnegative matrix factorization

Nonnegative matrix factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc.We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs.We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard sparse nonnegative matrix factorization techniques.     

正电子发射层析成像的鲁棒最小二乘重建

提出的鲁棒最小二乘算法综合考虑了正电子发射层析成像中的各种误差,适用于实际正电子发射层析成像系统．实验结果表明：该算法比传统的最小二乘重建算法具有更加鲁棒的重建特性．     

Non-negative Matrix Factorization with Symmetric Manifold Regularization

Non-negative matrix factorization (NMF) is becoming an important tool for information retrieval and pattern recognition. However, in the applications of image decomposition, it is not enough to discover the intrinsic geometrical structure of the observation samples by only considering the similarity of different images. In this paper, symmetric manifold regularized objective functions are proposed to develop NMF based learning algorithms (called SMNMF), which explore both the global and local features of the manifold structures for image clustering and at the same time improve the convergence of the graph regularized NMF algorithms. For different initializations, simulations are utilized to confirm the theoretical results obtained in the convergence analysis of the new algorithms. Experimental results on COIL20, ORL, and JAFFE data sets demonstrate the clustering effectiveness of the proposed algorithms by comparing with the state-of-the-art algorithms.

     

Convex and Semi-Nonnegative Matrix Factorizations

We present several new variations on the theme of nonnegative matrix factorization (NMF). Considering factorizations of the form X=FG^T, we focus on algorithms in which G is restricted to containing nonnegative entries, but allowing the data matrix X to have mixed signs, thus extending the applicable range of NMF methods. We also consider algorithms in which the basis vectors of F are constrained to be convex combinations of the data points. This is used for a kernel extension of NMF. We provide algorithms for computing these new factorizations and we provide supporting theoretical analysis. We also analyze the relationships between our algorithms and clustering algorithms, and consider the implications for sparseness of solutions. Finally, we present experimental results that explore the properties of these new methods.     

鲁棒自适应对称非负矩阵分解聚类算法

对称非负矩阵分解SNMF作为一种基于图的聚类算法,能够更自然地捕获图表示中嵌入的聚类结构,并且在线性和非线性流形上获得更好的聚类结果,但对变量的初始化比较敏感。另外,标准的SNMF算法利用误差平方和来衡量分解的质量,对噪声和异常值敏感。为了解决这些问题,在集成学习视角下,提出一种鲁棒自适应对称非负矩阵分解聚类算法RS³NMF(robust self-adaptived symmetric nonnegative matrix factorization)。基于L_2,1范数的RS³NMF模型缓解了噪声和异常值的影响,保持了特征旋转不变性,提高了模型的鲁棒性。同时,在不借助任何附加信息的前提下,利用SNMF对初始化特征的敏感性来逐步增强聚类性能。采用交替迭代方法优化,并保证目标函数值的收敛性。大量实验结果表明,所提RS³NMF算法优于其他先进的算法,具有较强的鲁棒性。     

Rapid algorithms for the construction of cerebral blood flow and oxygen utilization images with oxygen-15 and dynamic positron emission tomography

Two rapid estimation algorithms for construction of cerebral blood flow (CBF) and oxygen utilization (CMRO) images with dynamic positron emission tomography (PET) are presented. These algorithms are based on the linear least squares (LLS) and generalized linear least squares (GLLS) methodologies. Using the conventional two-compartmental model and multiple tracer studies, we derived a linear relationship for brain tissue activity to arterial blood activity, time-integrated arterial blood activity and time-integrated brain tissue activity. The LLS technique is computationally efficient as no regression analysis is required, while GLLS is used to refine the estimates obtained from LLS. A comparative study using non-linear least squares regression (NLS) revealed excellent correlation between the new algorithms for various noise levels expected in clinical applications. A sensitivity analysis was performed to examine reliability and identifiability of the parameter estimates. In view of the results, LLS and GLLS provide rapid and reliable estimates of CBF and CMRO when applied to dynamic PET data. These algorithms are particularly suitable for pixel-by-pixel construction of high resolution and highly accurate PET functional images.     

Non-negative matrix factorization based unmixing for principal component transformed hyperspectral data

Non-negative matrix factorization (NMF) has been widely used in mixture analysis for hyperspectral remote sensing. When used for spectral unmixing analysis, however, it has two main shortcomings: (1) since the dimensionality of hyperspectral data is usually very large, NMF tends to suffer from large computational complexity for the popular multiplicative iteration rule; (2) NMF is sensitive to noise (outliers), and thus the corrupted data will make the results of NMF meaningless. Although principal component analysis (PCA) can be used to mitigate these two problems, the transformed data will contain negative numbers, hindering the direct use of the multiplicative iteration rule of NMF. In this paper, we analyze the impact of PCA on NMF, and find that multiplicative NMF can also be applicable to data after principal component transformation. Based on this conclusion, we present a method to perform NMF in the principal component space, named ‘principal component NMF’ (PCNMF). Experimental results show that PCNMF is both accurate and time-saving.     

Enhanced clustering of biomedical documents using ensemble non-negative matrix factorization

Searching and mining biomedical literature databases are common ways of generating scientific hypotheses by biomedical researchers. Clustering can assist researchers to form hypotheses by seeking valuable information from grouped documents effectively. Although a large number of clustering algorithms are available, this paper attempts to answer the question as to which algorithm is best suited to accurately cluster biomedical documents. Non-negative matrix factorization (NMF) has been widely applied to clustering general text documents. However, the clustering results are sensitive to the initial values of the parameters of NMF. In order to overcome this drawback, we present the ensemble NMF for clustering biomedical documents in this paper. The performance of ensemble NMF was evaluated on numerous datasets generated from the TREC Genomics track dataset. With respect to most datasets, the experimental results have demonstrated that the ensemble NMF significantly outperforms classical clustering algorithms of bisecting K-means, and hierarchical clustering. We compared four different methods for constructing an ensemble NMF. For clustering biomedical documents, this research is the first to compare ensemble NMF with typical classical clustering algorithms, and validates ensemble NMF constructed from different graph-based ensemble algorithms. This is also the first work on ensemble NMF with Hybrid Bipartite Graph Formulation for clustering biomedical documents.     

Maximum likelihood least squares‐based iterative methods for output‐error bilinear‐parameter models with colored noises

This article is concerned with the parameter identification of output‐error bilinear‐parameter models with colored noises from measurement data. An auxiliary model least squares‐based iterative method is developed through the overparameterization model. It examines the difficulty of estimating the overparameterized vector, which usually presents a heavy computational burden in the identification process. To overcome this drawback, a parameter separation technique is introduced and the nonlinear model is reformulated as a refined identification model through eliminating the crossmultiplying terms. In this regard, a parameter separation least squares‐based iterative (PS‐LSI) algorithm is derived by avoiding estimating the redundant parameters. On the basis of the PS‐LSI algorithm, we derive a maximum likelihood least squares‐based iterative method to further improve the numerical accuracy. The identification is dependent on the formulation of a pseudolinear regression relationship, which contains two linear prefilters constructed from the system and noise models. The performance of this proposed method is confirmed by the numerical simulations as well as direct comparisons with other existing algorithms.