Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
From MaRDI portal
Publication:2329041
DOI10.1007/s10208-018-09410-yOpenAlexW2744182242WikidataQ128467519 ScholiaQ128467519MaRDI QIDQ2329041
Sander Gribling, David de Laat, Monique Laurent
Publication date: 17 October 2019
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1708.01573
nonnegative rankpositive semidefinite rankcompletely positive rankmatrix factorization ranksnoncommutative polynomial optimizationcompletely positive semidefinite rank
Factorization of matrices (15A23) Semidefinite programming (90C22) Numerical analysis (65-XX) Computer science (68-XX)
Related Items
Lifting for Simplicity: Concise Descriptions of Convex Sets, Bounding the separable rank via polynomial optimization, Sparse noncommutative polynomial optimization, Globally trace-positive noncommutative polynomials and the unbounded tracial moment problem, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks, Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices, Exploiting term sparsity in noncommutative polynomial optimization, Optimization over trace polynomials
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Matrices with high completely positive semidefinite rank
- Polytopes of minimum positive semidefinite rank
- From seven to eleven: completely positive matrices with high cp-rank
- The \(\mathcal A\)-truncated \(K\)-moment problem
- Linear conic formulations for two-party correlations and values of nonlocal games
- Some upper and lower bounds on PSD-rank
- Handbook on semidefinite, conic and polynomial optimization
- Smallest compact formulation for the permutahedron
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Positive semidefinite rank
- A note on the computation of the CP-rank
- The ellipsoid method and its consequences in combinatorial optimization
- Using separation algorithms to generate mixed integer model reformulations
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Expressing combinatorial optimization problems by linear programs
- A non-commutative spectral theorem
- Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
- Non-closure of the set of quantum correlations via graphs
- On the geometric interpretation of the nonnegative rank
- Combinatorial bounds on nonnegative rank and extended formulations
- Completely positive semidefinite rank
- Algorithms for positive semidefinite factorization
- The tracial moment problem and trace-optimization of polynomials
- A factorization method for completely positive matrices
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Quantum and non-signalling graph isomorphisms
- New approximations for the cone of copositive matrices and its dual
- Connes' embedding conjecture and sums of Hermitian squares
- Operator algebras. Theory of \(C^*\)-algebras and von Neumann algebras
- Global Optimization with Polynomials and the Problem of Moments
- Approximation of the Stability Number of a Graph via Copositive Programming
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- SDP Relaxations for Non-Commutative Polynomial Optimization
- Optimization of Polynomials in Non-Commuting Variables
- On the cp-Rank and Minimal cp Factorizations of a Completely Positive Matrix
- The truncated tracial moment problem
- New results on the cp-rank and related properties of co(mpletely )positive matrices
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Julia: A Fresh Approach to Numerical Computing
- Stochastic factorizations, sandwiched simplices and the topology of the space of explanations
- Convergent Relaxations of Polynomial Optimization Problems with Noncommuting Variables
- Quantum Bilinear Optimization
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- New Lower Bounds and Asymptotics for the cp-Rank
- Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone
- On the Complexity of Nonnegative Matrix Factorization
- Completely positive matrices associated withM-matrices
- On Ranks of Regular Polygons
- On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings
- THE SET OF QUANTUM CORRELATIONS IS NOT CLOSED
- The Matching Polytope has Exponential Extension Complexity
- Solution of the truncated complex moment problem for flat data
- Linear-Time Complete Positivity Detection and Decomposition of Sparse Matrices
- Correlation matrices, Clifford algebras, and completely positive semidefinite rank
- Lifts of Convex Sets and Cone Factorizations
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- The Complexity of Positive Semidefinite Matrix Factorization
- Symmetric Tensor Nuclear Norms
- The proof of Tchakaloff’s Theorem
- Maximum matching and a polyhedron with 0,1-vertices
- Extended formulations in combinatorial optimization
- Constrained trace-optimization of polynomials in freely noncommuting variables
