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.     

Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification

Given a row-stochastic matrix describing pairwise similarities between data objects, spectral clustering makes use of the eigenvectors of this matrix to perform dimensionality reduction for clustering in fewer dimensions. One example from this class of algorithms is the Robust Perron Cluster Analysis (PCCA+), which delivers a fuzzy clustering. Originally developed for clustering the state space of Markov chains, the method became popular as a versatile tool for general data classification problems. The robustness of PCCA+, however, cannot be explained by previous perturbation results, because the matrices in typical applications do not comply with the two main requirements: reversibility and nearly decomposability. We therefore demonstrate in this paper that PCCA+ always delivers an optimal fuzzy clustering for nearly uncoupled, not necessarily reversible, Markov chains with transition states.     

Symmetry of eigenvalues of Sylvester matrices and tensors

In this article, the index of imprimitivity of an irreducible nonnegative matrix in the famous PerronFrobenius theorem is studied within a more general framework, both in a more general tensor setting and in a more natural spectral symmetry perspective. A k-th order tensor has symmetric spectrum if the set of eigenvalues is symmetric under a group action with the group being a subgroup of the multiplicative group of k-th roots of unity. A sufficient condition, in terms of linear equations over the quotient ring, for a tensor possessing symmetric spectrum is given, which becomes also necessary when the tensor is nonnegative, symmetric and weakly irreducible, or an irreducible nonnegative matrix. Moreover, it is shown that for a weakly irreducible nonnegative tensor, the spectral symmetries are the same when either counting or ignoring multiplicities of the eigenvalues. In particular, the spectral symmetry(index of imprimitivity) of an irreducible nonnegative Sylvester matrix is completely resolved via characterizations with the indices of its positive entries. It is shown that the spectrum of an irreducible nonnegative Sylvester matrix can only be 1-symmetric or 2-symmetric, and the exact situations are fully described. With this at hand, the spectral symmetry of a nonnegative two-dimensional symmetric tensor with arbitrary order is also completely characterized.     

一类交换子奇异值不等式

本文研究了当A,B为复可分Hilbert空间上的正紧算子,f∈C(σ(A)∪σ(B)),f(0)=0且f是[0,+∞)上的非负单调增函数时,关于f(A),f(B)交换子奇异值不等式的问题.利用谱映射定理及Cayley变换的方法,获得了关于交换子奇异值的一类不等式,推广了F.Kittaneh的结果.     

Eigenvectors and ratio limit theorems for Markov chains and their relatives

Associated to classes of countable discrete Markov chains or, more generally, column-finite nonnegative infinite matrices, and a finite subset of the state space, is a dimension group. In many cases, this dimension group gives information about the nonnegative eigenvectors of the process. Moreover, the study of the nonnegative eigenvectors is, equivalent to the traces on an analytic one parameter family of dimension groups. We pay particular attention to the case that there is at most one nonnegative eigenvector per eigenvalue, giving a number of sufficient conditions. Using the techniques developed here, we also show that under a reasonable set of conditions (principle among them that there be just one nonnegative eigenvector for the spectral radius), a (one-sided) ratio limit theorem holds. Supported in part by an operating grant from NSERC (Canada) and an Isaac Walton Killam Fellowship (Canada Council).     

On the nonnegative self-adjoint solutions of the operator Riccati equation for infinite dimensional systems

The nonnegative self-adjoint solutions of the operator Riccati equation (ORE) are studied for stabilizable semigroup Hilbert state space systems with bounded sensing and control. Basic properties of the maximal solution of the ORE are investigated: stability of the corresponding closed loop system, structure of the kernel, Hilbert-Schmidt property. Similar properties are obtained for the nonnegative self-adjoint solutions of the ORE. The analysis leads to a complete classification of all nonnegative self-adjoint solutions, which is based on a bijection between these solutions and finite dimensional semigroup invariant subspaces contained in the antistable unobservable subspace.     

Aggregating multiple classification results using fuzzy integration and stochastic feature selection

