- Linear-time complete positivity detection and decomposition of sparse matrices Peter J.C. Dickinson (p.j.c.dickinsonrug.nl) Mirjam Dür (dueruni-trier.de) Abstract: A matrix $X$ is called completely positive if it allows a factorisation $X = \sum_{b\in \mathcal{B}} bb\Transpose$ with nonnegative vectors $b$. These matrices are of interest in optimisation, 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 factorisation 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. This includes tridiagonal matrices as an example. We show that in this case checking complete positivity can be done in linear-time. A factorisation 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. Keywords: completely positive, sparse matrix, linear-time Category 1: Linear, Cone and Semidefinite Programming (Other ) Citation: Preprint, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands, September 2011 Download: Entry Submitted: 11/17/2011Entry Accepted: 11/17/2011Entry Last Modified: 07/16/2012Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.