Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

Research output: Contribution to journalArticleScientificpeer-review


We use techniques from (tracial noncommutative) polynomial optimization to formu-late hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank,and their symmetric analogs: the completely positive rank and the completely positive semidefinite rank. We study convergence properties of our hierarchies, compare themextensively to known lower bounds, and provide some (numerical) examples.
Original languageEnglish
Pages (from-to)1013-1070
JournalFoundations of Computational Mathematics
Issue number5
Publication statusPublished - Oct 2019


  • Matrix factorization ranks, Nonnegative rank Positive semidefinite rank, Completely positive rank, Completely positive semidefinite rank, Noncommutative polynomial optimization


Dive into the research topics of 'Lower bounds on matrix factorization ranks via noncommutative polynomial optimization'. Together they form a unique fingerprint.

Cite this