  


Lineartime complete positivity detection and decomposition of sparse matrices
Peter J.C. Dickinson (p.j.c.dickinsonrug.nl) 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 NPhard. 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 lineartime. A factorisation of such a completely positive matrix can be found in lineartime as well. As a byproduct, our method provides insight on the number of different minimal rankone decompositions of the matrix. Keywords: completely positive, sparse matrix, lineartime 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/2011 Modify/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  