A multilevel approach for nonnegative matrix factorization

Nonnegative matrix factorization (NMF), the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices, has been shown to be useful in many applications, such as text mining, image processing, and computational biology. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their initial convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. Several simple multilevel strategies are described and are experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets.     

An Adaptive Nonmonotone Projected Barzilai-Borwein Gradient Method with Active Set Prediction for Nonnegative Matrix Factorization

In this paper, we first present an adaptive nonmonotone term to improve the efficiency of nonmonotone line search, and then an active set identification technique is suggested to get more efficient descent direction such that it improves the local convergence behavior of algorithm and decreases the computation cost. By means of the adaptive nonmonotone line search and the active set identification technique, we put forward a global convergent gradient-based method to solve the nonnegative matrix factorization (NMF) based on the alternating nonnegative least squares framework, in which we introduce a modified Barzilai-Borwein (BB) step size. The new modified BB step size and the larger step size strategy are exploited to accelerate convergence. Finally, the results of extensive numerical experiments using both synthetic and image datasets show that our proposed method is efficient in terms of computational speed.     

Convergence analysis of a non-negative matrix factorization algorithm based on Gibbs random field modeling

Non-negative matrix factorization (NMF) is a new approach to deal with the multivariate nonnegative data. Although the classic multiplicative update algorithm can solve the NMF problems, it fails to find sparse and localized object parts. Then a Gibbs random field (GRF) modeling based NMF algorithm, called the GRF-NMF algorithm, try to directly model the prior object structure of the components into the NMF problem. In this paper, the convergence of the GRF-NMF algorithm and its advantages are investigated. Based on a classic model, the equilibrium points are obtained. Some invariant sets are constructed to prepare for the analysis of the convergence of the GRF-NMF algorithm. Then using stability theory of the equilibrium point, the convergence of the algorithm is proved and the convergence conditions of the algorithm are obtained. We theoretically present the advantages of the GRF-NMF algorithm in the end.     

An alternating projected gradient algorithm for nonnegative matrix factorization

Due to the extensive applications of nonnegative matrix factorizations (NMFs) of nonnegative matrices, such as in image processing, text mining, spectral data analysis, speech processing, etc., algorithms for NMF have been studied for years. In this paper, we propose a new algorithm for NMF, which is based on an alternating projected gradient (APG) approach. In particular, no zero entries appear in denominators in our algorithm which implies no breakdown occurs, and even if some zero entries appear in numerators new updates can always be improved in our algorithm. It is shown that the effect of our algorithm is better than that of Lee and Seung’s algorithm when we do numerical experiments on two known facial databases and one iris database.     

On the convergence of higher-order orthogonal iteration

The higher-order orthogonal iteration (HOOI) has been popularly used for finding a best low-multilinear rank approximation of a tensor. However, its convergence is still an open question. In this paper, we first analyse a greedy HOOI, which updates each factor matrix by selecting from the best candidates one that is closest to the current iterate. Assuming the existence of a block-nondegenerate cluster point, we establish its global iterate sequence convergence through the so-called Kurdyka–?ojasiewicz property. In addition, we show that if the starting point is sufficiently close to any block-nondegenerate globally optimal solution, the greedy HOOI produces an iterate sequence convergent to a globally optimal solution. Relating the iterate sequence by the original HOOI to that by the greedy HOOI, we then show that the original HOOI has global convergence on the multilinear subspace sequence and thus positively address the open question.     

Modified subspace Barzilai-Borwein gradient method for non-negative matrix factorization

Non-negative matrix factorization (NMF) is a problem to obtain a representation of data using non-negativity constraints. Since the NMF was first proposed by Lee, NMF has attracted much attention for over a decade and has been successfully applied to numerous data analysis problems. Recent years, many variants of NMF have been proposed. Common methods are: iterative multiplicative update algorithms, gradient descent methods, alternating least squares (ANLS). Since alternating least squares has nice optimization properties, various optimization methods can be used to solve ANLS’s subproblems. In this paper, we propose a modified subspace Barzilai-Borwein for subproblems of ANLS. Moreover, we propose a modified strategy for ANLS. Global convergence results of our algorithm are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework

