Positive Semidefinite Matrix Factorization: A Connection with Phase
  Retrieval and Affine Rank Minimization
  Positive semidefinite matrix factorization (PSDMF) expresses each entry of a
nonnegative matrix as the inner product of two positive semidefinite (psd)
matrices. When all these psd matrices are constrained to be diagonal, this
model is equivalent to nonnegative matrix factorization. Applications include
combinatorial optimization, quantum-based statistical models, and recommender
systems, among others. However, despite the increasing interest in PSDMF, only
a few PSDMF algorithms were proposed in the literature. In this work, we
provide a collection of tools for PSDMF, by showing that PSDMF algorithms can
be designed based on phase retrieval (PR) and affine rank minimization (ARM)
algorithms. This procedure allows a shortcut in designing new PSDMF algorithms,
as it allows to leverage some of the useful numerical properties of existing PR
and ARM methods to the PSDMF framework. Motivated by this idea, we introduce a
new family of PSDMF algorithms based on iterative hard thresholding (IHT). This
family subsumes previously-proposed projected gradient PSDMF methods. We show
that there is high variability among PSDMF optimization problems that makes it
beneficial to try a number of methods based on different principles to tackle
difficult problems. In certain cases, our proposed methods are the only
algorithms able to find a solution. In certain other cases, they converge
faster. Our results support our claim that the PSDMF framework can inherit
desired numerical properties from PR and ARM algorithms, leading to more
efficient PSDMF algorithms, and motivate further study of the links between
these models.
