Search

In this paper we illustrate the use of Nonnegative Matrix Factorization (NMF) to analyze real data derived from an e-learning context. NMF is a matrix decomposition method which extracts latent information from data in such a way that it can be easily interpreted by humans. Particularly, the NMF of a score matrix can automatically generate the so called Q-matrix. In an e-learning scenario, the Q-matrix describes the abilities to be acquired by students to correctly answer evaluation exams. An example on real response data illustrates the effectiveness of this factorization method as a tool for EDM.

The nonnegative tensor (matrix) factorization finds more and more applications in various disciplines including machine learning, data mining, and blind source separation, etc. In computation, the optimization problem involved is solved by alternatively minimizing one factor while the others are fixed. To solve the subproblem efficiently, we first exploit a variable regularization term which makes the subproblem far from ill-condition. Second, an augmented Lagrangian alternating direction method is employed to solve this convex and well-conditioned regularized subproblem, and two accelerating skills are also implemented. Some preliminary numerical experiments are performed to show the improvements of the new method.

Nonnegative matrix factorization is a linear dimensionality reduction technique used for decomposing high-dimensional nonnegative data matrices for extracting basic and latent features. This technique plays fundamental roles in music analysis, signal processing, sound separation, and spectral data analysis. Given a time-varying objective function or a nonnegative time-dependent data matrix Y(t), the nonnegative factors of Y(t) can be obtained by taking the limit points of the trajectories of the corresponding ordinary differential equations. When the data are time dependent, it is natural to devise factorization techniques that capture the time dependency. To achieve this, one needs to solve continuous-time dynamical systems derived from iterative optimization schemes and construct nonnegative matrix factorization algorithms based on the solution curves. This article presents continuous nonnegative matrix factorization methods based on the solution of systems of ordinary differential equations associated with time-dependent data. In particular, we propose two new continuous-time algorithms based on the Kullback–Leibler divergence and the Amari \(\alpha \)-divergence.

This paper addresses the positive consensus problem for a homogeneous multi-agent system, by assuming that the agents' dynamics is described by a positive single-input and continuous-time system. We first provide a necessary condition for the problem solvability that refers to the Frobenius normal form of the Metzler matrix describing the agents' unforced evolution. This result imposes quite significant constraints on the agents' description, and it allows to reduce the general problem to the special case when the aforementioned matrix is irreducible. Under this assumption, equivalent sets of conditions that prove to be sufficient for the existence of a solution for the positive consensus problem are derived. Numerical examples illustrate the proposed results.

We present a nonnegative rank factorization of a nonnegative matrix A for the case in which one or both of A (1) A and AA (1) are nonnegative. This gives, in particular, a known result for characterizing nonnegative matrices when A † A or AA † is nonnegative. We applied this characterization to the derivation of known results based on the characterization of nonnegative monotone matrices.

Existence and determination of the set of Metzler matrices for given stable polynomialsThe problem of the existence and determination of the set of Metzler matrices for given stable polynomials is formulated and solved. Necessary and sufficient conditions are established for the existence of the set of Metzler matrices for given stable polynomials. A procedure for finding the set of Metzler matrices for given stable polynomials is proposed and illustrated with numerical examples.

In this paper, for a given set of numbers with special conditions, we construct a nonnegative matrix such that the given set is its spectrum.

The transition matrix, which characterizes a discrete time homogeneous Markov chain, is a stochastic matrix. A stochastic matrix is a special nonnegative matrix with each row summing up to 1. In this paper, we focus on the computation of the stationary distribution of a transition matrix from the viewpoint of the Perron vector of a nonnegative matrix, based on which an algorithm for the stationary distribution is proposed. The algorithm can also be used to compute the Perron root and the corresponding Perron vector of any nonnegative irreducible matrix. Furthermore, a numerical example is given to demonstrate the validity of the algorithm.

