Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

An ideal-sparse generalized moment problem reformulation for completely positive tensor decomposition exploiting maximal cliques of multi-hypergraphs

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2505.15056 v1 pith:OR6K6TD2 submitted 2025-05-21 math.OC

classification math.OC MSC 15A6944A6090C22
keywords completelypositivetensordecompositionmomentproblemideal-sparsitymulti-hypergraphmaximalcliquesemidefiniterelaxationzero-entrydominance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

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.

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 (2)
  1. [Section 3.3, Algorithm 3.1 (Step 8)] 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.
  2. [Section 4.2, Theorem 4.10(5)] 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.
minor comments (6)
  1. [Throughout] The manuscript contains numerous typos and grammatical errors (e.g., 'as follow', 'hiarachy', 'charaterized', 'perferom', 'reseach', 'asyptotic') that should be corrected in a revision.
  2. [Section 4.2, Lemma 4.6] 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).
  3. [Section 5.2, Table 5] The header `ξcp_t` appears without a definition; if it denotes the dense optimal value ξ_t for a CP tensor, please clarify.
  4. [Section 5.1, Table 2] 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.
  5. [Section 3.3] The proof of Proposition 3.7 contains a typo in `1 ≤ i1 ≤ · · · ım ≤ n`.
  6. [Section 5, Tables 3–5 and 8] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the ideal-sparse reformulation is derived from zero-entry data and standard moment theory, with no fitted parameter, self-referential definition, or load-bearing self-citation.

full rationale

The paper's derivation chain is: the support multi-hypergraph is read off from the zero entries of A (Section 3.2); Algorithm 3.1 outputs maximal subsets avoiding those zero-entry supports (Corollary 3.8); Lemma 4.4 shows K is the union of the corresponding clique-restricted sets; Theorem 4.5 proves equality of the dense and sparse optima; Theorem 4.10 transfers convergence from the dense hierarchy. None of these steps defines the target value as an input or fits a parameter to the output. The zero entries are data, not estimated constants, and the equality val = valisp is proved by an explicit measure-theoretic bijection rather than imposed by construction. The authors do not cite their own prior work as the basis for a uniqueness or ansatz claim; the invoked results are from Korda et al., Nie, Fan and Zhou, and Qi et al., and the theorem statements are reproduced or referenced as external mathematical facts. The reformulation is an extension of the known ideal-sparsity framework to m-th order monomial ideals, not a renaming of the answer. A proof gap exists: Corollary 3.8 is stated for all symmetric tensors and justified by 'This result can be obtained through the proof of Proposition 3.7 trivially', while Proposition 3.7 is proved only for completely positive tensors; and the algorithm's split procedure may be flawed on some inputs. However, a correctness defect in an auxiliary clique-generation routine is not circularity: it does not make the central equivalence, convergence theorem, or computational claims equivalent to their inputs by definition. The paper is also benchmarked against independently known examples from Fan and Zhou, which gives the claimed hierarchy independent content. Therefore no significant circularity is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted constants and no new physical entities. Its main imported assumptions are the zero-dominance property of CP tensors and the dense moment hierarchy theory; the least-supported input is the correctness of Algorithm 3.1 for non-CP tensors.

assumptions (4)
  • domain assumption Zero entry dominance property (Lemma 3.4): for a completely positive tensor, if A_{j1...jm} > 0 and {i1...im} is a subset of {j1...jm}, then A_{i1...im} > 0.
    Imported from Qi and Luo [20]; it is the basis for the clique definition and for Lemma 4.2 that every decomposition vector's support lies in a maximal clique.
  • domain assumption Correctness of Algorithm 3.1 for arbitrary symmetric tensors (Corollary 3.8): the algorithm outputs exactly the maximal subsets of [n] that contain no zero-entry support.
    The paper asserts this trivially from Proposition 3.7, which is proven only for completely positive tensors. The reformulation and the necessary condition in Corollary 3.9 depend on it.
  • domain assumption Assumption 4.9: the random SOS objective F is generic, and F and F|Vk lie in the interior of the SOS cone.
    Used in Theorem 4.10 to guarantee existence of optimizers, strong duality, and boundedness of the sparse hierarchy.
  • standard math Known convergence results for the dense moment hierarchy (Theorem 2.2 from Nie [15] and Fan and Zhou [6]).
    The finite convergence result of the sparse hierarchy is derived from the dense one.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An ideal-sparse generalized moment problem reformulation for completely positive tensor decomposition exploiting maximal cliques of multi-hypergraphs." pith.science (2026). https://pith.science/paper/OR6K6TD2

@misc{pith2026250515056,
  author       = {Pith},
  title        = {Pith review of: An ideal-sparse generalized moment problem reformulation for completely positive tensor decomposition exploiting maximal cliques of multi-hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OR6K6TD2}},
  note         = {Machine review of arXiv:2505.15056}
}
read the original abstract

