Optimization Online


Linear-time complete positivity detection and decomposition of sparse matrices

Peter J.C. Dickinson (p.j.c.dickinson***at***rug.nl)
Mirjam Dür (duer***at***uni-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


Entry Submitted: 11/17/2011
Entry Accepted: 11/17/2011
Entry Last Modified: 07/16/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society