We consider a continuous-time bilinear control system (BCS) with Metzler matrices. Each entry in the transition matrix of such a system is nonnegative, making the positive orthant an invariant set of the dynamics. Motivated by the stability analysis of positive linear switched systems (PLSSs), we define a control as optimal if, for a fixed final time, it maximizes the spectral radius of the transition matrix. Our main result is a first-order necessary condition for optimality in the form of a maximum principle (MP). The proof of this MP combines the standard needle variation with a basic result from the Perron--Frobenius theory of nonnegative matrices. We describe several applications of this MP to the stability analysis of PLSSs under arbitrary switching.

In Nonnegative Matrix Factorization (NMF), a nonnegative matrix is approximated by a product of lower-rank factorizing matrices. Most NMF methods assume that each factorizing matrix appears only once in the approximation, thus the approximation is linear in the factorizing matrices. We present a new class of approximative NMF methods, called Quadratic Nonnegative Matrix Factorization (QNMF), where some factorizing matrices occur twice in the approximation. We demonstrate QNMF solutions to four potential pattern recognition problems in graph partitioning, two-way clustering, estimating hidden Markov chains, and graph matching. We derive multiplicative algorithms that monotonically decrease the approximation error under a variety of measures. We also present extensions in which one of the factorizing matrices is constrained to be orthogonal or stochastic. Empirical studies show that for certain application scenarios, QNMF is more advantageous than other existing nonnegative matrix factorization methods.

For a square (0, 1, −1) sign pattern matrix S, denote the qualitative class of S by Q(S). In this article, we investigate the relationship between sign patterns and matrices that diagonalize an irreducible nonnegative matrix. We explicitly describe the sign patterns S such that every matrix in Q(S) diagonalizes some irreducible nonnegative matrix. Further, we characterize the sign patterns S such that some member of Q(S) diagonalizes an irreducible nonnegative matrix. Finally, we provide necessary and sufficient conditions for a multiset of real numbers to be realized as the spectrum of an irreducible nonnegative matrix M that is diagonalized by a matrix in the qualitative class of some S 2 NS sign pattern.

Nonnegative matrix factorization has been offered as a fast and effective method for analyzing nonnegative two-mode proximity data. The goal is to structurally represent a nonnegative proximity matrix as the product of two lower-dimensional nonnegative matrices. Goodness of fit is typically measured as the sum of the squared deviations between the observed matrix elements and the estimated elements yielded by the product of the matrix factors. The preservation of nonnegativity of the factors has been touted as a major practical advantage over comparable decomposition methods (e.g., principal component analysis, singular-value decomposition, spectral analysis) because of its propensity for a more coherent additive interpretation. We provide descriptions of the nonnegative matrix factorization model and a rescaled gradient descent algorithm for estimating the factors. A small numerical example is provided along with application to three network matrices from the empirical literature.

The problem to minimize power losses in an electrical network subject to voltage and power constraints is in general hard to solve. However, it has recently been discovered that semidefinite programming relaxations in many cases enable exact computation of the global optimum. Here we point out a fundamental reason for the successful relaxations, namely that the passive network components give rise to matrices with nonnegative off-diagonal entries. Recent progress on quadratic programming with Metzler matrix structure can therefore be applied.

An algorithm of diagonal transformation for the Perron root of nonnegative matrices is proposed by Duan and Zhang [F. Duan, K. Zhang, An algorithm of diagonal transformation for Perron root of nonnegative irreducible matrices, Appl. Math. Comput. 175 (2006) 762–772]. This method can be used for all nonnegative irreducible matrices. In this paper, an improved algorithm which is based on this method is proposed. The new algorithm inherits all the above-mentioned advantages of the original algorithm and has higher efficiency. It is testified by numerical testing that the efficiency of the new algorithm is improved greatly.

Positive stable realizations with system Metzler matricesConditions for the existence of positive stable realizations with system Metzler matrices for linear continuous-time systems are established. A procedure for finding a positive stable realization with system Metzler matrix based on similarity transformation of proper transfer matrices is proposed and demonstrated on numerical examples. It is shown that if the poles of stable transfer matrix are real then the classical Gilbert method can be used to find the positive stable realization.

