Font Size: a A A

Research On Fast Nonnegative Data Processing Methods And Their Applications

Posted on:2021-02-11Degree:DoctorType:Dissertation
Country:ChinaCandidate:P T WangFull Text:PDF
GTID:1488306302962289Subject:Control Science and Engineering
Abstract/Summary:PDF Full Text Request
In real world,many physical quantities are intrinsically nonnegative,such as the pixel values of gray images,the frequency of words in a document and the ratings in user experience evaluation.During the analysis of such kind of data,nonnegativity constraints are often required to make the result more interpretable.Nonnegative matrix factorization(NMF),nonnegative tensor decomposition/factorization(NTD/NTF)and nonnegative quadratic programming(NQP)are three of the most common methods for processing nonnegative data.NMF is a matrix factorization method satisfying that the entries of input matrix and factor matrices are nonnegative.Due to the nonnegativity constraints,the data in the input matrix of NMF are represented by an additive combination of nonnegative basis vectors.This leads to a part-based representation of data which coincides with the cognitive style in the human brain:perception of the whole is based on perception of its parts.Therefore,NMF can provide interpretable results.NMF has been widely used in many fields,such as pattern recognition,machine learning and signal separation.Tensors are generalizations of matrices to higher dimensions.They have been used to store data in more and more applications.NTD and NTF are generalizations of NMF to tensors.They inherit the good interpretability of NMF and have proved effective in nonnegative tensor analysis.Nonnegative quadratic programming(NQP)is a classical convex optimization problem.Many problems in nonnegative data processing can be attributed to solving NQP problems,such as image denoising,nonnegative matrix factorization,and density estimation in Bayesian networks.So far,many algorithms have been proposed for NMF,NTD/NTF and NQP.However,there still exist some problems in them.For example,many NMF algorithms are sensitive with respect to the initialization because of the alternating optimization strategy,and thus often suffer from slow convergence.Symmetric NTF(SNTF)is an important method for multi-way probability clustering.However,only a few algorithms have been proposed for SNTF and they often suffer from slow convergence.Many algorithms for NQP are difficult to satisfy both efficiency and simplicity.The dissertation focuses on the research of fast algorithms for NMF,NTD/NTF and NQP.The main research works are listed as follows:(1)Two fast algorithms are proposed for NMF.First,a Procrustes rotation based nonnegative matrix factorization(PRNMF)algorithm is proposed,which updates all the factor matrices in NMF simultaneously.The experimental results show that PRNMF not only converges fast but also has a low reconstruction error in the case where the input data are less noisy or the nonnegative rank is small.Besides,a hybrid algorithm is proposed for NMF(HNMF),which combines PRNMF with another NMF algorithm proposed by Zhou et.al.to draw on each other's strengths.The experimental results show that HNMF not only converges fast,but also is robust to noise.(2)A fast algorithm based on extrapolation is proposed for symmetric nonnegative matrix factorization(SNMF).It is derived by applying an extrapolation scheme to the multiplicative updates algorithm of He et.al.Moreover,the restarting technique is used to guarantee that the value of objective function is monotonically descending.The experimental results show that the proposed algorithm is more than four times faster than the multiplicative updates algorithm of He et.al.(3)Based on HNMF,a fast algorithm is developed for nonnegative Tucker decomposition(one of nonnegative tensor decomposition models).The experiments on several real-world datasets show that the proposed algorithm takes less time than the algorithm of Zhou et.al.to get a solution with similar performance.(4)Two multiplicative updates algorithms are proposed for SNTF of third order tensors.First,by constructing an auxiliary function of the objective function,a new multiplicative updates algorithm is proposed,and its convergence under mild conditions is proved.Based on it,a fast multiplicative updates algorithm is proposed,which uses two different multiplicative update rules.The experiments on synthetic data and real-world data show that the proposed algorithms,especially the second one,converge faster than the recent SNTF algorithms.(5)An algorithm,which not only converges fast but also can be implemented simply,is proposed for NQP.First,a NQP algorithm is developed by utilizing a quadratic auxiliary function and the Newton method.Then,it is improved by an extrapolation scheme to speed up convergence.The proposed algorithm is applied to train support vector machines.The experimental results show that the proposed algorithm converges faster than multiplicative margin maximization(M3)and sequential minimal optimization(SMO).
Keywords/Search Tags:Nonnegative matrix factorization, symmetric nonnegative matrix factorization, nonnegative Tucker decomposition, symmetric nonnegative tensor factorization, nonnegative quadratic programming
PDF Full Text Request
Related items