{"id":"a2f976a7-04cd-45d2-a233-24c33cbc025c","arxiv_id":"2411.15479","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New sparse moment-SOS hierarchies for polynomial matrix optimization reduce SDP size, with term sparsity converging to PMI sign symmetry blocks and a counterexample showing correlative sparsity can fail asymptotically.","lead":"This paper develops sparsity-based shortcuts for a class of global optimization problems where the objective and constraints are matrices whose entries are polynomials. These shortcuts make large instances solvable with standard semidefinite programming, and the paper also shows where one popular shortcut provably fails.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.6's general constraint case is asserted without proof: the scalarization used for q_k=1 does not extend to matrix constraints, leaving the term-sparsity convergence claim unverified for general PMO.","rationale":"The reader's weakest_assumption identifies the scalar-constraint-only proof of Theorem 4.6 as a load-bearing premise for the central term-sparsity convergence claim; my analysis agrees and isolates this as the single most important gap. The counterexample in Example 5.1 is carefully constructed and its computations check out, so the negative correlative-sparsity result appears solid. The matrix-sparsity theorems in Section 6 are also sketched, but the term-sparsity convergence result is more central to the paper's advertised contributions. The concern is a proof gap rather than a demonstrated falsehood: the matrix constraint case may be recoverable by a direct induction using the sign property θ^γ = E_{G_k,θ,ℓw} for monomials of a PMI sign-symmetric matrix, but the paper does not provide that argument. Because the numerical evidence and the existing q_k=1 case give partial support, the appropriate disposition remains the reader's CONDITIONAL verdict; no adjustment is needed unless the proposed re-derivation reveals a counterexample.","tokens_in":127,"tokens_out":25234,"duration_ms":353955,"concrete_test":"Re-prove Theorem 4.6 for general q_k: fix a PMI sign symmetry θ common to F,G_1,...,G_m, and show by induction on s that the stabilized block-closure graph has blocks equal to the character classes of [α]_{(i-1)q_k+ℓ} under χ_k(α,i,ℓ)=θ^α s_i t_{k,ℓ}, where E_{F,θ,ij}=s_i s_j and E_{G_k,θ,ℓw}=t_{k,ℓ}t_{k,w}. Concretely, verify that support-extension rule (35) adds every edge within each character class and no edge between classes; if a single 2×2 matrix-constraint example (e.g., G=[[1-x1^2-x2^2,x1],[x1,1-x1^2-x2^2]] with F from Example 4.1) violates this at any s, Theorem 4.6 fails. The TSSOS code in the paper's repository can run this check directly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4's main convergence result, Theorem 4.6, is proved only in the case q_1=...=q_m=1; the text says the general case 'is more involved but follows in a similar manner.' The scalarization argument used there maps the PMO to inf y^T F y with scalar constraints and y^T y=1, and then invokes [24, Cor. 6.8]. This does not carry over to matrix constraints. For q_k>1, scalarizing the objective introduces y but leaves each G_k(x)⪰0 as a matrix inequality; to view it as a scalar TSSOS instance one would need extra z_k variables, and a product of two basis monomials x^α z_ℓ and x^β z_w together with a support monomial of z_k^T G_k z_k contains four z-powers, so it cannot land in the support set C^{(s)}_{i,j} which tracks only two y-powers. Thus the claimed node correspondence is not established for q_k>1. A correct proof would have to show, using that every monomial γ in G_k^{ℓ,w} satisfies θ^γ = E_{G_k,θ,ℓw}, that the support-extension condition (α+β+supp(G_k^{ℓ,w}))∩C^{(s)}_{i,j}≠∅ is equivalent to θ^{α+β}=E_{F,θ,ij}E_{G_k,θ,ℓw}; this is exactly the B_k edge criterion of Theorem 4.4. The paper does not supply this step. Since Theorem 4.6 is the advertised justification for using term sparsity in constrained PMO, this proof gap is load-bearing. The numerical experiments are consistent with the claim but do not cover general q_k>1 convergence.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops sparse semidefinite relaxations for polynomial matrix optimization (PMO), i.e., minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to polynomial matrix inequalities. The contributions are: a Newton-polytope basis reduction for unconstrained PMIs; an iterative term-sparsity scheme for constrained PMOs together with a claimed convergence of the block structures to those determined by PMI sign symmetries; a correlative-sparsity adapted hierarchy with a counterexample showing that asymptotic convergence fails for matrix objectives, plus extraction results based on matrix-valued measures; matrix-sparsity decompositions for objective and constraint matrices; and extensive numerical experiments implemented in TSSOS.","tokens_in":33016,"tokens_out":14559,"duration_ms":130947,"significance":"If the main claims are fully established, the paper would provide the first systematic sparsity framework for PMO, with a practical implementation and substantial speedups on structured examples. The negative result in Example 5.1 is an important and convincing finding: it shows that the scalar correlative-sparsity convergence theory does not extend to matrix objectives under the usual Archimedean and running-intersection assumptions. The extraction theorems in Section 5 are proved in detail, and the numerical study is reproducible through the released TSSOS code. However, the central term-sparsity convergence theorem and the matrix-sparsity decomposition theorems rest on proofs that are currently omitted or only sketched, so the advertised scope of the results is larger than what the manuscript verifies.","major_comments":[{"comment":"The proof of Theorem 4.6 is carried out only for q_1=...=q_m=1, and the general case is asserted to follow 'in a similar manner'. This is not a routine extension: the scalarization y^T F y reduces a PMO with scalar constraints to the TSSOS setting of [24], but for matrix constraints G_k(x)⪰0 with q_k>1, scalarizing the constraint would require additional z_k variables and z_k^T G_k z_k has support with four z-powers, so the support-extension condition (α+β+supp(G_k^{ℓ,w}))∩C^{(s)}_{i,j}≠∅ cannot be matched to the two-y-power support sets used in the matrix iteration. A proof needs to establish, for general q_k, the equivalence between this support-extension condition and the B_k edge criterion in (42), or Theorem 4.6 should be stated only for q_k=1. Since Theorem 4.6 is the advertised justification for term sparsity in constrained PMO, this gap is load-bearing.","section":"Section 4, Theorem 4.6"},{"comment":"Theorem 4.4 is stated with the proof omitted 'for conciseness'. This theorem supplies the constrained PMI-sign-symmetry block decomposition that underlies Corollary 4.5 and the convergence statement in Theorem 4.6; it is not a peripheral result. The authors should provide the full proof or an explicit citation to a published proof. As it stands, the block-diagonal representation (43) is an unverified assertion.","section":"Section 4, Theorem 4.4"},{"comment":"The proofs of Theorems 6.1, 6.2, and Corollary 6.3 are omitted with the instruction to replace the usual inner product by ⟨·,·⟩_p in the proofs of [42]. This is an assertion rather than a proof. The p-product is not a scalar inner product, and the Gram matrix of S_k has a block structure; one must show that the chordal decomposition of the SOS matrices and the p-product terms are compatible, and that the maximal cliques of F's sparsity graph can be lifted to the p×q_k block structure. Without these details, the matrix-sparsity decomposition theorems are not established.","section":"Section 6, Theorems 6.1-6.3"}],"minor_comments":[{"comment":"Reference [1] in the bibliography appears corrupted ('AboutSections Polynomial Matrix Inequality and Semidefinite Representation'); it should be corrected to the actual title.","section":"References"},{"comment":"The sentence 'Theorem 4.2 can be further extended to the constrained case' should refer to Theorem 4.3, not Theorem 4.2.","section":"Section 4"},{"comment":"The computation L(F)=0 is asserted with 'One can easily check'; since this is the contradiction driving the counterexample, the explicit calculation should be included so the example is fully self-contained.","section":"Example 5.1"},{"comment":"In Table 4, the CS+Chordal bounds are strictly looser than the CS bounds for a range of n; a sentence explaining why the chordal closure loses tightness in this PMO example would help the reader interpret the table.","section":"Table 4"},{"comment":"The displayed matrix R in (23) is difficult to parse because of the line breaks introduced by the text layout; please typeset it as a single matrix so that the column-to-basis correspondence is clear.","section":"Example 3.1"}],"recommendation":"major_revision","confidential_remarks":"The main novelty of the paper hinges on Theorem 4.4 and Theorem 4.6, and both have omitted proofs for the matrix-constraint case. I recommend requiring full proofs before acceptance. The counterexample and the extraction results are solid and well documented, and the numerical study is a clear strength."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: this is a useful paper with a genuine negative result and a promising framework, but the headline convergence theorem for term sparsity in the constrained PMO setting has a proof gap that the authors themselves flag with “more involved but follows in a similar manner.” I don't think that gap is fatal—there is good numerical evidence and the likely fix is technical—but it means the paper's central claim should be read as conditional until the general case is worked out.\n\nWhat's new: the paper extends term sparsity, correlative sparsity, and matrix sparsity from scalar polynomial optimization to PMO. The PMI sign symmetry concept is a real generalization, and the counterexample to correlative sparsity convergence (Example 5.1) is convincing and fully worked. The extraction theorems using matrix-valued measures give useful tools for detecting global optimality and retrieving solutions. The numerical experiments are extensive, reproducible via TSSOS, and show substantial speedups.\n\nWhere it's soft: Theorem 4.6 is the advertised justification for term sparsity with constraints, yet its proof is only given for q_k=1. The stress-test note explains why scalarization does not carry over: with matrix constraints, you would need extra z variables, and the support sets C^{(s)}_{i,j} track only two y-powers, so the node correspondence is not established. The authors assert the general case follows “in a similar manner,” but that is not a proof. The matrix sparsity decomposition theorems (6.1, 6.2, Cor 6.3) likewise rest on “replace the inner product with the p-product” without details. These are real gaps, but they are localized—the unconstrained results and the counterexample stand on their own. The numerical experiments are consistent with the claims but do not cover general q_k>1 convergence.\n\nWho it is for: researchers using moment-SOS hierarchies for PMO, especially in control and structured optimization. They will find the counterexample important and the sparse hierarchies practically useful. I would send it to a serious referee, but the referee should insist on completing Theorem 4.6 or explicitly restricting its scope.\n\nRecommendation: engage with it; accept conditional on the proof gap being resolved. If you are deciding whether to cite, the counterexample and the PMI sign symmetry framework are worth citing now; the term-sparsity convergence claim should be cited with care until the general proof appears.","headline":"Real advances on sparsity for polynomial matrix optimization, but the key term-sparsity convergence theorem is only proved for scalar constraints and should be treated as conditional pending a complete proof.","tokens_in":33491,"tokens_out":1818,"would_cite":true,"duration_ms":16883,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C23"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that term sparsity preserves the dense hierarchy's guarantees for polynomial matrix optimization, while correlative sparsity does not.","keywords":["polynomial matrix optimization","polynomial matrix inequality","sum of squares","term sparsity","correlative sparsity","matrix sparsity","PMI sign symmetry","matrix-valued measures"],"falsifier":"Run the term-sparsity block-closure iteration on a polynomial matrix optimization with at least one constraint matrix of size q_k > 1 and compare its fixed block partition to the partition induced by the common PMI sign symmetries; a single example where the two differ would falsify Theorem 4.6 as stated, and a systematic search over small random polynomial matrices with planted sign symmetries could settle the general-case claim.","tokens_in":32406,"feed_emoji":"🧮","tokens_out":10377,"duration_ms":87251,"temperature":0.7,"pith_summary":"The paper asks whether the sparsity shortcuts that make sum-of-squares optimization practical for scalar polynomials survive when the objects are polynomial matrices, and shows the answer is mixed. Term sparsity does survive: the paper constructs an iterative support-and-chordal-extension procedure whose block structure converges to the one forced by the common PMI sign symmetries of the objective and constraints, and proves finite convergence of the resulting sparse relaxations to the dense bounds. Correlative sparsity does not: a simple 2x2 example satisfies the Archimedean condition and running intersection property yet the adapted hierarchy never reaches the true minimum. The paper also shows how Newton polytopes shrink monomial bases, how matrix-valued measures certify optimality and extract solutions under correlative sparsity, and how chordal matrix sparsity of the objective or the constraints can be decomposed into smaller blocks. If correct, these results let practitioners solve larger polynomial matrix problems by choosing the sparsity structure that preserves convergence.","feed_headline":"Term sparsity converges for matrix SOS; correlative doesn't.","feed_subtitle":"For polynomial matrix problems, term sparsity keeps lower bounds tight; correlative sparsity fails to converge.","key_machinery":"The central objects are: (1) the term sparsity pattern graph, whose nodes are monomials tagged with a column index, [$\\alpha$]_i, and whose edges record which monomial products can contribute to entries of F and the G_k; (2) the alternating support-extension and chordal-extension iteration, with block closure as the chordal extension, which drives the graph to the common PMI sign symmetry structure; (3) PMI sign symmetries, binary vectors $\\theta$ in {-1,1}^n with P($\\theta$ composed with x) = E_{P,$\\theta$} composed with P(x) for a complete-bipartite sign matrix E_{P,$\\theta$}, generalizing ordinary sign symmetry to matrix entries; and (4) the p-product, a blockwise trace product that replaces the scalar inner product in the matrix Positivstellensatz and lets chordal decomposition proofs carry over. Matrix-valued measures and their flatness provide the dual certificates for optimality detection and solution extraction.","core_discovery":"On its own terms, the paper's central discovery is that sparsity reduction for polynomial matrix optimization has a different landscape from the scalar case. The term-sparsity iteration, alternating support extension with chordal extension using block closures, stabilizes at the block structure determined by the common PMI sign symmetries of F(x), G_1(x), ..., G_m(x), and the sparse hierarchy's bounds converge finitely to the dense hierarchy's bounds. In contrast, correlative sparsity loses asymptotic convergence when the objective is a matrix: Example 5.1 exhibits a 2x2 polynomial matrix F and two box constraints satisfying the Archimedean condition and running intersection property, yet no correlatively sparse relaxation order certifies the true optimal value. The paper restores some guarantees by giving rank-flatness conditions under which the correlatively sparse relaxation proves global optimality and returns optimal points and eigenvectors. It also transfers chordal matrix-sparsity decomposition to the matrix setting by replacing the usual inner product with the p-product, yielding block-decomposed SOS certificates for objectives and constraints with sparse chordal patterns.","pith_inferences":["If the term-sparsity convergence theorem extends to matrix constraints as asserted, then PMI sign symmetries could be used directly as a preprocessing step, without running the iterative term-sparsity procedure, to impose block-diagonal Gram structure.","The correlative-sparsity counterexample suggests that any convergent sparse hierarchy for PMO must either scalarize the objective or impose additional conditions tying the matrix-valued marginals together; a natural test is whether a joint atomicity condition on the matrix-valued measure restores convergence.","The paper's use of the p-product to port scalar chordal decomposition results suggests a general recipe for transferring other scalar SOS theorems to matrix-valued settings, though each transfer needs independent verification.","A practical extension would be a heuristic that detects whether the correlatively sparse hierarchy is converging, for example by monitoring the rank of overlapping marginal moment matrices, so a user can switch to the scalarized formulation only when needed."],"forward_implications":["Term sparsity with block closures can be applied to PMO at any relaxation order, and the resulting lower bounds converge to the dense hierarchy's bounds in finitely many sparse iterations, so sparsification does not cost accuracy.","Unconstrained PMI verification can be performed with monomial bases cut down to the half-Newton polytopes of the diagonal entries, shrinking the Gram matrix without conservatism.","Correlative sparsity alone is not a sound reduction for matrix objectives: the paper's Example 5.1 shows the hierarchy can stay strictly below the true optimal value at every order despite Archimedean and running intersection assumptions.","When the correlatively sparse relaxation satisfies the flatness-type rank conditions, global optimality can be certified and optimal solutions, together with eigenvectors, can be recovered by merging atomic matrix-valued measures.","Matrix sparsity of the objective or of the constraints yields block-decomposed SOS representations, with the same chordal decomposition theorems as the scalar case after replacing the inner product by the p-product."],"supporting_citations":[{"why":"Supplies the Newton polytope containment New(g_j) subset of 1/2 New(f) that drives the monomial basis reduction in Section 3.","marker":"[27]"},{"why":"Establishes the scalar term-sparsity iteration with block closures and its convergence to sign-symmetry block structures, which Theorem 4.6 extends to PMO.","marker":"[24]"},{"why":"Shows sign symmetries impose a block-diagonal structure on Gram matrices in SOS, used to prove Theorems 4.3 and 4.4 via scalarization.","marker":"[29]"},{"why":"Provides the matrix Positivstellensatz and the p-product weighted SOS representation underlying all constrained PMO relaxations.","marker":"[47]"},{"why":"Develops the matrix-valued moment relaxation, flatness theorem, and extraction procedure used for the dense hierarchy and for optimality detection.","marker":"[41]"},{"why":"Gives the scalar correlative-sparsity convergence theorem that the paper extends and then shows fails for matrix objectives.","marker":"[43]"},{"why":"Inspires the matrix-valued-measure construction behind the counterexample showing correlative sparsity does not converge for matrix objectives.","marker":"[55]"},{"why":"Proves chordal decomposition of polynomial matrix inequalities in the scalar-constraint setting, which Section 6 adapts to PMO with the p-product.","marker":"[42]"},{"why":"Supplies the chordal sparse PSD decomposition theorem used to split sparse Gram matrices into cliques.","marker":"[52]"},{"why":"Supplies the PSD completion theorem used for completable cones in sparse SDP relaxations.","marker":"[53]"}],"fun_headline_variants":["Term sparsity converges for matrix SOS; correlative fails","Matrix SOS: term sparsity tightens, correlative fails","Polynomial matrices: term sparsity works, correlative doesn't","Correlative sparsity fails for polynomial matrix optimization","Term sparsity succeeds where correlative fails in matrix SOS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the term-sparsity convergence theorem is carried out only for scalar constraints (q_1 = ... = q_m = 1), and the paper asserts that the general case with matrix constraints follows in a similar manner without supplying the details.","fun_headline_variants_meta":{"raw":{"variants":["Term sparsity converges for matrix SOS; correlative fails","Matrix SOS: term sparsity tightens, correlative fails","Polynomial matrices: term sparsity works, correlative doesn't","Correlative sparsity fails for polynomial matrix optimization","Term sparsity succeeds where correlative fails in matrix SOS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000367,"raw_usage":{"total_tokens":1996,"prompt_tokens":991,"completion_tokens":1005,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":923}},"tokens_in":607,"tokens_out":1005,"duration_ms":8006,"temperature":1.0,"reasoning_tokens":923,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:16:39.514250+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the term-sparsity block-closure iteration on a polynomial matrix optimization with at least one constraint matrix of size q_k > 1 and compare its fixed block partition to the partition induced by the common PMI sign symmetries; a single example where the two differ would falsify Theorem 4.6 as stated, and a systematic search over small random polynomial matrices with planted sign symmetries could settle the general-case claim.","supporting_citations":[{"cited_title":"Extremal PSD forms with few terms,","cited_arxiv_id":null,"evidence_quote":"Supplies the Newton polytope containment New(g_j) subset of 1/2 New(f) that drives the monomial basis reduction in Section 3."},{"cited_title":"TSSOS: A moment-SOS hierarchy that exploits term sparsity,","cited_arxiv_id":null,"evidence_quote":"Establishes the scalar term-sparsity iteration with block closures and its convergence to sign-symmetry block structures, which Theorem 4.6 extends to PMO."},{"cited_title":"Pre-and post-processing sum-of-squares programs in practice,","cited_arxiv_id":null,"evidence_quote":"Shows sign symmetries impose a block-diagonal structure on Gram matrices in SOS, used to prove Theorems 4.3 and 4.4 via scalarization."},{"cited_title":"Matrix Sum-of-Squares Relaxations for Robust Semi-Definite Programs,","cited_arxiv_id":null,"evidence_quote":"Provides the matrix Positivstellensatz and the p-product weighted SOS representation underlying all constrained PMO relaxations."},{"cited_title":"A Moment-Sum-of-Squares Hierarchy for Robust Polynomial Matrix Inequality Optimization with Sum-of-Squares Convexity,","cited_arxiv_id":null,"evidence_quote":"Develops the matrix-valued moment relaxation, flatness theorem, and extraction procedure used for the dense hierarchy and for optimality detection."},{"cited_title":"A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones,","cited_arxiv_id":null,"evidence_quote":"Gives the scalar correlative-sparsity convergence theorem that the paper extends and then shows fails for matrix objectives."},{"cited_title":"On matrix-valued monge–kantorovich optimal mass transport,","cited_arxiv_id":null,"evidence_quote":"Inspires the matrix-valued-measure construction behind the counterexample showing correlative sparsity does not converge for matrix objectives."},{"cited_title":"Sum-of-squares chordal decomposition of polynomial matrix inequalities,","cited_arxiv_id":null,"evidence_quote":"Proves chordal decomposition of polynomial matrix inequalities in the scalar-constraint setting, which Section 6 adapts to PMO with the p-product."},{"cited_title":"Positive semidefinite matrices with a given sparsity pattern,","cited_arxiv_id":null,"evidence_quote":"Supplies the chordal sparse PSD decomposition theorem used to split sparse Gram matrices into cliques."},{"cited_title":"Positive definite completions of partial hermitian matrices,","cited_arxiv_id":null,"evidence_quote":"Supplies the PSD completion theorem used for completable cones in sparse SDP relaxations."}],"review_version":1}