Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

被引：17
作者：
Gribling, Sander [1 ]
de Laat, David [1 ]
Laurent, Monique [1 ,2 ]
机构：
[1] CWI, Amsterdam, Netherlands
[2] Tilburg Univ, Tilburg, Netherlands
来源：
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS | 2019年 / 19卷 / 05期
基金：
欧洲研究理事会;
关键词：
Matrix factorization ranks; Nonnegative rank; Positive semidefinite rank; Completely positive rank; Completely positive semidefinite rank; Noncommutative polynomial optimization; QUANTUM GRAPH PARAMETERS; CP-RANK; COMPLEXITY; CONE; APPROXIMATIONS; RELAXATIONS; ALGORITHMS; SUMS;
D O I：
10.1007/s10208-018-09410-y
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 analogs: the completely positive rank and the completely positive semidefinite rank. We study convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.
引用
收藏
页码：1013 / 1070
页数：58
相关论文
共 78 条
[1]  
Anjos M. F., 2012, Handbook on Semidefinite, Conic and Polynomial Optimization
[2]  
[Anonymous], 2006, ENCY MATH SCI
[3]  
[Anonymous], 1994, Linear and Multilinear Algebra
[4]  
[Anonymous], SPRINGER BRIEFS MATH
[5]   Quantum and non-signalling graph isomorphisms [J].
Atserias, Albert ;
Mancinska, Laura ;
Roberson, David E. ;
Samal, Robert ;
Severini, Simone ;
Varvitsiotis, Antonios .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 136 :289-328
[6]   NON-COMMUTATIVE SPECTRAL THEOREM [J].
BARKER, GP ;
EIFLER, LQ ;
KEZLAN, TP .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1978, 20 (02) :95-100
[7]   The proof of Tchakaloff's theorem [J].
Bayer, Christian ;
Teichmann, Josef .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 134 (10) :3035-3040
[8]  
Berman A., 2003, Completely positive matrices
[9]   A note on the computation of the CP-rank [J].
Berman, Abraham ;
Rothblum, Uriel G. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 419 (01) :1-7
[10]   QUANTUM BILINEAR OPTIMIZATION [J].
Berta, Mario ;
Fawzi, Omar ;
Scholz, Volkher B. .
SIAM JOURNAL ON OPTIMIZATION, 2016, 26 (03) :1529-1564
12345678