In this paper, we consider the completely positive tensor decomposition problem with ideal-sparsity. First, we propose an algorithm to generate the maximal cliques of multi-hypergraphs associated with completely positive tensors. This also leads to a necessary condition for tensors to be completely positive. Then, the completely positive tensor decomposition problem is reformulated into an ideal-sparse generalized moment problem. It optimizes over several lower dimensional measure variables supported on the maximal cliques of a multi-hypergraph. The moment-based relaxations are applied to solve the reformulation. The convergence of this ideal-sparse moment hierarchies is studied. Numerical results show that the ideal-sparse problem is faster to compute than the original dense formulation of completely positive tensor decomposition problems. It also illustrates that the new reformulation utilizes sparsity structures that differs from the correlative and term sparsity for completely positive tensor decomposition problems.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Representing Higher-Order Networks: A Survey of Graph-Based Frameworks

    cs.SI 2026-03 unverdicted novelty 4.0 of 10

    A survey organizing higher-order network formalisms into four families with a master comparison table, plus ~17 new superhypergraph-style definitions whose only supporting theorems are well-definedness checks.

Reference graph

Works this paper leans on

30 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [1]

    Bezanson, A

    J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia: A fresh approach to nu- merical computing, SIAM review, 59 (2017), pp. 65–98, https://doi.org/https://doi.org/ 10.1137/141000671

  2. [2]

    Che and Y

    M. Che and Y. Wei, Multiplicative algorithms for symmetric nonnegative tensor factorizations and its applications , Journal of Scientific Computing, 83 (2020), p. 53, https://doi.org/ https://doi.org/10.1007/s10915-020-01233-w

  3. [3]

    Cichocki, R

    A. Cichocki, R. Zdunek, A. H. Phan, and S.-i. Amari, Nonnegative matrix and tensor factor- izations: applications to exploratory multi-way data analysis and blind source separation , John Wiley & Sons, 2009. 22

  4. [4]

    R. E. Curto and L. A. Fialkow, Solution of the truncated complex moment problem for flat data, vol. 568, American Mathematical Soc., 1996

  5. [5]

    R. E. Curto and L. A. Fialkow, The truncated complex k-moment problem , Transactions of the American mathematical society, 352 (2000), pp. 2825–2855, https://doi.org/https: //doi.org/10.1090/S0002-9947-00-02472-7

  6. [6]

    F an and A

    J. F an and A. Zhou, A semidefinite algorithm for completely positive tensor decomposition , Computational Optimization and Applications, 66 (2017), pp. 267–283, https://doi.org/ https://doi.org/10.1007/s10589-016-9870-9

  7. [7]

    Z. He, A. Cichocki, S. Xie, and K. Choi, Detecting the number of clusters in n-way prob- abilistic clustering , IEEE Transactions on Pattern Analysis and Machine Intelligence, 32 (2010), pp. 2006–2021, https://doi.org/10.1109/TPAMI.2010.15

  8. [8]

    Henrion and J.-B

    D. Henrion and J.-B. Lasserre, Detecting global optimality and extracting solutions in glop- tipoly, in Positive polynomials in control, Springer, 2005, pp. 293–310, https://doi.org/ https://doi.org/10.1007/10997703 15

