Tensor factorizations with nonnegativity constraints have found application in analysing data from cyber traffic, social networks, and other areas. We consider application data best described as being generated by a Poisson process e.g. count data, which leads to sparse tensors that can be modelled by sparse factor matrices. In this paper, we investigate efficient techniques for computing an appropriate canonical polyadic tensor factorization based on the Kullback–Leibler divergence function. We propose novel subproblem solvers within the standard alternating block variable approach. Our new methods exploit structure and reformulate the optimization problem as small independent subproblems. We employ bound-constrained Newton and quasi-Newton methods. We compare our algorithms against other codes, demonstrating superior speed for high accuracy results and the ability to quickly find sparse solutions.
A row subproblem reformulation similar to ours is noted in earlier papers exploring the LS objective, but it never led to Hessian-based methods that exploit sparsity as ours do. Gonzales and Zhang use the reformulation with a multiplicative update method for NMF @cite_35 but do not generalize to tensors or the K-L objective. @ @cite_23 note the reformulation is suitable for parallelizing a Hessian-based method for NTF using LS. Kim and Park use the reformulation for NTF with LS @cite_16 , deriving small bound-constrained LS subproblems. Their method solves the LS subproblems by exact matrix factorization, without exploiting sparsity, and features a block principal pivoting method for choosing the active set. Other works solve the LS objective by taking advantage of row-by-row or column-by-column subproblem decomposition @cite_5 @cite_17 @cite_14 .
@cite_35 @cite_14 @cite_23 @cite_5 @cite_16 @cite_17
88153722 1542843314 2026034143 1561391377
Approximate nonnegative matrix factorization is an emerging technique with a wide spectrum of potential applications in data analysis. Currently, the most-used algorithms for this problem are those proposed by Lee and Seung [7]. In this paper we present a variation of one of the Lee-Seung algorithms with a notably improved performance. We also show that algorithms of this type do not necessarily converge to local minima. Alternative least squares (ALS) algorithm is considered as a "work-horse" algorithm for general tensor factorizations. For nonnegative tensor factorizations (NTF), we usually use a nonlinear projection (rectifier) to remove negative entries during the iteration process. However, this kind of ALS algorithm often fails and cannot converge to the desired solution. In this paper, we proposed a novel algorithm for NTF by recursively solving nonnegative quadratic programming problems. The validity and high performance of the proposed algorithm has been confirmed for difficult benchmarks, and also in an application of object classification. Nonnegative matrix factorization (NMF) and its extensions such as Nonnegative Tensor Factorization (NTF) have become prominent techniques for blind sources separation (BSS), analysis of image databases, data mining and other information retrieval and clustering applications. In this paper we propose a family of efficient algorithms for NMF NTF, as well as sparse nonnegative coding and representation, that has many potential applications in computational neuroscience, multi-sensory processing, compressed sensing and multidimensional data analysis. We have developed a class of optimized local algorithms which are referred to as Hierarchical Alternating Least Squares (HALS) algorithms. For these purposes, we have performed sequential constrained minimization on a set of squared Euclidean distances. We then extend this approach to robust cost functions using the alpha and beta divergences and derive flexible update rules. Our algorithms are locally stable and work well for NMF-based blind source separation (BSS) not only for the over-determined case but also for an under-determined (over-complete) case (i.e., for a system which has less sensors than sources) if data are sufficiently sparse. The NMF learning rules are extended and generalized for N-th order nonnegative tensor factorization (NTF). Moreover, these algorithms can be tuned to different noise statistics by adjusting a single parameter. Extensive experimental results confirm the accuracy and computational performance of the developed algorithms, especially, with usage of multi-layer hierarchical NMF approach [3]. We introduce an efficient algorithm for computing a low-rank nonnegative CANDECOMP PARAFAC (NNCP) decomposition. In text mining, signal processing, and computer vision among other areas, imposing nonnegativity constraints to the low-rank factors of matrices and tensors has been shown an effective technique providing physically meaningful interpretation. A principled methodology for computing NNCP is alternating nonnegative least squares, in which the nonnegativity-constrained least squares (NNLS) problems are solved in each iteration. In this chapter, we propose to solve the NNLS problems using the block principal pivoting method. The block principal pivoting method overcomes some difficulties of the classical active method for the NNLS problems with a large number of variables. We introduce techniques to accelerate the block principal pivoting method for multiple right-hand sides, which is typical in NNCP computation. Computational experiments show the state-of-the-art performance of the proposed method.