Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

Sander Gribling, David de Laat, Monique Laurent

Research output: Working paperOther research output

13 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 languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages45
Publication statusPublished - 4 Aug 2017

Publication series

NamearXiv
Volume1708.01573

Fingerprint

Matrix Factorization
Lower bound
Polynomial
Optimization
Positive semidefinite
Semidefinite Programming
Convergence Properties
Non-negative
Analogue
Numerical Examples

Keywords

  • optimization and control

Cite this

Gribling, S., Laat, D. D., & Laurent, M. (2017). Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization. (arXiv; Vol. 1708.01573). Ithaca: Cornell University Library. Foundations of Computational Mathematics
Gribling, Sander ; Laat, David de ; Laurent, Monique. / Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization. Ithaca : Cornell University Library, 2017. (arXiv). (Foundations of Computational Mathematics).
@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 = "8",
day = "4",
language = "English",
series = "arXiv",
publisher = "Cornell University Library",
type = "WorkingPaper",
institution = "Cornell University Library",

}

Gribling, S, Laat, DD & Laurent, M 2017 'Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization' arXiv, vol. 1708.01573, Cornell University Library, Ithaca.

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization. / Gribling, Sander; Laat, David de; Laurent, Monique.

Ithaca : Cornell University Library, 2017. (arXiv; Vol. 1708.01573).

Research output: Working paperOther research output

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 -

Gribling S, Laat DD, Laurent M. Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization. Ithaca: Cornell University Library. 2017 Aug 4. (arXiv).