Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

Sander Gribling; David de Laat; Monique Laurent

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

Sander Gribling, David de Laat, Monique Laurent

Research output: Working paper › Other research output

131 Downloads (Pure)

Abstract

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

Original language	English
Place of Publication	Ithaca
Publisher	Cornell University Library
Number of pages	45
Publication status	Published - 4 Aug 2017

Publication series

Name	arXiv
Volume	1708.01573

Keywords

optimization and control

Access to Document

1708.01573v2

1 Article

Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
Gribling, S., De Laat, D. & Laurent, M., Oct 2019, In: Foundations of Computational Mathematics. 19, 5, p. 1013-1070
Research output: Contribution to journal › Article › Scientific › peer-review

Open Access

Cite this

@techreport{2dddf1563d4b4936bf02aa84f3cc4463,

title = "Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization",

abstract = "We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.",

keywords = "optimization and control",

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

year = "2017",

month = aug,

day = "4",

language = "English",

series = "arXiv",

publisher = "Cornell University Library",

type = "WorkingPaper",

institution = "Cornell University Library",

}

TY - UNPB

T1 - Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

AU - Gribling, Sander

AU - Laat, David de

AU - Laurent, Monique

PY - 2017/8/4

Y1 - 2017/8/4

N2 - We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.

AB - We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.

KW - optimization and control

M3 - Working paper

T3 - arXiv

BT - Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

PB - Cornell University Library

CY - Ithaca

ER -

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Research output

Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

Cite this