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.
- Matrix factorization ranks, Nonnegative rank Positive semidefinite rank, Completely positive rank, Completely positive semidefinite rank, Noncommutative polynomial optimization
Gribling, S., De Laat, D., & Laurent, M. (2019). Lower bounds on matrix factorization ranks via noncommutative polynomial optimization. Foundations of Computational Mathematics, 19(5), 1013-1070. https://doi.org/10.1007/s10208-018-09410-y