Classifying magnetic resonance spectra is often difficult due to the curse of dimensionality; scenarios in which a high-dimensional feature space is coupled with a small sample size. We present an aggregation strategy that combines predicted disease states from multiple classifiers using several fuzzy integration variants. Rather than using all input features for each classifier, these multiple classifiers are presented with different, randomly selected, subsets of the spectral features. Results from a set of detailed experiments using this strategy are carefully compared against classification performance benchmarks. We empirically demonstrate that the aggregated predictions are consistently superior to the corresponding prediction from the best individual classifier.     

Parameter identification in periodic delay differential equations with distributed delay

In this study, a parameter identification approach for identifying the parameters of a periodic delayed system with distributed delay is introduced based on time series analysis and spectral element analysis. Using this approach the parameters of the distributed delayed system can be identified from the time series of the response of the system. The experimental or numerical data of the response is examined with Floquet theory and time series analysis techniques to estimate a reduced order dynamics, or truncated state space to identify the Floquet multipliers. Parameter identification is then completed using a dynamic map developed for the assumed model of the system which can relate the Floquet multipliers to the unknown parameters in the model. The parameter identification technique is validated numerically for first and second order delay differential equations with distributed delay.     

Geometric simplicity of spectral radius of nonnegative irreducible tensors

We study the real and complex geometric simplicity of nonnegative irreducible tensors. First, we prove some basic conclusions. Based on the conclusions, the real geometric simplicity of the spectral radius of an evenorder nonnegative irreducible tensor is proved. For an odd-order nonnegative irreducible tensor, sufficient conditions are investigated to ensure the spectral radius to be real geometrically simple. Furthermore, the complex geometric simplicity of nonnegative irreducible tensors is also studied.     

Strictly nonnegative tensors and nonnegative tensor partition

We introduce a new class of nonnegative tensors—strictly nonnegative tensors.A weakly irreducible nonnegative tensor is a strictly nonnegative tensor but not vice versa.We show that the spectral radius of a strictly nonnegative tensor is always positive.We give some necessary and su?cient conditions for the six wellconditional classes of nonnegative tensors,introduced in the literature,and a full relationship picture about strictly nonnegative tensors with these six classes of nonnegative tensors.We then establish global R-linear convergence of a power method for finding the spectral radius of a nonnegative tensor under the condition of weak irreducibility.We show that for a nonnegative tensor T,there always exists a partition of the index set such that every tensor induced by the partition is weakly irreducible;and the spectral radius of T can be obtained from those spectral radii of the induced tensors.In this way,we develop a convergent algorithm for finding the spectral radius of a general nonnegative tensor without any additional assumption.Some preliminary numerical results show the feasibility and effectiveness of the algorithm.     

On gradient methods for maximum entropy regularizing retrieval of atmospheric aerosol particle size distribution function

The determination of the aerosol particle size distribution function using the particle spectrum extinction equation is an ill-posed integral equation of the first kind, since as is known, we are often faced with limited or insufficient observations in remote sensing and the observations are contaminated. Physically, the particle size distribution is always nonnegative, and we are often faced with incomplete data. Therefore, the concept of maximum entropy from information theory and statistic mechanics can be used to counteract this problem of missing or erroneous data. Therefore, in this paper, we study the maximum entropy based regularization model and gradient methods for solving the corresponding optimization problem. Numerical tests are made for synthetic aerosol data to show the efficiency and feasibility of the proposed algorithms. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A fast algorithm for the spectral radii of weakly reducible nonnegative tensors

In this paper, we propose a fast algorithm for computing the spectral radii of symmetric nonnegative tensors. In particular, by this proposed algorithm, we are able to obtain the spectral radii of weakly reducible symmetric nonnegative tensors without requiring the partition of the tensors. As we know, it is very costly to determine the partition for large‐sized weakly reducible tensors. Numerical results are reported to show that the proposed algorithm is efficient and also able to compute the spectral radii of large‐sized tensors. As an application, we present an algorithm for testing the positive definiteness of Z‐tensors. By this algorithm, it is guaranteed to determine the positive definiteness for any Z‐tensor.     

Analytical representation of concave and quasiconcave homogeneous functions