In this note, a simple method is presented that is both necessary and sufficient for determining whether a given Metzler matrix A is Hurwitz. The method is based on the well known fact that a Hurwitz Metzler matrix is also diagonally stable. By using this fact, very simple conditions are derived for the Hurwitz stability of a Metzler matrix. The conditions are stated in terms of the signs of the diagonal entries of a sequence of lower dimensional matrices. The efficacy of the conditions is demonstrated by applying them to determine stability in several examples.

We present in this paper a general formulation for nonnegative data factorization, called projective nonnegative graph embedding (PNGE), which 1) explicitly decomposes the data into two nonnegative components favoring the characteristics encoded by the so-called intrinsic and penalty graphs , respectively, and 2) explicitly describes how to transform each new testing sample into its low-dimensional nonnegative representation. In the past, such a nonnegative decomposition was often obtained for the training samples only, e.g., nonnegative matrix factorization (NMF) and its variants, nonnegative graph embedding (NGE) and its refined version multiplicative nonnegative graph embedding (MNGE). Those conventional approaches for out-of-sample extension either suffer from the high computational cost or violate the basic nonnegative assumption. In this work, PNGE offers a unified solution to out-of-sample extension problem, and the nonnegative coefficient vector of each datum is assumed to be projected from its original feature representation with a universal nonnegative transformation matrix. A convergency provable multiplicative nonnegative updating rule is then derived to learn the basis matrix and transformation matrix. Extensive experiments compared with the state-of-the-art algorithms on nonnegative data factorization demonstrate the algorithmic properties in convergency, sparsity, and classification power.

We present a dedicated algorithm for the nonnegative factorization of a correlation matrix from an application in financial engineering. We look for a low-rank approximation. The origin of the problem is discussed in some detail. Next to the description of the algorithm, we prove, by means of a counter example, that an exact nonnegative decomposition of a general positive semidefinite matrix is not always available.

Let A be an n × n irreducible nonnegative matrix. We show that over the set Ω n of all n × n doubly stochastic matrices S, the multiplicative spectral radius ρ ( SA ) attains a minimum and a maximum at a permutation matrix. For the case when A is a symmetric nonnegative matrix, a by-product of our technique of proof yields a result allowing us to show that ρ ( S 1 A ) ⩾ ρ ( S 2 A ) , when S 1 and S 2 are two symmetric matrices such that both S 1 A and S 2 A are nonnegative matrices and S 1 - S 2 is a positive semidefinite matrix. This result has several corollaries. One corollary is that ρ ( S 1 A ) ⩾ ρ ( S 2 A ) , when S 1 = ( 1 / n ) J and S 2 = ( 1 / ( n - 1 ) ) ( J - I ) , where J is the matrix of all 1’s. A second corollary is a comparison theorem for weak regular splittings of two monotone matrices.

In this paper, we study the structured nonnegative matrix factorization problem: given a square, nonnegative matrix P , decompose it as P = VAV ⊤ with V and A nonnegative matrices and with the dimension of A as small as possible. We propose an iterative approach that minimizes the Kullback–Leibler divergence between P and VAV ⊤ subject to the nonnegativity constraints on A and V with the dimension of A given. The approximate structured decomposition P ≃ VAV ⊤ is closely related to the approximate symmetric decomposition P ≃ VV ⊤ . It is shown that the approach for finding an approximate structured decomposition can be adapted to solve the symmetric decomposition problem approximately. Finally, we apply the nonnegative decomposition VAV ⊤ to the hidden Markov realization problem and to the clustering of data vectors based on their distance matrix.

For a class of positive matrices A + K with a stable positive nominal part A and a structured positive perturbation part K, we address the problem of finding the largest set of admissible perturbations such that the global matrix remains stable. Theoretical bounds are derived and an algorithm for constructing this set is presented. As an example, this algorithm is applied to the regulation of water flow in open channels. Copyright (C) 2008 John Wiley & Sons. Ltd.

We study the concept of a nonnegative matrix inducing hierarchies and apply it to the nonnegative input–output matrix of the open Leontief model, leading to properties which are stronger than the feasibility of the model. We show some examples of these matrices. The characterization of nonnegative matrices inducing hierarchies for any permutation of indices leads to certain matrices of class M ( x ) .

