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

Keywords

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

Access to Document

10.1007/s10208-018-09410-y

1 Working paper

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization
Gribling, S., Laat, D. D. & Laurent, M., 4 Aug 2017, Ithaca: Cornell University Library, 45 p. (arXiv; vol. 1708.01573).
Research output: Working paper › Other research output

File

Cite this

@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 = oct,

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

language = "English",

volume = "19",

pages = "1013--1070",

journal = "Foundations of Computational Mathematics",

issn = "1615-3375",

publisher = "Springer New York",

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 -

Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

Abstract

Keywords

Access to Document

Fingerprint

Research output

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

Cite this