The formula which implements bijection between the class of concave linearly homogeneous functions defined on the nonnegative orthant of an arithmetic space and the simpler class of concave functions defined on the standard (probabilistic) simplex is presented. Two generalizations of this formula for analytical representation of quasiconcave homogeneous function are also proposed. These formulas particularly extend opportunities of modelling production objects and consumption.     

An efficient computational approach for multiframe blind deconvolution

Obtaining high resolution images of space objects from ground based telescopes involves using a combination of sophisticated hardware and computational post-processing techniques. An important, and often highly effective, computational post processing tool is multiframe blind deconvolution (MFBD). Mathematically, MFBD is modeled as a nonlinear inverse problem that can be solved using a flexible, variable projection optimization approach. In this paper we consider MFBD problems that are parameterized by a large number of variables. The formulas required for efficient implementation are carefully derived using the spectral decomposition and by exploiting properties of conjugate symmetric vectors. In addition, a new approach is proposed to provide a mathematical decoupling of the optimization problem, leading to a block structure of the Jacobian matrix. An application in astronomical imaging is considered, and numerical experiments illustrate the effectiveness of our approach.     

Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs

The problem of computing the smallest fixed point of an order-preserving map arises in the study of zero-sum positive stochastic games. It also arises in static analysis of programs by abstract interpretation. In this context, the discount rate may be negative. We characterize the minimality of a fixed point in terms of the nonlinear spectral radius of a certain semidifferential. We apply this characterization to design a policy iteration algorithm, which applies to the case of finite state and action spaces. The algorithm returns a locally minimal fixed point, which turns out to be globally minimal when the discount rate is nonnegative.     

Invariant Maximal Positive Subspaces and Polar Decompositions

It is proved that invertible operators on a Krein space which have an invariant maximal uniformly positive subspace and map its orthogonal complement into a nonnegative subspace allow polar decompositions with additional spectral properties. As a corollary, several classes of Krein space operators are shown to allow polar decompositions. An example in a finite dimensional Krein space shows that there exist dissipative operators that do not allow polar decompositions.     

Finding the Maximum Eigenvalue of Essentially Nonnegative Symmetric Tensors via Sum of Squares Programming

Finding the maximum eigenvalue of a tensor is an important topic in tensor computation and multilinear algebra. Recently, for a tensor with nonnegative entries (which we refer it as a nonnegative tensor), efficient numerical schemes have been proposed to calculate its maximum eigenvalue based on a Perron–Frobenius-type theorem. In this paper, we consider a new class of tensors called essentially nonnegative tensors, which extends the concept of nonnegative tensors, and examine the maximum eigenvalue of an essentially nonnegative tensor using the polynomial optimization techniques. We first establish that finding the maximum eigenvalue of an essentially nonnegative symmetric tensor is equivalent to solving a sum of squares of polynomials (SOS) optimization problem, which, in its turn, can be equivalently rewritten as a semi-definite programming problem. Then, using this sum of squares programming problem, we also provide upper and lower estimates for the maximum eigenvalue of general symmetric tensors. These upper and lower estimates can be calculated in terms of the entries of the tensor. Numerical examples are also presented to illustrate the significance of the results.     

张量分析和多项式优化的若干进展

张量分析 (也称多重数值线性代数) 主要包括张量分解和张量特征值的理论和算法,多项式优化主要包括目标和约束均为多项式的一类优化问题的理论和算法. 主要介绍这两个研究领域中若干新的研究结果. 对张量分析部分,主要介绍非负张量H-特征值谱半径的一些性质及求解方法,还介绍非负张量最大 (小) Z-特征值的优化表示及其解法;对多项式优化部分,主要介绍带单位球约束或离散二分单位取值、目标函数为齐次多项式的优化问题及其推广形式的多项式优化问题和半定松弛解法. 最后对所介绍领域的发展趋势做了预测和展望.     

On tangent cones of Alexandrov spaces with curvature bounded below

The tangent cones of an inner metric Alexandrov space with finite Hausdorff dimension and a lower curvature bound are always inner metric spaces with nonnegative curvature. In this paper we construct an infinite-dimensional inner metric Alexandrov space of nonnegative curvature which has in one point a tangent cone whose metric is not an inner metric. Received: 20 October 1999 / Revised version: 8 May 2000