A copositive matrix A is said to be exceptional if it is not the sum of a positive semidefinite matrix and a nonnegative matrix. We show that with certain assumptions on A−1, especially on the diagonal entries, we can guarantee that a copositive matrix A is exceptional. We also show that the only 5-by-5 exceptional matrix with a hollow nonnegative inverse is the Horn matrix (up to positive diagonal congruence and permutation similarity).

It was recently conjectured that the Hurwitz stability of the convex hull of a set of Metzler matrices is a necessary and sufficient condition for the asymptotic stability of the associated switched linear system under arbitrary switching. In this note, we show that (1) this conjecture is true for systems constructed from a pair of second-order Metzler matrices; (2) the conjecture is true for systems constructed from an arbitrary finite number of second-order Metzler matrices; and (3) the conjecture is in general false for higher order systems. The implications of our results, both for the design of switched positive linear systems, and for research directions that arise as a result of our work, are discussed toward the end of the note.

In this paper, we obtain some new bounds for Perron root of a nonnegative matrix, which are expressed by easily calculated function in element of matrix. These new results generalize and improve the bounds of G. Frobenius [1] and H. Minc [2], and also extend the known results by Liu [6].

Es reproducción del documento publicado en http://dx.doi.org/10.1155/2007/84913 This paper investigates the properties of reachability, observability, controllability, and constructibility of positive discrete-time linear time-invariant dynamic systems when the sampling instants are chosen aperiodically. Reachability and observability hold if and only if a relevant matrix defining each of those properties is monomial for the set of chosen sampling instants provided that the continuous-time system is positive. Controllability and constructibility hold globally only asymptotically under close conditions to the above ones guaranteeing reachability/observability provided that the matrix of dynamics of the continuous-time system, required to be a Metzler matrix for the system's positivity, is furthermore a stability matrix while they hold in finite time only for regions excluding the zero vector of the first orthant of the state space or output space, respectively. Some related properties can be deduced for continuous-time systems and for piecewise constant discrete-time ones from the above general framework.

Nonnegative matrix factorization (NMF) is a powerful technique for dimensionality reduction. Conventional NMF algorithms usually keep the matrices W and H nonnegative while iterating. However, to get the NMF of a matrix, it's unnecessary to force the temporary solutions in iterations nonnegative. In this paper, we propose a two-staged approach for NMF. At the relaxation stage, the nonnegative constraint of temporary solutions is relaxed and a real valued matrix factorization is generated. At the constraint stage, the real valued matrix factorization is transformed to a nonnegative matrix factorization by an invertible linear transformation. Based on this approach, we study on exact nonnegative matrix factorization when rank=2. We proved that, given two real valued matrices of rank=2, there exists an invertible linear transformation which can transform the real valued matrices to nonnegative matrices with their product stable. We propose an algorithm to find out the transformation. When rank is higher than 2, this kind of transformation may not exist. In the experiments, it's showed that this approach can reach a nonnegative matrix factorization with lower reconstruction error than conventional methods, and the technique for rank=2 exact NMF works well.

The conditions for positivity and stability of a class of fractional nonlinear continuous-time systems are established. It is assumed that the nonlinear vector function is continuous, satisfies the Lipschitz condition and the linear part is described by a Metzler matrix. Using an extension of the Lyapunov method sufficient conditions for the stability are derived.

How quickly can we compute the nonnegative rank (r) of an m x n matrix? This problem ---- and the companion problem of finding a nonnegative matrix factorization with minimum inner-dimension ---- has a rich history, with applications in quantum mechanics, probability theory, data analysis, communication complexity and polyhedral combinatorics. Here we will survey the recent progress on this question, that has essentially resolved its worst-case complexity.

This paper investigates the stabilizability of linear systems with closed-loop positivity. A necessary and sufficient condition for the existence of desired state-feedback controllers guaranteeing the resultant closed-loop system to be asymptotically stable and positive is obtained. Both continuous and discrete-time cases are considered, and all of the conditions are expressed as linear matrix inequalities which can be easily verified by using standard numerical software. Numerical examples are provided to illustrate the proposed conditions.

A nonnegative sign pattern matrix is a matrix whose entries are from the set {+, 0}. A nonnegative sign pattern matrix can also be viewed as a Boolean matrix, by replacing each + entry with 1. In this paper, some interesting connections between nonnegative sign pattern matrices and Boolean matrices are investigated. In particular, the relations between the minimum rank and the Boolean row (or column) rank are explored; the idempotent Boolean matrices that allow idempotence are identified; and the nonnegative sign patterns that allow various types of nonnegative (or positive) generalized inverses are characterized.

Let V∈ R m,n be a nonnegative matrix. The nonnegative matrix factorization (NNMF) problem consists of finding nonnegative matrix factors W∈ R m,r and H ∈ R r , n such that V ≈ WH . Lee and Seung proposed two algorithms, one of which finds nonnegative W and H such that ∥ V − WH ∥ F is minimized. After examining the case in which r =1 about which a complete characterization of the solution is possible, we consider the case in which m = n and V is symmetric. We focus on questions concerning when the best approximate factorization results in the product WH being symmetric and on cases in which the best approximation cannot be a symmetric matrix . Finally, we show that the class of positive semidefinite symmetric nonnegative matrices V generated via a Soules basis admit for every 1⩽ r ⩽rank( V ), a nonnegative factorization WH which coincides with the best approximation in the Frobenius norm to V in R n,n of rank not exceeding r . An example of applications in which NNMF factorizations for nonnegative symmetric matrices V arise is video and other media summarization technology where V is obtained from a distance matrix.

In this paper we obtain a decomposition of nonnegative matrices A such that AA# ≥ 0. We then use this characterization to obtain the previous results known for nonnegative matrices A with A 3 ≥ 0. We also consider nonnegative matrices A with A - A 2 ≥ 0.

In this paper we give necessary and sufficient conditions for a matrix in Jordan canonical form to be similar to an eventually nonnegative matrix whose irreducible diagonal blocks satisfy the conditions identified by Zaslavsky and Tam, and whose subdiagonal blocks (with respect to its Frobenius normal form) are nonnegative. These matrices are referred to as seminonnegative matrices, and we show that they exhibit many of the same combinatorial spectral properties as nonnegative matrices. This paper extends the work on Jordan forms of irreducible eventually nonnegative matrices to the reducible case.

We consider the following inverse spectrum problem for nonnegative matrices: given a set of real numbers σ={λ1,λ2,…,λn}, find necessary and sufficient conditions for the existence of an n×n nonnegative matrix A with spectrum σ. In particular, by the use of a relevant theorem of Brauer we obtain new simple sufficient conditions for the problem to have a solution. Moreover, we can always construct a solution matrix, which is nonnegative generalized stochastic.

The following inverse spectrum problem for nonnegative matrices is considered: given a set of complex numbers σ ={ λ 1 , λ 2 ,…, λ n }, find necessary and sufficient conditions for the existence of an n × n nonnegative matrix A with spectrum σ . Our work is motivated by a relevant theoretical result of Guo Wuwen [Linear Algebra Appl. 266 (1997) 261, Theorem 2.1]: there exists a real parameter λ 0 ⩾max 2⩽ j ⩽ n | λ j | such that the problem has a solution if and only if λ 1 ⩾ λ 0 . In particular, we discuss how to compute λ 0 and the solution matrix A for certain class of matrices. A sufficient condition for the problem to have a solution is also derived.

Let A be an n×n nonnegative real matrix. We know that A is Γ-monotone if it has a nonnegative Γ-inverse. Moreover if A has an appropriate generalized inverse, then we can obtain nonnegative solutions for the linear system Ax=b, where b⩾0.In this paper, using properties about nonnegatives matrices, we present sufficient conditions in order that the Leontief price model(I+F)p(k+1)=[1+r(k)]Fp(k)+Gp0(k+1)a0,where F=(I−AT)−1BT and G=(I−AT)−1, have nonnegative solutions.

