# A Non-commutative Extension of Lee-Seung's Algorithm for Positive Semidefinite Factorizations

arXiv: https://arxiv.org/abs/2106.00293 · HTML: https://mlsanity.com/paper/2106.00293/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 48 references that are in the map.
- First posted on arXiv 1 Jun 2021.

## Builds on (most cited first, 10 of 10)

- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [The Why and How of Nonnegative Matrix Factorization](https://mlsanity.com/paper/1401.5226/) (2014)
- [Positive semidefinite rank](https://mlsanity.com/paper/1407.4095/) (2014)
- [Inference in Graphical Models via Semidefinite Programming Hierarchies](https://mlsanity.com/paper/1709.06525/) (2017)
- [Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization](https://mlsanity.com/paper/2007.12364/) (2020)
- [A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow](https://mlsanity.com/paper/1506.08568/) (2015)
- [Algorithms for Positive Semidefinite Factorization](https://mlsanity.com/paper/1707.07953/) (2017)
- [Faster gradient descent and the efficient recovery of images](https://mlsanity.com/paper/1308.2464/) (2013)
- [Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity](https://mlsanity.com/paper/1311.2571/) (2013)

## Built on by (most cited first, 2 of 2)

- [A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization](https://mlsanity.com/paper/2303.17992/) (2023)
- [Multiplicative updates for symmetric-cone factorizations](https://mlsanity.com/paper/2108.00740/) (2021)

## Abstract (arXiv)

Given a matrix X∈ ℝ_+m× n with nonnegative entries, a Positive Semidefinite (PSD) factorization of X is a collection of r × r-dimensional PSD matrices Ai and Bj satisfying Xij= tr(Ai Bj) for all  i∈ [m], j∈ [n]. PSD factorizations are fundamentally linked to understanding the expressiveness of semidefinite programs as well as the power and limitations of quantum resources in information theory. The PSD factorization task generalizes the Non-negative Matrix Factorization (NMF) problem where we seek a collection of r-dimensional nonnegative vectors ai and bj satisfying Xij= ai^top bj, for all i∈ [m], j∈ [n] -- one can recover the latter problem by choosing matrices in the PSD factorization to be diagonal. The most widely used algorithm for computing NMFs of a matrix is the Multiplicative Update algorithm developed by Lee and Seung, in which nonnegativity of the updates is preserved by scaling with positive diagonal matrices. In this paper, we describe a non-commutative extension of Lee-Seung's algorithm, which we call the Matrix Multiplicative Update (MMU) algorithm, for computing PSD factorizations. The MMU algorithm ensures that updates remain PSD by congruence scaling with the matrix geometric mean of appropriate PSD matrices, and it retains the simplicity of implementation that Lee-Seung's algorithm enjoys. Building on the Majorization-Minimization framework, we show that under our update scheme the squared loss objective is non-increasing and fixed points correspond to critical points. The analysis relies on Lieb's Concavity Theorem. Beyond PSD factorizations, we use the MMU algorithm as a primitive to calculate block-diagonal PSD factorizations and tensor PSD factorizations. We demonstrate the utility of our method with experiments on real and synthetic data.