We review algorithms developed for nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF) from a unified view based on the block coordinate descent (BCD) framework. NMF and NTF are low-rank approximation methods for matrices and tensors in which the low-rank factors are constrained to have only nonnegative elements. The nonnegativity constraints have been shown to enable natural interpretations and allow better solutions in numerous applications including text analysis, computer vision, and bioinformatics. However, the computation of NMF and NTF remains challenging and expensive due the constraints. Numerous algorithmic approaches have been proposed to efficiently compute NMF and NTF. The BCD framework in constrained non-linear optimization readily explains the theoretical convergence properties of several efficient NMF and NTF algorithms, which are consistent with experimental observations reported in literature. In addition, we discuss algorithms that do not fit in the BCD framework contrasting them from those based on the BCD framework. With insights acquired from the unified perspective, we also propose efficient algorithms for updating NMF when there is a small change in the reduced dimension or in the data. The effectiveness of the proposed updating algorithms are validated experimentally with synthetic and real-world data sets.     

Improving Jacobi and Gauss-Seidel Iterations

When convergent Jacobi or Gauss-Seidel iterations can be applied to solve systems of linear equations, a natural question is how convergence rates are affected if the original system is modified by performing some Gaussian elimination. We prove that if the initial iteration matrix is nonnegative, then such elimination improves convergence. Our results extend those contained in [4].     

Heuristics for exact nonnegative matrix factorization

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that \(X = WH\). In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic n-gons and conjecture the exact value of (i) the extension complexity of regular n-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.     

Characterization of some convergent bivariate subdivision schemes with nonnegative masks

Knowing that the convergence of a multivariate subdivision scheme with a nonnegative mask can be characterized by whether or not some finite products of row-stochastic matrices induced by this mask have a positive column. However, the number of those products is exponential with respect to the size of matrices. For nonnegative univariate subdivision, this problem is completely solved. Thus, the convergence in this case can be checked in linear time with respect to the size of a square matrix. This paper will demonstrate the necessary and sufficient conditions for the convergence of some nonnegative bivariate subdivision schemes by means of the so-called connectivity of a square matrix, which is derived by a given mask. Moreover, the connectivity can be examined in linear time with respect to the size of this matrix.     

Efficient Nonnegative Matrix Factorization Via Modified Monotone Barzilai-Borwein Method with Adaptive Step Sizes Strategy

In this paper, we develop an active set identification technique. By means of the active set technique, we present an active set adaptive monotone projected Barzilai-Borwein method (ASAMPBB) for solving nonnegative matrix factorization (NMF) based on the alternating nonnegative least squares framework, in which the Barzilai-Borwein (BB) step sizes can be adaptively picked to get meaningful convergence rate improvements. To get optimal step size, we take into account of the curvature information. In addition, the larger step size technique is exploited to accelerate convergence of the proposed method. The global convergence of the proposed method is analysed under mild assumption. Finally, the results of the numerical experiments on both synthetic and real-world datasets show that the proposed method is effective.     

On the geometric interpretation of the nonnegative rank

The nonnegative rank of a nonnegative matrix is the minimum number of nonnegative rank-one factors needed to reconstruct it exactly. The problem of determining this rank and computing the corresponding nonnegative factors is difficult; however it has many potential applications, e.g., in data mining and graph theory. In particular, it can be used to characterize the minimal size of any extended reformulation of a given polytope. In this paper, we introduce and study a related quantity, called the restricted nonnegative rank. We show that computing this quantity is equivalent to a problem in computational geometry, and fully characterize its computational complexity. This in turn sheds new light on the nonnegative rank problem, and in particular allows us to provide new improved lower bounds based on its geometric interpretation. We apply these results to slack matrices and linear Euclidean distance matrices and obtain counter-examples to two conjectures of Beasley and Laffey, namely we show that the nonnegative rank of linear Euclidean distance matrices is not necessarily equal to their dimension, and that the rank of a matrix is not always greater than the nonnegative rank of its square.     

A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation

In this paper, we propose a structure-preserving doubling algorithm (SDA) for the computation of the minimal nonnegative solution to the nonsymmetric algebraic Riccati equation (NARE), based on the techniques developed for the symmetric cases. This method allows the simultaneous approximation to the minimal nonnegative solutions of the NARE and its dual equation, requiring only the solutions to two linear systems and several matrix multiplications per iteration. Similar to Newton's method and the fixed-point iteration methods for solving NAREs, we also establish global convergence for SDA under suitable conditions, using only elementary matrix theory. We show that sequences of matrices generated by SDA are monotonically increasing and quadratically convergent to the minimal nonnegative solutions of the NARE and its dual equation. Numerical experiments show that the SDA algorithm is feasible and effective, and outperforms Newton's iteration and the fixed-point iteration methods. This research was supported in part by RFDP (20030001103) & NSFC (10571007) of China and the National Center for Theoretical Sciences in Taiwan. This author's research was supported by NSFC grant 1057 1007 and RFDP grant 200300001103 of China.     

Local convergence analysis of iterative aggregation-disaggregation methods with polynomial correction

The paper introduces some new results on local convergence analysis of one class of iterative aggregation-disaggregation methods for computing a stationary probability distribution vector of an irreducible stochastic matrix. We focus on methods, where the basic iteration on the fine level corresponds to a multiplication by a polynomial of order one with nonnegative coefficients in the original matrix. We show that this process is locally convergent for matrices with positive diagonals or when the coefficients of the polynomial are positive. On the other hand there are examples for which the process may diverge in a local sense for higher degree polynomials even if it converges for a polynomial of a lower degree for the same matrix.     

Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. Moreover, we present a convergent algorithm for calculating the largest eigenvalue for any nonnegative tensors.     

矩阵不等式约束下矩阵方程AX=B的双对称解

本文讨论矩阵不等式CXD≥E 约束下矩阵方程AX=B的双对称解,即给定矩阵A,B,C,D和 E, 求双对称矩阵X, 使得AX=B 和 CXD≥E, 其中CXD≥E表示矩阵CXD-E非负.本文将问题转化为矩阵不等式最小非负偏差问题,利用极分解理论给出了求其解的迭代方法,并结合相关矩阵理论说明算法的收敛性.最后给出数值算例验证算法的有效性.     

Parallel multisplitting two-stage iterative methods with general weighting matrices for non-symmetric positive definite systems

In this work, we propose a new parallel multisplitting iterative method for non-symmetric positive definite linear systems. Based on optimization theory, the new method has two great improvements; one is that only one splitting needs to be convergent, and the other is that the weighting matrices are not scalar and nonnegative matrices. The convergence of the new parallel multisplitting iterative method is discussed. Finally, the numerical results show that the new method is effective.     

Line-Sum Symmetry via the DomEig Algorithm

We propose a new algorithm, the DomEig algorithm, for obtaining the line-sum-symmetric similarity-scaling of a given irreducible, essentially nonnegative matrix A. It is based on results concerning the minimum dominant eigenvalue of an essentially nonnegative matrix under trace-preserving perturbations of its diagonal. In this note we relate the minimum dominant eigenvalue problem to the problem of determining the diagonal scaling matrix for line-sum-symmetry. We present the DomEig algorithm, prove its convergence, and discuss briefly the results of a comparison of this algorithm with another algorithm, the DSS algorithm, often used for line-sum symmetry. The experiments suggest that, for matrices of order greater than 50, the convergence rate, measured either in flop counts or CPU time, is significantly greater for DomEig than for DSS, with the improvement in rate increasing as the order increases. The algorithm may be useful in such applications as the scaling of large social accounting matrices.     

Exact solution to a parametric linear programming problem

In this paper, we present a cubically convergent method for finding the largest eigenvalue of a nonnegative irreducible tensor. A cubically convergent method is used to solve an equivalent system of nonlinear equations which is transformed by the tensor eigenvalue problem. Due to particular structure of tensor, Chebyshev’s direction is added to the method with a few extra computation. Two rules are designed such that the descendant property of the search directions is ensured. The global convergence is proved by using the line search technique. Numerical results indicate that the proposed method is competitive and efficient on some test problems.     

On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.