Sums of Squares and Sparse Semidefinite Programming

DOI10.1137/20M1376170zbMath1478.90075arXiv2010.11311OpenAlexW3206078947WikidataQ114847123 ScholiaQ114847123MaRDI QIDQ5157588

Kevin Shu, Grigoriy Blekherman

Publication date: 19 October 2021

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.11311

zbMATH Keywords

semidefinite programmingmatrix completionreal algebraic geometry

Mathematics Subject Classification ID

Semidefinite programming (90C22) Real algebraic and real-analytic geometry (14P99) Matrix completion problems (15A83)

Related Items (1)

Bilinear matrix inequalities and polynomials in several freely noncommuting variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Positive definite completions of partial Hermitian matrices
• Decomposition by clique separators
• Structural conditions for cycle completable graphs
• The real positive definite completion problem for a simple cycle
• Minimum fill-in: inapproximability and almost tight lower bounds
• There are significantly more nonnegative polynomials than sums of squares
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Sums of squares and varieties of minimal degree
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
• On a Parametrization of Positive Semidefinite Matrices with Zeros
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The real positive definite completion problem: cycle completability
• Semidefinite Optimization and Convex Algebraic Geometry
• Do Sums of Squares Dream of Free Resolutions?
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

This page was built for publication: Sums of Squares and Sparse Semidefinite Programming