Show all 30 references
  1. [9]

    Henrion, J.-B

    D. Henrion, J.-B. Lasserre, and J. L¨ofberg, GloptiPoly 3: moments, optimization and semidefinite programming , Optimization Methods & Software, 24 (2009), pp. 761–779, https://doi.org/https://doi.org/10.1080/10556780802699201

  2. [10]

    T. G. Kolda, Numerical optimization for symmetric tensor decomposition , Mathemat- ical Programming, 151 (2015), pp. 225–248, https://doi.org/https://doi.org/10.1007/ s10107-015-0895-0

  3. [11]

    Korda, M

    M. Korda, M. Laurent, V. Magron, and A. Steenkamp, Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks , Mathe- matical Programming, 205 (2024), pp. 703–744, https://doi.org/https://doi.org/10.1007/ s10107-023-01993-x

  4. [12]

    Lim and P

    L.-H. Lim and P. Comon, Nonnegative approximations of nonnegative tensors , Journal of Chemometrics: A Journal of the Chemometrics Society, 23 (2009), pp. 432–441, https: //doi.org/https://doi.org/10.1002/cem.1244

  5. [13]

    Magron and J

    V. Magron and J. W ang, Tssos: a julia library to exploit sparsity for large-scale polynomial optimization, arXiv preprint arXiv:2103.00915, (2021)

  6. [14]

    Magron and J

    V. Magron and J. W ang, Sparse polynomial optimization: theory and practice , World Scien- tific, 2023

  7. [15]

    Nie, The A-truncated K-moment problem, Foundations of Computational Mathematics, 14 (2014), pp

    J. Nie, The A-truncated K-moment problem, Foundations of Computational Mathematics, 14 (2014), pp. 1243–1276, https://doi.org/https://doi.org/10.1007/s10208-014-9225-9

  8. [16]

    Nie, Optimality conditions and finite convergence of lasserre’s hierarchy , Mathemat- ical programming, 146 (2014), pp

    J. Nie, Optimality conditions and finite convergence of lasserre’s hierarchy , Mathemat- ical programming, 146 (2014), pp. 97–121, https://doi.org/https://doi.org/10.1007/ s10107-013-0680-x

  9. [17]

    Nie, Moment and Polynomial Optimization , SIAM, 2023

    J. Nie, Moment and Polynomial Optimization , SIAM, 2023

  10. [18]

    Panagakis, J

    Y. Panagakis, J. Kossaifi, G. G. Chrysos, J. Oldfield, M. A. Nicolaou, A. Anandkumar, and S. Zafeiriou, Tensor methods in computer vision and deep learning , Proceedings of the IEEE, 109 (2021), pp. 863–890, https://doi.org/10.1109/JPROC.2021.3074329

  11. [19]

    K. J. Pearson and T. Zhang, On spectral hypergraph theory of the adjacency tensor , Graphs and Combinatorics, 30 (2014), pp. 1233–1248, https://doi.org/https://doi.org/10.1007/ s00373-013-1340-x

  12. [20]

    Qi and Z

    L. Qi and Z. Luo, Tensor analysis: spectral theory and special tensors , SIAM, 2017

  13. [21]

    L. Qi, C. Xu, and Y. Xu, Nonnegative tensor factorization, completely positive tensors, and a hierarchical elimination algorithm , SIAM Journal on Matrix Analysis and Applications, 35 (2014), pp. 1227–1241, https://doi.org/https://doi.org/10.1137/13092232X

  14. [22]

    Shashua and T

    A. Shashua and T. Hazan, Non-negative tensor factorization with applications to statistics and computer vision, in Proceedings of the 22nd international conference on Machine learn- ing, 2005, pp. 792–799, https://doi.org/https://doi.org/10.1145/1102351.1102451

  15. [23]

    Torres-Jimenez, J

    J. Torres-Jimenez, J. C. Perez-Torres, and G. Maldonado-Martinez, hclique: An exact algorithm for maximum clique problem in uniform hypergraphs , Discrete Mathematics, Algorithms and Applications, 9 (2017), p. 1750078, https://doi.org/https://doi.org/10. 1142/S1793830917500781

  16. [24]

    W aki, S

    H. W aki, S. Kim, M. Kojima, and M. Muramatsu, Sums of squares and semidefinite pro- gram relaxations for polynomial optimization problems with structured sparsity , SIAM Journal on Optimization, 17 (2006), pp. 218–242, https://doi.org/https://doi.org/10.1137/ 050623802

  17. [25]

    W ang and V

    J. W ang and V. Magron, A second order cone characterization for sums of nonnegative cir- cuits, in Proceedings of the 45th International Symposium on Symbolic and Algebraic Com- putation, 2020, pp. 450–457, https://doi.org/https://doi.org/10.1145/3373207.3404033

  18. [26]

    W ang, V

    J. W ang, V. Magron, and J.-B. Lasserre, TSSOS: A moment-sos hierarchy that exploits COMPLETELY POSITIVE TENSOR DECOMPOSITION 23 term sparsity, SIAM Journal on optimization, 31 (2021), pp. 30–58, https://doi.org/https: //doi.org/10.1137/19M1307871

  19. [27]

    W ang, V

    J. W ang, V. Magron, J. B. Lasserre, and N. H. A. Mai, CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization, ACM Transactions on Mathematical Software, 48 (2022), pp. 1–26, https://doi.org/https://doi.org/10.1145/3569709

  20. [28]

    Wu and J.-K

    Q. Wu and J.-K. Hao, A review on algorithms for maximum clique problems , European Journal of Operational Research, 242 (2015), pp. 693–709, https://doi.org/https://doi. org/10.1016/j.ejor.2014.09.064

  21. [29]

    C. Xu, Z. Luo, L. Qi, and Z. Chen, {0, 1} completely positive tensors and multi-hypergraphs, Linear Algebra and its Applications, 510 (2016), pp. 110–123, https://doi.org/https://doi. org/10.1016/j.laa.2016.08.016

  22. [30]

    A. Zhou, J. F an, and Q. W ang, Completely positive tensors in the complex field , Science China mathematics, 63 (2020), pp. 1219–1234, https://doi.org/https://doi.org/10.1007/ s11425-017-9437-2

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.