Positive Semidefinite Matrix Factorization: A Link To Phase Retrieval And A Block Gradient Algorithm

This paper deals with positive semidefinite matrix factorization (PSDMF). PSDMF writes each entry of a nonnegative matrix as the inner product of two symmetric positive semidefinite matrices. PSDMF generalizes nonnegative matrix factorization. Exact PSDMF has found applications in combinatorial optimization, quantum communication complexity, and quantum information theory, among others. In this paper, we show, for the first time, a link between PSDMF and the problem of matrix recovery from phaseless measurements, which includes phase retrieval. We demonstrate the usefulness of this observation by proposing a new type of local optimization scheme for PSDMF, which is based on a generalization of the Wirtinger flow method for phase retrieval. Numerical experiments show that our algorithm can performs as well as state-of-the-art algorithms, in certain setups. We suggest that this link between the two types of problems, which have until now been addressed separately, opens the door to new applications, algorithms, and insights.