Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

摘要

We use techniques from (tracial noncommutative) polynomial optimization toformulate hierarchies of semidefinite programming lower bounds on matrixfactorization ranks. In particular, we consider the nonnegative rank, thepositive semidefinite rank, and their symmetric analogues: the completelypositive rank and the completely positive semidefinite rank. We study theconvergence properties of our hierarchies, compare them extensively to knownlower bounds, and provide some (numerical) examples.