Papers › Sum-of-squares chordal decomposition of polynomial matrix inequalities
Sum-of-squares chordal decomposition of polynomial matrix inequalities
Yang Zheng, Giovanni Fantuzzi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We prove decomposition theorems for sparse positive (semi)definite polynomial matrices that can be viewed as sparsity-exploiting versions of the Hilbert--Artin, Reznick, Putinar, and Putinar--Vasilescu Positivstellens\"atze. First, we establish that a polynomial matrix P(x) with chordal sparsity is positive semidefinite for all x∈ℝⁿ if and only if there exists a sum-of-squares (SOS) polynomial σ(x) such that σP is a sum of sparse SOS matrices. Second, we show that setting σ(x)=(x₁² + ⋯+ xₙ²)^ν for some integer ν suffices if P is homogeneous and positive definite globally. Third, we prove that if P is positive definite on a compact semialgebraic set 𝒦={x:g₁(x)≥0,…,gₘ(x)≥0} satisfying the Archimedean condition, then P(x) = S₀(x) + g₁(x)S₁(x) + ⋯+ gₘ(x)Sₘ(x) for matrices Sᵢ(x) that are sums of sparse SOS matrices. Finally, if 𝒦 is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for (x₁² + …+ xₙ²)^ν P(x) with some integer ν≥0 when P and g₁,…,gₘ are homogeneous of even degree. Using these results, we find sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables, and we construct new convergent hierarchies of sparsity-exploiting SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate that these hierarchies can have a significantly lower computational complexity than traditional ones.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections