Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

Sander Gribling, David De Laat, Monique Laurent

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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
Volume19
Issue number5
DOIs
Publication statusPublished - Oct 2019

    Fingerprint

Keywords

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

Cite this