Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
DOI10.1007/s10107-023-01993-xarXiv2209.09573MaRDI QIDQ6126663
Andries Steenkamp, Milan Korda, Monique Laurent, Victor Magron
Publication date: 9 April 2024
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2209.09573
semidefinite programmingsparsitypolynomial optimizationnonnegative rankgeneralized moment problemcompletely positive rankmatrix factorization rank
Factorization of matrices (15A23) Semidefinite programming (90C22) Methods involving semicontinuity and convergence; relaxation (49J45) Linear operator methods in interpolation, moment and extension problems (47A57) Numerical methods of relaxation type (49M20) Polynomial optimization (90C23)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- From seven to eleven: completely positive matrices with high cp-rank
- On the computational complexity of membership problems for the completely positive cone and its dual
- The \(\mathcal A\)-truncated \(K\)-moment problem
- Stability and performance verification of optimization-based controllers
- Treewidth computations. I: Upper bounds
- A semidefinite programming approach to the generalized problem of moments
- Real rank versus nonnegative rank
- Positive semidefinite matrices with a given sparsity pattern
- Completely positive matrices and positivity of least squares solutions
- Extremal psd forms with few terms
- Completely positive matrices with a book-graph
- Notes on completely positive matrices
- On the geometric interpretation of the nonnegative rank
- The maximal cp-rank of rank \(k\) completely positive matrices
- Bounding the separable rank via polynomial optimization
- Semidefinite approximations of invariant measures for polynomial systems
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- A note on the representation of positive polynomials with structured sparsity
- Sum-of-squares chordal decomposition of polynomial matrix inequalities
- Global Optimization with Polynomials and the Problem of Moments
- Relative Entropy Relaxations for Signomial Optimization
- On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming
- On the cp-Rank and Minimal cp Factorizations of a Completely Positive Matrix
- An Introduction to Polynomial and Semi-Algebraic Optimization
- Julia: A Fresh Approach to Numerical Computing
- A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- New Lower Bounds and Asymptotics for the cp-Rank
- On the Complexity of Nonnegative Matrix Factorization
- Complexity of Finding Embeddings in a k-Tree
- Completely positive matrices associated withM-matrices
- Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Solution of the truncated complex moment problem for flat data
- The truncated complex $K$-moment problem
- Sparse Polynomial Optimization
- Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets
- A second order cone characterization for sums of nonnegative circuits
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Symmetric Tensor Nuclear Norms
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- The Representation of a Graph by Set Intersections
- Algorithm 457: finding all cliques of an undirected graph
- JuMP: A Modeling Language for Mathematical Optimization
- Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity