Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)     

An inequality for nonnegative matrices and the inverse eigenvalue problem

We present two versions of the same inequality, relating the maximal diagonal entry of a nonnegative matrix to its eigenvalues. We demonstrate a matrix factorization of a companion matrix, which leads to a solution of the nonnegative inverse eigenvalue problem (denoted the nniep) for 4×4 matrices of trace zero, and we give some sufficient conditions for a solution to the nniep for 5×5 matrices of trace zero. We also give a necessary condition on the eigenvalues of a 5×5 trace zero nonnegative matrix in lower Hessenberg form. Finally, we give a brief discussion of the nniep in restricted cases.     

Construction of nonnegative symmetric matrices with given spectrum

Let σ = (λ₁, … , λ_n) be the spectrum of a nonnegative symmetric matrix A with the Perron eigenvalue λ₁, a diagonal entry c and let τ = (μ₁, … , μ_m) be the spectrum of a nonnegative symmetric matrix B with the Perron eigenvalue μ₁. We show how to construct a nonnegative symmetric matrix C with the spectrum

(λ₁+max{0,μ₁-c},λ₂,…,λ_n,μ₂,…,μ_m).     

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.     

A note on the sequence of consecutive powers of a nonnegative matrix in max algebra

In this note, we shall consider the sequence of consecutive powers in max algebra of a nonnegative matrix with each element less than or equal to 1. The notion of asymptotic period is defined to study the ‘limiting behavior' of this sequence. A simple and effective characterization for the asymptotic period of the sequence is given.     

Constructive methods for spectra with three nonzero elements in the nonnegative inverse eigenvalue problem

We present and compare three constructive methods for realizing nonreal spectra with three nonzero elements in the nonnegative inverse eigenvalue problem. We also provide some necessary conditions for realizability and numerical examples. In particular, we utilize the companion matrix.     

Systematic maximum sum rank codes

In the last decade there has been a great interest in extending results for codes equipped with the Hamming metric to analogous results for codes endowed with the rank metric. This work follows this thread of research and studies the characterization of systematic generator matrices (encoders) of codes with maximum rank distance. In the context of Hamming distance these codes are the so-called Maximum Distance Separable (MDS) codes and systematic encoders have been fully investigated. In this paper we investigate the algebraic properties and representation of encoders in systematic form of Maximum Rank Distance (MRD) codes and Maximum Sum Rank Distance (MSRD) codes. We address both block codes and convolutional codes separately and present necessary and sufficient conditions for an encoder in systematic form to generate a code with maximum (sum) rank distance. These characterizations are given in terms of certain matrices that must be superregular in a extension field and that preserve superregularity after some transformations performed over the base field. We conclude the work presenting some examples of Maximum Sum Rank convolutional codes over small fields. For the given parameters the examples obtained are over smaller fields than the examples obtained by other authors.     

A mixed random walk on nonnegative matrices: A law of large numbers

In this paper a mixed random walk on nonnegative matrices has been studied. Under reasonable conditions, existence of a unique invariant probability measure and a law of large numbers have been established for such walks.     

Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering

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.     

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.     

Nonnegative rank of a matrix with one negative eigenvalue

We show that a rank-three symmetric matrix with exactly one negative eigenvalue can have arbitrarily large nonnegative rank.     

Studying Non-negative Factorizations with Tools from Linear Algebra over a Semiring

We develop the technique useful for studying the problem of factoring nonnegative matrices. We illustrate our method, based on the tools from linear algebra over a semiring, by applying it to studying the problem of existence of a rank-three matrix with full nonnegative rank equal to n.     

A note on the equality of rank and trace for an idempotent matrix

The equality of rank and trace for an idempotent matrix is established by means of elementary matrix factorizations. The proof is substantially simpler than most found in the literature.     

Two cores of a nonnegative matrix

We prove that the sequence of eigencones (i.e., cones of nonnegative eigenvectors) of positive powers A^k$A^k$ of a nonnegative square matrix A is periodic both in max algebra and in nonnegative linear algebra. Using an argument of Pullman, we also show that the Minkowski sum of the eigencones of powers of A is equal to the core of A defined as the intersection of nonnegative column spans of matrix powers, also in max algebra. Based on this, we describe the set of extremal rays of the core.     

Right ideals generated by an idempotent of finite rank

Let R be a K-algebra acting densely on V_D, where K is a commutative ring with unity and V is a right vector space over a division K-algebra D. Let f(X₁,…,X_t) be an arbitrary and fixed polynomial over K in noncommuting indeterminates X₁,…,X_t with constant term 0 such that for some μK occurring in the coefficients of f(X₁,…,X_t). It is proved that a right ideal ρ of R is generated by an idempotent of finite rank if and only if the rank of f(x₁,…,x_t) is bounded above by a same natural number for all x₁,…,x_tρ. In this case, the rank of the idempotent that generates ρ is also explicitly given. The results are then applied to considering the triangularization of ρ and the irreducibility of f(ρ), where f(ρ) denotes the additive subgroup of R generated by the elements f(x₁,…,x_t) for x₁,…,x_tρ.     

A very fast algorithm for matrix factorization

We present a very fast algorithm for general matrix factorization of a data matrix for use in the statistical analysis of high-dimensional data via latent factors. Such data are prevalent across many application areas and generate an ever-increasing demand for methods of dimension reduction in order to undertake the statistical analysis of interest. Our algorithm uses a gradient-based approach which can be used with an arbitrary loss function provided the latter is differentiable. The speed and effectiveness of our algorithm for dimension reduction is demonstrated in the context of supervised classification of some real high-dimensional data sets from the bioinformatics literature.