LINEAR-TIME COMPLETE POSITIVITY DETECTION AND DECOMPOSITION OF SPARSE MATRICES

A matrix X is called completely positive if it allows a factorization X - Sigma(b epsilon beta)bb(T) with nonnegative vectors b. These matrices are of interest in optimization, as it has been found that several combinatorial and quadratic problems can be formulated over the cone of completely positive matrices. The difficulty is that checking complete positivity is NP-hard. Finding a factorization of a general completely positive matrix is also hard. In this paper we study complete positivity of matrices whose underlying graph possesses a specific sparsity pattern, for example, being acyclic or circular, where the underlying graph of a symmetric matrix of order n is defined to be a graph with n vertices and an edge between two vertices if the corresponding entry in the matrix is nonzero. The types of matrices that we analyze include tridiagonal matrices as an example. We show that in these cases checking complete positivity can be done in linear-time. A factorization of such a completely positive matrix can be found in linear-time as well. As a by-product, our method provides insight on the number of different minimal rank-one decompositions of the matrix.