A Nonnegative Matrix Factorization (NMF) of a data matrix $X\in \mathbb{R}_+^{m\times n}$ is given by two families of nonnegative vectors $\{a_i\}\subseteq \mathbb{R}^r_+$ and $\{b_j\}\subseteq \mathbb{R}^r_+$ satisfying $ X_{ij}= \langle a_i,b_j\rangle,$ for all $ i\in [m],\ j\in [n], $ where $r\in\mathbb{N}$ is a user-specified parameter. NMFs are widely used as a dimensionality reduction technique, since the nonnegativity constraints give additive representations of the input data. A popular and easily implementable algorithm for finding NMFs is the multiplicative update method by Lee and Seung (LS). In this work, we give a non-commutative generalization of LS's algorithm for the positive semidefinite (PSD) factorization problem, where the goal is to find two families of PSD matrices $\{A_i\}\subseteq \mathbb{S}_+^r$ and $\{B_j\}\subseteq \mathbb{S}_+^r$ (for some $r\in\mathbb{N}$) satisfying $X_{ij}= {\rm trace}(A_iB_j)$ for all $\ i\in [m],\ j\in [n]. $ PSD factorizations have applications in a wide range of areas, most notably towards understanding the expressive power semidefinite programming and for studying the power and limitations of quantum resources in the context of information theory. Our PSD factorization algorithm is easy to implement, recovers LS's algorithm when specialized to diagonal PSD matrices, and is also the first algorithm for finding PSD factorizations with block-diagonal factors.

Joint work with Yong Sheng Soh (NUS)