Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

Sander Gribling; David De Laat; Monique Laurent

doi:10.1007/s10208-018-09410-y

Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

Sander Gribling, David De Laat, Monique Laurent

Research output: Contribution to journal › Article › Scientific › peer-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 language	English
Pages (from-to)	1013-1070
Journal	Foundations of Computational Mathematics
Volume	19
Issue number	5
DOIs	https://doi.org/10.1007/s10208-018-09410-y
Publication status	Published - Oct 2019

Fingerprint

Keywords

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

Cite this

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

@article{4c5afc60af8c4b7d96b1f5e2a8fc180f,

title = "Lower bounds on matrix factorization ranks via noncommutative polynomial optimization",

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.",

keywords = "Matrix factorization ranks, Nonnegative rank Positive semidefinite rank, Completely positive rank, Completely positive semidefinite rank, Noncommutative polynomial optimization",

author = "Sander Gribling and {De Laat}, David and Monique Laurent",

year = "2019",

month = "10",

doi = "10.1007/s10208-018-09410-y",

language = "English",

volume = "19",

pages = "1013--1070",

journal = "Foundations of Computational Mathematics",

issn = "1615-3375",

number = "5",

}

TY - JOUR

T1 - Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

AU - Gribling, Sander

AU - De Laat, David

AU - Laurent, Monique

PY - 2019/10

Y1 - 2019/10

N2 - 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.

AB - 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.

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

U2 - 10.1007/s10208-018-09410-y

DO - 10.1007/s10208-018-09410-y

M3 - Article

VL - 19

SP - 1013

EP - 1070

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

SN - 1615-3375

IS - 5

ER -

Access to Document

10.1007/s10208-018-09410-y

Research Output