The notions of primitivity and exponent of a square nonnegative matrix A are classical: A is primitive provided there is a nonnegative integer k such that A k is entrywise positive and in the case A is primitive the exponent of A is the smallest such k. Fornasini and Valcher have extended the notion of primitivity to pairs (A, B) of square nonnegative matrices of the same order. The pair (A, B) is primitive provided there exist nonnegative integers h and k such that the sum of all products formed by words consisting of hA ’s and kB ’s is entrywise positive. This paper defines the exponent of a nonnegative matrix pair to be the smallest value of h + k over all such h and k. It is then shown that the largest exponent of a primitive pair of n by n nonnegative matrices lies in the interval [(n 3 − 5n 2 )/2 ,( 3n 3 + 2n 2 − 2n)/2]. In addition, the exponent of a pair of nonnegative matrices is related to properties of an associated twodimensional dynamical system. © 2001 Elsevier Science Inc. All rights reserved.

In this article we obtain a nonnegative rank factorization of nonnegative matrices A satisfying one or both of the following conditions: (i) AA † ⩽ 0 (ii) A † A ⩽ 0, thus providing a new set of conditions that guarantee the existence of a nonnegative least-squares solution of a linear system. Indeed, the characterization of such matrices improves some of the previous known conditions for the existence of a nonnegative least-squares solution of a linear system.

Link prediction is an important issue to understand the dynamics and evolution mechanisms of complex networks. Traditional link prediction algorithms are based on the topological properties of the underlying network in terms of graph theory. In order to improve the accuracy of link prediction, recent researches increasingly focus on modeling the link behaviors from the latent structure information of the networks. In this paper, we propose a neighborhood-based nonnegative matrix factorization model to solve the problem of link prediction. Our model learns latent feature factors from the overall topological structure combing with local neighborhood structures of the underlying network. Extensive experiments on real-world networks demonstrate the effectiveness and efficiency of our proposed model.

In this paper, we propose an `1-norm Symmetric Nonnegative Matrix TriFactorization (`1 S-NMTF) framework to cluster multi-type relational data by utilizing their interrelatedness. Due to introducing the `1-norm distances in our new objective function, the proposed approach is robust against noise and outliers, which are inherent in multi-relational data. We also derive the solution algorithm and rigorously analyze its correctness and convergence. The promising experimental results of the algorithm applied to text clustering on IMDB dataset validate the proposed approach.

International audience; We present a new design for continuous-discrete observers for a large class of continuous time nonlinear time-varying systems with discrete time measurements. Using the notion of cooperative systems, we show that the solutions of the observers converge to the solutions of the original system, under conditions on the nonlinear terms and on the largest sampling interval. Our conditions are given by explicit expressions.

The most widely studied matrix function is the matrix exponential, mainly because of its key role in the solution of differential equations. In this work we derive new alternatives for efficient computation of the matrix cosine. We focus especially on the two classes of Normal and Nonnegative matrices for which we study the interval of application for rational [7/7] L∞ approximation compared to the corresponding [7/7] Pade approximant when we implement the scaling and squaring Algorinthm [2].

We present a lower and an upper bound for the second smallest eigenvalue of Laplacian matrices in terms of the averaged minimal cut of weighted graphs. This is used to obtain an upper bound for the real parts of the non-maximal eigenvalues of irreducible nonnegative matrices. The result can be applied to Markov chains.

The upper bound of maximal entries in the principal eigenvector of a simple undirected connected graph is investigated in [Linear Algebra Appl. 310 (2000) 129]. We further investigate the maximal entry ymaxp in the principle eigenvector of symmetric nonnegative matrix with zero trace and obtain both sharp upper and lower bounds on the ymaxp. Particularly, this result answers the open question given in the above-mentioned reference

The spectral radius r(A) of matrix A is the maximum modulus of the Eigen values. In this paper, the studies about the lower and upper bounds for the spectral radius and the lower bounds for the minimum eigen value of appositive and nonnegative matrices are investigate.The matrix norm, the spectral radius norm,and the column (row) sums of nonnegative and positive matrices are widely used to establish some inequalities for matrices. Then several existing results are improved for these inequalities for nonnegative and positive matrix. Furthermore, the lower and upper bounds of the Perron roots for nonnegative matrices are examined, and some upper bounds are computed.