{"id":"7ca3f394-0aa9-4c9f-8b66-21f561d6211f","arxiv_id":"2502.01410","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Sparse moment relaxations converge finitely and yield minimizers when clique moment matrices have flat extensions and the cliques satisfy the running intersection property.","lead":"This paper proves new conditions under which sparse moment relaxations of polynomial optimization problems converge exactly and let you extract all optimal solutions. The conditions are weaker than previous ones, so more real problems can be certified as solved at a finite relaxation order.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the local flat-extension step and the RIP-based assembly both hold up under scrutiny.","rationale":"The proof of Theorem 1.1 is explicit, and the delicate steps hold. The rank equality (1.4a) is slightly stronger than the usual flat-extension condition, but monotonicity of ranks makes it sufficient. The atomic assembly in Section 4.1 correctly matches marginals on the relevant overlap using only the predecessor supplied by RIP, and Proposition 4.1's support-maximality argument is sound. The minor Proposition 3.2 imprecision does not affect the theorem or corollary. I therefore agree with the reader's ACCEPT verdict and find no reason to adjust it.","tokens_in":17642,"tokens_out":26989,"duration_ms":226961,"concrete_test":"Run an independent check on the clique-subvector step: take a small instance satisfying (1.3)–(1.4a), such as Example 5.1, and apply the flat extension theorem directly to verify the unique atomic measure on K_i; also verify that (1.4a) implies rank M^ω = rank M^{ω-1} by checking ranks of all intermediate moment submatrices.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a careful pass, I do not find a load-bearing flaw in the central argument. The reader's weakest assumption is the application of the classical flat extension theorem to each clique subvector. This application is valid: from (1.4a) and monotonicity of ranks, rank M^ω_{Δ_i}(y) = rank M^{ω-1}_{Δ_i}(y); together with (1.3) this is exactly the hypothesis of the Curto–Fialkow/Laurent flat extension theorem, yielding a unique finitely atomic representing measure on K_i. Lemma 3.3's uniqueness for the overlap follows similarly from (1.4b). The assembly of local measures uses only the one-predecessor consistency allowed by RIP, and Section 4.1 gives a correct atomic construction. The only imprecision is Proposition 3.2, which states the rank conditions without the PSD assumption used in its proof; this does not affect Theorem 1.1, where PSD is assumed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies moment relaxations of polynomial optimization problems with correlative sparsity. It proves a new sufficient condition for the finite convergence of such relaxations: assuming the cliques satisfy a running intersection property, if for each clique the associated moment and localizing matrices are positive semidefinite and satisfy a flat-extension rank condition (1.4a), and if a rank condition on one overlap per clique (1.4b) holds, then the sparse moment vector admits an atomic representing measure supported on the feasible set, with at least as many atoms as the largest rank of the clique moment matrices. This yields exactness of the relaxation and extraction of minimizers (Corollary 1.2). The paper also gives an explicit atomic assembly algorithm in Section 4.1, proves maximality of the support of the resulting measure (Section 4.2), and illustrates the results with examples, including a non-RIP counterexample in Section 5.3.","tokens_in":17779,"tokens_out":21478,"duration_ms":181910,"significance":"If the result holds, it is a solid contribution to the sparse moment-SOS literature. The criterion generalizes previous finite-convergence results of Nie et al. and Lasserre by allowing different clique ranks and requiring the overlap condition only for one predecessor per clique. The explicit atomic construction and the maximal-support theorem are new and practically useful. The paper is well written and the proofs are mostly rigorous, relying on standard flat-extension theorems. The examples in Section 5 clearly demonstrate situations where previous criteria fail but the new one succeeds.","major_comments":[],"minor_comments":[{"comment":"The proposition as stated omits the positive semidefiniteness assumption (1.3) that is used in its proof via Lemma 3.1. Without PSD the statement is false: for n=2 with cliques {1} and {2}, omega=2, take y0=0, y_{01}=1, and all other entries zero. Then y_{Delta_1}=0 but y is nonzero, and the rank equalities (1.4) hold. The statement should include the PSD assumption, or the proof of Theorem 1.1 should instead observe directly that PSD plus y nonzero forces y0>0, hence every clique subvector is nonzero.","section":"Section 3.1, Proposition 3.2"},{"comment":"There are several cross-reference typos: 'Theorem 1.2' in the paragraph after Corollary 1.2 and in Section 1.3 should be 'Corollary 1.2'; 'Theorem 3.3' in Section 3.2 should be 'Lemma 3.3'; and 'Theorem 3.1' in the proof of Proposition 3.2 should be 'Lemma 3.1'.","section":"Section 1.3 and surrounding text"},{"comment":"The uniqueness of the local clique measure mu_{Delta_i} follows from (1.4a) because d_i >= 1 implies rank M^omega_{Delta_i} = rank M^{omega-1}_{Delta_i} (by monotonicity of ranks of principal submatrices). This observation is used implicitly in the maximality proof in Section 4.2; it would be helpful to state it explicitly, since it justifies the claim that any other atomic representing measure has the same clique marginals.","section":"Section 3.2 and Section 4.2"},{"comment":"The shaded submatrices indicating M^{omega-d_i}_{Delta_i}(y) are not visible in the plain-text rendering; the reader must infer the principal submatrix block. A textual description of the submatrix indices would improve readability.","section":"Section 5.2.1, equations (5.11)"}],"recommendation":"minor_revision","confidential_remarks":"The reader's take and my own assessment agree: the central theorem is sound and the issues are local. The false statement of Proposition 3.2 should be corrected before publication, but it does not affect the main theorem because Theorem 1.1 assumes PSD. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers what it promises: a new sufficient condition for finite convergence and minimizer extraction in correlatively sparse moment relaxations, strictly weaker than the prior criteria in [18] and [11]. The key relaxation is dropping the requirement that all clique moment ranks take the same value, and only asking for the overlap rank condition (1.4b) along one RIP predecessor instead of all intersecting pairs. That is a real, useful advance, and the examples show cases where the older tests simply could not certify exactness.\n\nThe proof structure is the right one. Local flat extensions give atomic measures for each clique subvector; condition (1.4b) forces the marginals to agree on the needed overlaps; and the RIP-based gluing then assembles a global atomic measure. The construction in Section 4.1 is explicit and the maximal-support result in Proposition 4.1 is a nice bonus. The examples are worked out and illustrate both the power of the new criteria and the necessity of RIP. I checked the local representability step—the weakest assumption the reader flagged—and it is legitimate: (1.4a) with PSD is exactly the flat-extension hypothesis, so the clique subvectors do have atomic representing measures.\n\nSoft spots are minor. Proposition 3.2 is stated without the PSD assumption, though its proof uses it; this is an imprecision, not a gap, since Theorem 1.1 assumes PSD up front. Example 5.2 verifies ranks on rounded numerical data from MOSEK, which is fine as an illustration but not a rigorous numerical certificate; the theory does not depend on it. The conjecture in Section 5.4 is speculative but clearly labeled as such. I do not see a load-bearing flaw.\n\nWho should read this: anyone working on sparse moment-SOS hierarchies, polynomial optimization, or truncated moment problems. It will be a standard reference for the weaker finite-convergence criterion. My recommendation: send it to serious peer review. It deserves publication after minor revisions, mostly cleaning up the Proposition 3.2 statement and being explicit about the numerical rounding caveat.","headline":"A genuinely weaker finite-convergence certificate for sparse moment relaxations, with a clean proof and an extraction algorithm; the soft spots are minor and don't threaten the main theorem.","tokens_in":18337,"tokens_out":1324,"would_cite":true,"duration_ms":13468,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C26","44A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper identifies rank conditions on moment matrices that certify finite convergence of sparse moment relaxations and yield minimizers.","keywords":["moment-SOS relaxation","correlative sparsity","finite convergence","truncated moment problem","running intersection property","flat extension","minimizer extraction","polynomial optimization"],"falsifier":"A concrete calculation that would settle the claim: construct a correlatively sparse moment vector $y$ that satisfies the running intersection property, positive semidefiniteness, and all rank equalities in (1.4), but for which no atomic measure supported on the feasible set represents $y$. The paper's own example in section 5.3 performs the analogous test when the running intersection property fails; the same test with the property satisfied would falsify Theorem 1.1 if successful.","tokens_in":17416,"feed_emoji":"📐","tokens_out":5124,"duration_ms":43949,"temperature":0.7,"pith_summary":"This paper establishes a sufficient condition under which the sparse moment relaxation of a polynomial optimization problem is exact, meaning its optimal value equals the true global minimum, and it explains how to recover minimizers from the relaxation's solution. The condition combines a running intersection property on the variable cliques with rank equalities on the moment matrices of each clique and on overlap submatrices. The argument solves a correlatively sparse version of the truncated moment problem: it shows the relaxation's moment vector is represented by an atomic measure whose atoms lie in the feasible set. When the relaxation is optimal, those atoms are minimizers. This matters because sparse relaxations are used to reduce the cost of moment-SOS hierarchies, and knowing that they can be certified exact at a finite order, along with a way to extract the optimizers, is what makes the approach practically useful.","feed_headline":"Two rank tests certify exact sparse moment relaxations","feed_subtitle":"When they pass, the relaxation's solution provably gives the true optimum and its minimizers.","key_machinery":"The load-bearing mechanism is the flat extension theorem for truncated moment sequences, applied clique by clique. For each clique, positive semidefinite moment and localizing matrices together with the rank equality $\\mathrm{rank}\\,M_{\\Delta_i}^{\\omega}(y)=\\mathrm{rank}\\,M_{\\Delta_i}^{\\omega-d_i}(y)$ produce a unique finitely atomic representing measure for the clique subvector, supported on the clique's constraint set. The running intersection property and the overlap rank condition $\\mathrm{rank}\\,M_{\\Delta_i\\cap\\Delta_j}^{\\omega}(y)=\\mathrm{rank}\\,M_{\\Delta_i\\cap\\Delta_j}^{\\omega-1}(y)$ then guarantee that these local measures have consistent marginals on clique intersections, so a measure assembly construction (an atomic version of the lemma in [11]) stitches them into a global atomic representing measure. The atomic decomposition $y=\\sum_{k=1}^{r}\\lambda_k\\langle x_k\\rangle_{\\mathrm{sp}}^{2\\omega}$ is the identity that yields both exactness and minimizer extraction.","core_discovery":"The paper's central claim is Theorem 1.1: given a correlatively sparse moment vector $y$, if the cliques satisfy the running intersection property and, for every clique $i$, the moment and localizing matrices are positive semidefinite, the rank of the clique moment matrix equals the rank of its truncated submatrix, and the rank of the overlap moment matrix equals the rank of its truncated overlap submatrix, then $y$ is represented by a finitely atomic measure supported on the feasible set, with at least as many atoms as the largest clique moment rank. Corollary 1.2 applies this to the optimal solution of the sparse moment relaxation: under the same conditions the relaxation is exact, and the atoms of the representing measure are minimizers of the original polynomial optimization problem. The paper also gives an explicit atomic assembly procedure that recovers a representing measure with maximal support, and shows via examples that the rank conditions are not redundant and that the running intersection property cannot be dropped.","pith_inferences":["Editorial inference: the rank conditions can be checked a posteriori on any solved relaxation with standard linear algebra, so the test doubles as a cheap certificate of exactness in existing moment-SOS software.","Editorial inference: the maximal-support property means the extracted atoms give the full set of minimizers detectable at that relaxation order; solving the convex program (4.13) with a linear cost can produce sparser atomic representing measures, which may correspond to subsets of minimizers.","Editorial inference: the conjecture that sparse finite convergence never needs a higher order than dense convergence, if true, would strengthen the practical case for sparse hierarchies; the interpolator-polynomial argument in the paper is a first step but does not yet handle the overlap conditions.","Editorial inference: the same flat-extension-per-clique strategy is likely to extend to sparse polynomial matrix optimization, a direction the paper explicitly leaves open."],"forward_implications":["If the rank conditions hold for an optimal solution of the sparse moment relaxation, the relaxation is exact at that order: $f_{\\omega}^{*}=f^{*}$.","The extraction procedure returns at least $\\max_i \\mathrm{rank}\\,M_{\\Delta_i}^{\\omega}(y)$ distinct minimizers of the original polynomial optimization problem.","The recovered representing measure has maximal support among all atomic representing measures for $y$, so its atoms do not depend on the clique ordering.","The sufficient condition generalizes earlier criteria because it does not require equal ranks across cliques, nor rank-one overlap matrices, so it can detect finite convergence where previous results fail.","Sparse relaxations can be exact at relaxation orders lower than those required by dense relaxations, as illustrated by an example and formulated as a conjecture."],"supporting_citations":[{"why":"Supplies the flat extension theorem that converts rank equalities into finitely atomic representing measures for truncated moment sequences.","marker":"[4]"},{"why":"Provides the running intersection property, the measure assembly lemma, and the asymptotic convergence framework that this paper refines to finite order.","marker":"[11]"},{"why":"Gives the flat extension theorem (Theorem 5.29) used to prove uniqueness of representing measures on clique intersections.","marker":"[13]"},{"why":"Contains the prior sufficient condition that this paper generalizes, plus an example showing the running intersection property is needed.","marker":"[18]"},{"why":"Supplies the standard linear algebra algorithm used to extract clique atom measures from moment matrices.","marker":"[8]"},{"why":"Provides a revisited flat extension result that supports the existence and uniqueness of local representing measures.","marker":"[12]"},{"why":"Supplies the interpolator polynomial argument used to compare sparse and dense relaxation orders and to motivate the conjecture.","marker":"[1]"}],"fun_headline_variants":["Exact sparse relaxations via two rank conditions and running intersection","Rank tests guarantee exact sparse moment relaxations","When rank tests pass, sparse relaxations hit true optima","Certifying finite convergence in sparsity-exploiting relaxations","Sparse moment relaxations: rank checks and running intersection"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the flat extension theorem applies to each clique subvector, converting algebraic rank equalities into genuinely atomic local measures; if that local representability failed, the global representing measure would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Exact sparse relaxations via two rank conditions and running intersection","Rank tests guarantee exact sparse moment relaxations","When rank tests pass, sparse relaxations hit true optima","Certifying finite convergence in sparsity-exploiting relaxations","Sparse moment relaxations: rank checks and running intersection"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000353,"raw_usage":{"total_tokens":2080,"prompt_tokens":884,"completion_tokens":1196,"prompt_tokens_details":{"cached_tokens":768},"prompt_cache_hit_tokens":768,"prompt_cache_miss_tokens":116,"completion_tokens_details":{"reasoning_tokens":1115}},"tokens_in":116,"tokens_out":1196,"duration_ms":11078,"temperature":1.0,"reasoning_tokens":1115,"cache_read_input_tokens":768,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:25:55.060093+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete calculation that would settle the claim: construct a correlatively sparse moment vector $y$ that satisfies the running intersection property, positive semidefiniteness, and all rank equalities in (1.4), but for which no atomic measure supported on the feasible set represents $y$. The paper's own example in section 5.3 performs the analogous test when the running intersection property fails; the same test with the property satisfied would falsify Theorem 1.1 if successful.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the flat extension theorem that converts rank equalities into finitely atomic representing measures for truncated moment sequences."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the running intersection property, the measure assembly lemma, and the asymptotic convergence framework that this paper refines to finite order."},{"cited_title":"Laurent.Sums of squares, moment matrices and optimization over polynomials, volume 149 ofIMA Vol","cited_arxiv_id":null,"evidence_quote":"Gives the flat extension theorem (Theorem 5.29) used to prove uniqueness of representing measures on clique intersections."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Contains the prior sufficient condition that this paper generalizes, plus an example showing the running intersection property is needed."},{"cited_title":"Henrion and J.-B","cited_arxiv_id":null,"evidence_quote":"Supplies the standard linear algebra algorithm used to extract clique atom measures from moment matrices."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides a revisited flat extension result that supports the existence and uniqueness of local representing measures."},{"cited_title":"Baldi and B","cited_arxiv_id":null,"evidence_quote":"Supplies the interpolator polynomial argument used to compare sparse and dense relaxation orders and to motivate the conjecture."}],"review_version":1}