{"id":"f5df366e-2928-4275-8468-83217db54a35","arxiv_id":"2505.15056","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper reformulates completely positive tensor decomposition using maximal cliques of multi-hypergraphs, yielding an ideal-sparse moment hierarchy that is much faster than dense relaxations and provably equivalent.","lead":"A new method makes checking whether a tensor is completely positive much faster by exploiting its zero entries, splitting the large optimization problem into smaller pieces linked to hypergraph cliques. It matters because these tensor checks appear in computer vision, blind source separation, and multiway clustering, and the paper proves the faster formulation gives the same answer.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3.1 is buggy: `add C := ∅` inside the per-candidate loop discards split candidates; for a CP tensor with n=5, m=3 it misses three maximal cliques, so Corollary 3.8 and the coverage lemma behind Theorem 4.5 fail as stated.","rationale":"The reader identified Corollary 3.8 as the load-bearing assumption, which is exactly where the paper fails, but the failure mode is more serious than a missing proof for arbitrary tensors: the proposed Algorithm 3.1 is actually incorrect on completely positive tensors, including the main case m=3. The reset of `add C` inside the loop over candidates means that when two maximal candidates both contain the same zero-support set, only the splits from the last candidate are considered for reinsertion; splits from earlier candidates are discarded even when they are not subsets of any remaining candidate. The explicit n=5, m=3 CP tensor above demonstrates the omission of three maximal cliques. Because Lemma 4.4 and Theorem 4.5 rely on the generated sets covering every support that avoids the zero entries, the central equivalence val = valisp is not true for the algorithm as stated. The likely repair is straightforward: initialize `add C` once per zero entry and accumulate splits from all affected candidates; with that fix the induction in Proposition 3.7 goes through and the reformulation is plausibly correct. However, as submitted, the main theorem is unsupported and contradicted by a concrete CP instance, so the current version should not be accepted. The numerical experiments and tables should be rerun after the fix, since the reported cliques may also have been produced by an implementation that already deviates from the printed algorithm.","tokens_in":22085,"tokens_out":29706,"duration_ms":254234,"concrete_test":"Implement Algorithm 3.1 exactly as printed and run it on the CP tensor A = sum_{U in C} (1_U)^{⊗3} with n=5, m=3, C = {{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5}}. Record the returned set C_end. If C_end omits any of {2,3,4}, {2,3,5}, {2,4,5}, then Proposition 3.7 and Corollary 3.8 are false; rerunning with `add C` initialized once per zero entry should return all six maximal cliques and confirm the one-line fix.","verdict_should_be":"REJECT","load_bearing_attack":"The paper's central equivalence Theorem 4.5 depends on Corollary 3.8, which asserts that Algorithm 3.1 outputs exactly the maximal subsets of [n] containing no zero-support set. The algorithm as written has a concrete flaw: in the Split Procedure, `add C := ∅` is executed inside the loop over S (line 8), so when two candidates both contain the zero-support set being processed, only the splits from the last such candidate survive. This is not merely a proof gap: it produces the wrong output on completely positive inputs, including m=3. Take n=5, m=3 and let A be the CP tensor given by rank-one factors with supports U in C = {{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5}}, e.g. A = sum_{U in C} (1_U)^{⊗3}. The zero entries are exactly those triples whose support contains {1,2}, plus (3,4,5); this tensor is completely positive and satisfies the zero-entry dominance property. Running Algorithm 3.1 in lexicographic order, the zero entries {1,1,2}, {1,2,2}, {1,2,3}, {1,2,4}, {1,2,5} leave C = {{2,3,4,5},{1,3,4,5}}. When the later zero (3,4,5) is processed, both remaining candidates contain {3,4,5}; the reset of `add C` discards the splits {2,3,5},{2,3,4},{2,4,5} generated from the first candidate. The output is only {1,4,5},{1,3,5},{1,3,4}. The missing sets {2,3,4},{2,3,5},{2,4,5} are maximal cliques, so Corollary 3.8 is false. Consequently Lemma 4.4's identity K = cK_1 ∪ ... ∪ cK_p fails: a measure supported on a vector with support {2,3,4} lies in K but in no cK_k for the generated cliques, so the equality val = valisp in Theorem 4.5 is not established and is false for this instance as formulated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies completely positive (CP) tensor decomposition via moment relaxations. It defines maximal cliques of an m-uniform multi-hypergraph associated with the zero pattern of a symmetric tensor, proposes Algorithm 3.1 to compute these cliques, and uses them to build an ideal-sparse reformulation of the A-truncated moment problem. The main theoretical results are Corollary 3.8 (the algorithm returns the maximal subsets avoiding zero supports), Lemma 4.4 (K is the union of the cK_k), Theorem 4.5 (equivalence of dense and sparse problems), and Theorem 4.10 (convergence and finite convergence of the sparse hierarchy). Numerical experiments compare the sparse hierarchy with dense moment relaxations and with TSSOS.","tokens_in":22493,"tokens_out":17020,"duration_ms":147827,"significance":"The contribution is potentially significant: the sparse reformulation replaces one measure on R^n with several measures on |V_k|-dimensional subspaces, so the largest SDP matrix size is governed by the largest maximal clique rather than by n. The adaptation of ideal-sparsity from graphs to m-uniform multi-hypergraphs via zero dominance is a natural and useful extension, and the convergence analysis sensibly mirrors the dense machinery. The numerical tables give informative evidence of speedups. However, the key algorithmic lemma underpinning the reformulation is incorrect as stated; because the central equivalence depends on it, the claims in their current form are not valid. The underlying idea is salvageable with a corrected algorithm and proof.","major_comments":[{"comment":"The instruction `add C := ∅` is placed inside the loop `for S ∈ C`, so when a zero support is contained in more than one current candidate, the splits generated for all but the last candidate are discarded. This is not merely a proof gap: it changes the output on CP inputs. Let n=5, m=3 and A = Σ_{U∈C} (1_U)^{⊗3} with C = {{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5}}. This A is CP, and its zero entries are exactly those with support containing {1,2}, plus (3,4,5). After processing the zeros with support {1,2}, the candidate set is {{2,3,4,5},{1,3,4,5}}; processing (3,4,5), both candidates contain {3,4,5}, and the reset in Step 8 keeps only the splits from the second candidate. The algorithm outputs {1,3,4},{1,3,5},{1,4,5} and misses {2,3,4},{2,3,5},{2,4,5}. These missed sets are maximal cliques, so Corollary 3.8 is false. Consequently Lemma 4.4 fails: a measure supported on a vector with support {2,3,4} lies in K but in no cK_k, and the equality val = valisp of Theorem 4.5 fails for this example because the sparse problem cannot match A_234 = 1. The fix is to initialize `add C := ∅` before the loop over S; the proof of Corollary 3.8 must then be supplied without relying on Proposition 3.7's CP assumption, since the corollary is claimed for arbitrary symmetric tensors.","section":"Section 3.3, Algorithm 3.1 (Step 8)"},{"comment":"The finite-convergence proof contains an unjustified rank argument. From `rank M_0 ≤ rank M_{dK} ≤ ... ≤ rank M_{(R+1)dK} ≤ |Supp(µ_k)| ≤ R` one can only conclude that there exists some l ∈ {1,...,R+1} with rank M_{(l-1)dK} = rank M_{ldK}; the proof asserts `there exists l ≥ R+1`, which is not a consequence of the pigeonhole principle. If the first equality occurs at l dK < t0, the flatness condition (4.9) is not satisfied. Moreover, a common l is needed for all k simultaneously, and the argument does not produce one. The statement is likely salvageable by taking t ≥ (R + t0)dK and using the fact that ranks of moment matrices of a finitely atomic measure saturate for sufficiently large s, but the proof as written does not establish finite convergence.","section":"Section 4.2, Theorem 4.10(5)"}],"minor_comments":[{"comment":"The manuscript contains numerous typos and grammatical errors (e.g., 'as follow', 'hiarachy', 'charaterized', 'perferom', 'reseach', 'asyptotic') that should be corrected in a revision.","section":"Throughout"},{"comment":"The statement `Ω(ξisp_t) ⊆ Ω(ξt)` is formally incorrect because the two feasible sets live in different spaces; the intended statement is that the image of Ω(ξisp_t) under the linear map z_α = Σ_k ⟨x^α|_{V_k}, z_k⟩ is contained in Ω(ξt).","section":"Section 4.2, Lemma 4.6"},{"comment":"The header `ξcp_t` appears without a definition; if it denotes the dense optimal value ξ_t for a CP tensor, please clarify.","section":"Section 5.2, Table 5"},{"comment":"The column header `p n` is unclear; the table should indicate the nonzero density and the order d in the header rather than only in the text.","section":"Section 5.1, Table 2"},{"comment":"The proof of Proposition 3.7 contains a typo in `1 ≤ i1 ≤ · · · ım ≤ n`.","section":"Section 3.3"},{"comment":"The relation between Algorithm 3.1 as printed and the implementation used for the numerical experiments should be clarified; for example, the cliques reported in Table 4 include sets that would be lost by the printed loop if multiple candidates contained the same zero support.","section":"Section 5, Tables 3–5 and 8"}],"recommendation":"major_revision","confidential_remarks":"The paper's main idea is sound and the error is localized, so I recommend major revision rather than rejection. The corrected algorithm must be retested and the proof of Corollary 3.8 must be genuinely independent of the CP dominance assumption. The comparison with TSSOS is useful, but the manuscript needs a careful proofreading pass and clarification of the numerical implementation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis paper extends Korda et al.'s ideal-sparsity from graph constraints x_i x_j = 0 to m-uniform hypergraph constraints x_{i1} ... x_{im} = 0, for completely positive tensor decomposition. That is a genuine and useful extension. The clique definition and the reformulation (4.5) are natural, Theorem 4.5 would be a strong result if the clique cover were correct, and the convergence proof in Theorem 4.10 is careful and follows from the dense machinery plus Lemma 4.2. The numerical tables show dramatic SDP size reductions. Credit where due: the authors identify the right structure and give a fairly complete equivalence proof given correct maximal cliques.\n\nThe reader's concern about Corollary 3.8 is well placed, and the stress-test sharpens it: the algorithm is wrong, not merely unproven. Algorithm 3.1 executes `add C := ∅` inside the loop over candidates S (line 8), so when two candidates both contain the zero entry being split, the splits from all but the last candidate are discarded. This is not a missing proof; it produces wrong output on a completely positive tensor. Take n=5, m=3 and A = sum over U in {{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5}} of (1_U)^{⊗3}. The zero entries are exactly triples containing {1,2} plus (3,4,5), and A is CP. Running Algorithm 3.1 in lexicographic order, the zero (1,1,2) leaves candidates {2,3,4,5} and {1,3,4,5}; the next zero with support {1,2} resets `add C` while processing the second candidate, and by the time (3,4,5) is processed the splits {2,3,4}, {2,3,5}, {2,4,5} are gone. The output is only the three cliques containing 1. Those missing sets are maximal subsets avoiding all zero supports, so Corollary 3.8 is false as stated, Lemma 4.4's covering identity fails, and Theorem 4.5's equality val = valisp is not established. Corollary 3.9 inherits this.\n\nThe fix looks easy - move `add C := ∅` outside the for-S loop - and I expect the intended algorithm is correct, but the current text cannot be used.\n\nMinor issues: no code or data released, so the numerical claims are not independently reproducible; the random SOS objective and rank tolerances are not specified; and Corollary 3.8 is dismissed with 'trivially' rather than proven.\n\nWho this is for: people working on moment relaxations for tensor decompositions and ideal-sparsity. It deserves a serious referee - the core idea is right and the main theorem is probably salvageable - but it should not be accepted without the algorithm fixed and retested.\n\nRecommendation: send to peer review, major revision.","headline":"The ideal-sparse reformulation is a good idea, but Algorithm 3.1 as written drops valid cliques on a simple CP counterexample, so the main equivalence theorem is not established.","tokens_in":23144,"tokens_out":7127,"would_cite":false,"duration_ms":51720,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A69","44A60","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"A completely positive tensor's zero pattern defines a multi-hypergraph, and the paper claims its decomposition problem is exactly the ideal-sparse moment problem over the hypergraph's maximal cliques, so that semidefinite relaxations…","keywords":["completely positive tensor","tensor decomposition","moment problem","ideal-sparsity","multi-hypergraph","maximal clique","semidefinite relaxation","zero-entry dominance"],"falsifier":"For a small dimension such as $n=4$ and order $m=3$, enumerate all nonnegative symmetric tensors with a fixed sparse zero pattern, run Algorithm 3.1 on each, and compare the output with brute-force enumeration of the maximal subsets of $[n]$ that contain no support of a zero entry. Any mismatch falsifies Corollary 3.8 and consequently the equality $val=val^{isp}$ in Theorem 4.5.","tokens_in":21809,"feed_emoji":"🧮","tokens_out":11134,"duration_ms":87821,"temperature":0.7,"pith_summary":"This paper claims that deciding whether a symmetric tensor is completely positive, and finding its decomposition, can be reformulated as an ideal-sparse generalized moment problem: instead of one measure on the whole nonnegative sphere, one optimizes several measures, each supported on a low-dimensional subset associated with a maximal clique of the tensor's support multi-hypergraph. The reformulation rests on a zero-entry dominance property: for a completely positive tensor, a positive entry forces every sub-multiset of its indices to be positive, so the zero pattern is governed by a hypergraph. The paper proposes Algorithm 3.1 to generate the maximal cliques of this hypergraph, yielding a necessary condition for complete positivity. It then proves the optimum of the sparse reformulation equals the optimum of the dense moment problem (Theorem 4.5) and that the ideal-sparse moment hierarchy converges, with finite convergence whenever the dense hierarchy converges finitely (Theorem 4.10). If correct, complete positivity can be certified and decompositions extracted by semidefinite programs whose matrix sizes are governed by the largest maximal clique rather than the full tensor dimension.","feed_headline":"New method shrinks complete-positivity SDPs to clique size","feed_subtitle":"Reformulation trades one big moment problem for small ones on each maximal clique of the support hypergraph.","key_machinery":"The load-bearing object is the $m$-uniform support multi-hypergraph of the tensor: vertices are the indices $[n]$, and a multiset of $m$ indices is an edge exactly when the corresponding tensor entry is nonzero. For completely positive tensors, the zero-entry dominance property makes cliques of this hypergraph well-behaved: a positive entry's index set must lie inside some maximal clique, so every decomposition vector has support inside one clique. Algorithm 3.1 generates these maximal cliques by initializing with $[n]$ and, whenever a zero entry is encountered, splitting every candidate set that contains the entry's index support by deleting one index at a time. The ideal generated by the monomials $x_{i_1}\\cdots x_{i_m}$ attached to zero entries defines the sets $K_k$ on which the sparse measures live; Theorem 4.5 transfers the objective and constraints between the dense problem and the clique-wise problem, and Theorem 4.10 transfers convergence.","core_discovery":"On the paper's own terms, the central discovery is that the completely positive tensor decomposition problem (2.1) is exactly equivalent to the ideal-sparse generalized moment problem (4.5): the optimal values coincide, $val = val^{isp}$, and feasibility of one implies feasibility of the other. The link is the support multi-hypergraph of the tensor, whose maximal cliques are the maximal index sets containing no support of a zero entry; the zero-entry dominance lemma guarantees that every decomposition vector of a completely positive tensor is supported inside one of these cliques. The paper's Algorithm 3.1 enumerates these cliques by repeatedly splitting candidate sets across each zero entry's index support, and it also produces a necessary condition for complete positivity. Consequently the dense moment hierarchy for the A-truncated moment problem can be replaced by a hierarchy of smaller semidefinite programs over the cliques, with asymptotic convergence and finite convergence whenever the dense hierarchy has it.","pith_inferences":["Editorial inference: the correctness of Algorithm 3.1 for non-completely-positive tensors is the single point on which the equivalence rests; a counterexample would invalidate the sparse reformulation and not merely the necessary condition.","Editorial inference: the clique-based reformulation should extend to any moment problem whose zero pattern defines monomial constraints, and the paper itself lists non-symmetric and complex completely positive tensors as natural candidates for such an extension.","Editorial inference: combined with the paper's numerical observation that most randomly generated sparse tensors fail the necessary condition, the algorithm can act as a fast pre-filter before any semidefinite relaxation is attempted."],"forward_implications":["The largest semidefinite matrix in the relaxation is indexed by the largest maximal clique of the support multi-hypergraph, so the computational cost scales with the clique size rather than the tensor dimension $n$.","Algorithm 3.1 alone gives a necessary condition for complete positivity: if a positive entry's index set lies in no generated maximal clique, the tensor is not completely positive.","The ideal-sparse moment hierarchy converges to the true optimum of the completely positive tensor decomposition problem, and it is finitely convergent whenever the dense moment hierarchy is.","When a flat optimal solution of the sparse hierarchy is found, a completely positive decomposition can be extracted, with each decomposition vector supported inside one maximal clique.","In the paper's numerical tests, the sparse semidefinite relaxations are solved much faster than the dense ones, and they exploit a sparsity structure different from correlative and term sparsity approaches."],"supporting_citations":[{"why":"Introduces ideal-sparsity for generalized moment problems and the maximal-clique reformulation that this paper extends from quadratic to $m$-th order monomial ideals.","marker":"[11]"},{"why":"Characterizes completely positive tensors through a truncated moment problem, which is the starting formulation (2.1).","marker":"[6]"},{"why":"Establishes the A-truncated K-moment problem theory, including boundedness, flatness, and finite convergence results that Theorem 4.10 adapts to the sparse hierarchy.","marker":"[15]"},{"why":"Supplies the zero-entry dominance property of completely positive tensors that underlies the clique definition and the correctness of Algorithm 3.1.","marker":"[20]"},{"why":"Gives the flatness condition for existence of a finitely atomic representing measure, used to extract sparse decompositions.","marker":"[4]"},{"why":"Completes the flatness-based moment extraction theory used in the dense hierarchy and transferred to the sparse one.","marker":"[5]"},{"why":"Defines completely positive tensors and provides the decomposition examples used as benchmarks in the numerical section.","marker":"[21]"}],"fun_headline_variants":["Clique-based sparsity slashes CP tensor SDP cost","Maximal cliques shrink CP tensor decompositions to smaller SDPs","Ideal-sparse reformulation: smaller SDPs on maximal cliques","Zero-pattern cliques make CP tensor SDPs cheaper","CP tensor decomposition via ideal-sparse clique moments"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Algorithm 3.1 outputs exactly the maximal subsets of $[n]$ that contain no support of a zero entry for every symmetric tensor; the paper proves this for completely positive tensors and asserts the general case follows 'trivially' without a detailed proof.","fun_headline_variants_meta":{"raw":{"variants":["Clique-based sparsity slashes CP tensor SDP cost","Maximal cliques shrink CP tensor decompositions to smaller SDPs","Ideal-sparse reformulation: smaller SDPs on maximal cliques","Zero-pattern cliques make CP tensor SDPs cheaper","CP tensor decomposition via ideal-sparse clique moments"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1454,"prompt_tokens":894,"completion_tokens":560,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":510,"completion_tokens_details":{"reasoning_tokens":472}},"tokens_in":510,"tokens_out":560,"duration_ms":6216,"temperature":1.0,"reasoning_tokens":472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:26:00.026059+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small dimension such as $n=4$ and order $m=3$, enumerate all nonnegative symmetric tensors with a fixed sparse zero pattern, run Algorithm 3.1 on each, and compare the output with brute-force enumeration of the maximal subsets of $[n]$ that contain no support of a zero entry. Any mismatch falsifies Corollary 3.8 and consequently the equality $val=val^{isp}$ in Theorem 4.5.","supporting_citations":[{"cited_title":"Korda, M","cited_arxiv_id":null,"evidence_quote":"Introduces ideal-sparsity for generalized moment problems and the maximal-clique reformulation that this paper extends from quadratic to $m$-th order monomial ideals."},{"cited_title":"F an and A","cited_arxiv_id":null,"evidence_quote":"Characterizes completely positive tensors through a truncated moment problem, which is the starting formulation (2.1)."},{"cited_title":"Qi and Z","cited_arxiv_id":null,"evidence_quote":"Supplies the zero-entry dominance property of completely positive tensors that underlies the clique definition and the correctness of Algorithm 3.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the flatness condition for existence of a finitely atomic representing measure, used to extract sparse decompositions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Completes the flatness-based moment extraction theory used in the dense hierarchy and transferred to the sparse one."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines completely positive tensors and provides the decomposition examples used as benchmarks in the numerical section."}],"review_version":1}