LAUSR

Abstract A matrix A is called completely positive, if there exists an entrywise nonnegative matrix B such that A = B B T . These matrices play a major role in combinatorial and quadratic optimization. In this paper, we study the problem of finding a nonnegative factorization B B T of a given completely positive matrix A. We formulate this factorization problem as a nonconvex feasibility problem and develop a solution method based on alternating projections. A local convergence result can be shown for this algorithm. We also provide a heuristic extension which improves the numerical performance of the algorithm. Extensive numerical tests show that the factorization method is very fast in most of the test instances and performs better than existing algorithms.