Non-negative matrix and tensor factorization with applications to feature extraction

Abstract

Non-negative big data arising in many engineering problems may take the form of matrices or multi-dimensional array called tensors. To preserve the non-negativity property for interpretability, these non-negative algebraic structures can only be analyzed by means of Non-negative Matrix Factorization (NMF) and Non-negative Tensor Factorization (NTF) techniques, which have attracted increasing attention in the field of signal processing and machine learning. The NMF and NTF problem is to decompose a non-negative array into a lower dimensional rank structure so that the components of the decomposition characterize the essential features of the data. This thesis investigates the matrix and tensor modeling of non-negative data with an aim to develop efficient algorithms for NMF and NTF, and subsequently their applications for feature extraction. Two new methods, called the Double Non-negative Least Squares (D-NNLS) and Separable Non-negative Tensor Factorization (SNTF), are developed for NMF and NTF, respectively. The proposed SNTF algorithm is then used to develop a general methodology for extracting features from non-negative multiclass data for the purpose of classification.

Many existing NMF algorithms produce decomposition solutions that are inconsistent due to unpredictable convergence to local minima. By viewing the data matrix V as a collection of data points in the non-negative space, the associated non-negative geometry provides a way for interpreting the NMF problem as a generator extraction problem followed by non-negative regression. The proposed D-NNLS method performs NMF V=WH by extracting the extreme points from the original data cloud of V using non-negative least squares (NNLS) to construct W. The corresponding coefficient matrix H is then obtained by NNLS again such that V=WH. After comparing five commonly used NNLS algorithms, experimental results show that the Block Principal Pivoting method is the best NNLS algorithm for the proposed D-NNLS NMF. A data tensor can be treated as the multi-linear extension of the non-negative matrix obtained by stacking multiple matrices together. The proposed SNTF algorithm performs tensor decomposition using a hierarchical approach that sequentially unfolds the tensor along different directions to produce matrices, and then applies the proposed D-NNLS NMF algorithm to the matrices to extract features along different directions of the original data tensor. Based on the proposed SNTF, a feature extraction methodology is developed whereby non-negative multiclass data represented as a third-odder tensor is first decomposed into a CP (CANDECOMP and PARAFAC) model consisting of characteristic components whose weightings serve as features. The use of the methodology is demonstrated by means of applications to Electrooculography signal processing and face image classification problems. The effectiveness of all the proposed methods is evaluated using both synthetic and real data from biomedical signal processing and image analysis domains. Experimental results show that the proposed methods are promising in terms of computational error, computational time requirement and classification accuracy.