Pith. sign in

REVIEW 5 minor 46 references

On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization

T0 review · 0 major / 5 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Exact entrywise power factorization equals low-rank matrix signing: strongly NP-hard in general, polynomial for fixed rank, FPT for generic inputs; Frobenius approximation is already NP-hard at rank 2.

desk verdict Clean complexity map for EPMF/LRMS: strong NP-hardness, fixed-r poly-time via skeleton + symmetric span, generic FPT, and rank-2 Frobenius hardness; proofs and code check out. read the letter →

arxiv 2607.04875 v2 pith:PJG7I5Z3 submitted 2026-07-06 cs.CC cs.IRmath.COstat.ML

Nicolas Gillis , Subhayan Saha , Stefano Sicilia , Arnaud Vandaele This is my paper · ORCID
classification cs.CCcs.IRmath.COstat.ML MSC 68Q1715A2390C60
keywords entrywisepowermatrixfactorizationlow-ranksigningsignlessranksquare-rootfixed-parametertractablestrongNP-hardnessFrobeniusapproximationnonlineardecompositions
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

The paper completely charts the computational complexity of entrywise power matrix factorization (EPMF), the problem of writing a nonnegative matrix as the entrywise p-th power of the absolute values of a rank-r matrix. Exact EPMF is shown to be identical to the combinatorial problem of flipping signs of a given matrix so that the result has rank at most r (low-rank matrix signing, LRMS). When the target rank r is part of the input, LRMS and therefore exact EPMF are strongly NP-hard. When r is fixed the same problem becomes polynomial-time solvable by an explicit enumeration that exploits skeleton factorizations and the low dimension of the space of symmetric matrices. For generic inputs the same algorithm is fixed-parameter tractable in r and in fact linear in the number of matrix entries. In the approximate setting that minimizes the Frobenius residual, hardness already appears at the smallest nontrivial rank r=2.

What carries the argument

Skeleton decomposition of a candidate rank-k matrix: once a nonsingular k imes k signed block is fixed, the remaining rows and columns are completely determined by linear dependence; the feasibility constraints |w_i^T h_j|=M_{ij} are rewritten as linear equations on the binom(k+1,2)-dimensional space of k imes k symmetric matrices, so only a polynomial-size subset of candidate rows needs to be enumerated.

What would settle it

Construct a family of non-generic (for example, integer or highly structured) matrices whose signing rank is known to be small, run the algorithm of Theorem 3.2/3.8, and check whether the early-exit conditions still fire or whether the running time reverts to the slower fixed-rank enumeration that is exponential in both dimensions.

Watch

Extended reading notes

Core claim

Exact EPMF is computationally equivalent to low-rank matrix signing. The latter (and hence the former) is strongly NP-hard when the rank is part of the input, admits a polynomial-time algorithm when the rank is fixed, and becomes fixed-parameter tractable with running time 2^{O(r^3)} O(mn) on generic matrices even when the rank is variable. The least-squares (Frobenius) version of EPMF is NP-hard already for rank 2.

Load-bearing premise

The fixed-parameter tractability claim for variable rank holds only when the input is generic, so that every signed k imes k block is automatically full-rank and every set of binom(k+1,2) outer products spans the symmetric matrices with probability one.

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

0 major / 5 minor

Summary. The paper maps the computational complexity of entrywise power matrix factorization (EPMF) for nonnegative matrices. Exact EPMF is shown equivalent to low-rank matrix signing (LRMS): decide whether signs can be assigned to the entries of a given nonnegative matrix so that the signed matrix has rank at most r. When r is part of the input, LRMS (hence exact EPMF) is strongly NP-hard by a many-one reduction from Monotone NAE-3SAT that produces matrices with entries in a fixed finite set (Theorem 2.2, Corollary 2.3). When r is fixed the problem is solvable in polynomial time by an explicit enumeration algorithm that builds a skeleton factorization and filters candidate rows/columns via the finite-dimensional space of symmetric matrices (Theorem 3.2, Algorithm 1). For generic rank-r* inputs the same algorithm is FPT in r with running time 2^{O(r^3)} O(mn) (Theorem 3.8). In the Frobenius-norm approximate setting, EPMF is already NP-hard for the smallest nontrivial rank r=2 via a reduction from Cut-Norm (Theorem 4.1).

Significance. The work supplies a complete, self-contained complexity landscape for a natural family of nonlinear matrix decompositions that unifies the modulus model and componentwise square factorization (square-root rank). The strong NP-hardness result improves the earlier weak NP-hardness for square-root rank, the fixed-rank algorithm is constructive and accompanied by publicly available MATLAB code, and the FPT claim for generic matrices is carefully conditioned on continuous latent factors (Lemmas 3.5–3.7). The reductions use only polynomially many bits and bounded integer alphabets, so they establish strong hardness. These contributions close a gap left open by the extensive literature on linear low-rank models and give a clear baseline for future algorithmic work on nonlinear matrix decompositions.

minor comments (5)
  1. Section 3.2.4, Tables 2–3: the reported runtimes are useful, but a short remark on the precise arithmetic model (floating-point vs. exact rational) would help readers interpret the numbers for larger r.
  2. Page 8, display (2): the matrix M_φ is written with a 5 in position (3,1); a parenthetical note that any constant larger than 3 would work equally well would make the construction slightly more transparent.
  3. Theorem 3.8 and Remark 1: the phrase “fixed-parameter linear” is correct, yet a one-line reminder that the hidden constant still contains 2^{O(r^3)} would prevent over-optimistic reading of the asymptotic.
  4. Appendix A, Lemma A.1: the hypothesis ε^{1/p}<1/2 is used without comment; a brief sentence that this is ensured by the choice of N in the main reduction would close the loop.
  5. Throughout: the acronyms ExactEPMF / FroEPMF / LRMS are introduced cleanly, but a single table collecting all decision-problem definitions (as done for the complexity summary in Table 1) would improve navigability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: hardness by explicit many-one reductions from external NP-complete problems; tractability by self-contained constructive enumeration.

full rationale

The paper is a pure computational-complexity analysis. Exact EPMF is definitionally equivalent to LRMS after entrywise p-th roots (magnitudes fixed, only signs free); this is an equivalence of decision problems, not a circular derivation of a prediction. Strong NP-hardness (Thm 2.2 / Cor 2.3) is proved by a fully written polynomial-time many-one reduction from the external, strongly NP-complete Monotone NAE-3SAT problem, constructing an explicit matrix M_φ with entries in {0,1,2,5}. Fixed-rank tractability (Thm 3.2) is an explicit branching algorithm (Alg 1) that enumerates nonsingular k imes k signed blocks, filters via the finite-dimensional space of symmetric matrices, and reconstructs a skeleton factorization; the argument never appeals to an unproved prior claim of the authors. The FPT specialization for generic inputs (Thm 3.8) rests only on measure-zero statements for continuous distributions (Lems 3.5–3.7), which are proved inside the paper. FroEPMF hardness for r=2 (Thm 4.1) is likewise a self-contained reduction from the external Cut-Norm problem, with an explicit block matrix X and polynomial-size N. Background self-citations concern algorithmic heuristics for related NMD models and are not load-bearing for any complexity theorem. No fitted parameters, no uniqueness theorems imported from the authors, and no ansatz smuggled via citation appear in the derivation chain.

Assumptions & free parameters 1 free parameters · 6 assumptions · 2 invented entities

The paper is a complexity-theory contribution. It relies on standard linear algebra (rank, skeleton/CUR decomposition, dimension of symmetric matrices) and standard NP-complete problems (Partition, Monotone NAE-3SAT, Cut-Norm). Genericity is modeled by continuous factor distributions. The only engineered quantities are the large block size N and the concrete entry set {0,1,2,5} in the hardness gadgets; both are polynomial and explicit. No physical constants or data-fitted scales.

free parameters (1)
  • N (block size in FroEPMF reduction) = polynomial function of s,t,p
    Chosen as ceil of max{(24p)^2 (st)^3, (24p)^p (st)^{p+1/2}} so that error terms η stay below 1/(12 p st); polynomial in the cut-norm instance size, not fitted to data.
assumptions (6)
  • standard math Skeleton decomposition: rank-k matrix Y admits Y = Y(:,J) Y(I,J)^{-1} Y(I,:) for some full-rank k×k submatrix (Lemma 3.1).
    Classical linear algebra fact used to structure Algorithm 1.
  • standard math Space of k×k symmetric matrices has dimension binom(k+1,2).
    Used to bound the number of row candidates that must be enumerated in Step 3.
  • domain assumption Monotone NAE-3SAT is strongly NP-complete.
    Source problem for the strong NP-hardness reduction (Section 2.2); cited as known.
  • domain assumption Cut-Norm decision for ±1 matrices is strongly NP-hard.
    Source problem for rank-2 FroEPMF hardness (Section 4); cited from Gillis–Vavasis.
  • domain assumption Generic rank-r* matrices are products W# H# with continuous i.i.d. entries, so signed k×k minors and outer-product spans are full rank w.p.1.
    Load-bearing for the FPT claim (Lemmas 3.5–3.7, Thm 3.8).
  • ad hoc to paper Exact p-th root oracle available when mapping ExactEPMF to LRMS over rationals (BSS model).
    Footnote in Section 3.3; needed only for the ExactEPMF corollary, not for LRMS itself.
invented entities (2)
  • Low-Rank Matrix Signing (LRMS) independent evidence
    purpose: Combinatorial reformulation of exact EPMF after taking entrywise p-th roots; decision problem of existence of a signing of rank ≤ r.
    Named and formalized here as the intermediate problem; closely related to signless rank but treated as a decision problem with fixed target rank.
  • Entrywise Power Matrix Factorization (EPMF) independent evidence
    purpose: Unifies modulus (p=1) and componentwise square (p=2) models under one complexity analysis.
    Natural generalization already present in related NMD literature; paper supplies the complexity map rather than inventing the model from scratch.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization." pith.science (2026). https://pith.science/paper/PJG7I5Z3

@misc{pith2026260704875,
  author       = {Pith},
  title        = {Pith review of: On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PJG7I5Z3}},
  note         = {Machine review of arXiv:2607.04875}
}
abstract

Given a nonnegative matrix $X$, a factorization rank $r$ and {a positive integer $p$}, entrywise power matrix factorization (EPMF) looks for a low-rank matrix $X_r$ such that $X = |X_r|^{\circ p}$ (exact case) or $X \approx |X_r|^{\circ p}$ (approximate case), where $(\cdot)^{\circ p}$ denotes the componentwise exponent. EPMF includes the modulus model ($p=1$) and componentwise square factorization ($p=2$) as special cases, the latter being closely related to the square root rank. We analyze the computational complexity of the exact decision problem and the Frobenius-norm approximation problem, and establish a complete complexity landscape. In the exact case, we show that EPMF is equivalent to the combinatorial problem of flipping the signs of the entries of a given matrix $X$ to obtain a rank-$r$ matrix, which we refer to as the low-rank matrix signing (LRMS) problem. We first show that LRMS, and hence exact EPMF, is strongly NP-hard, improving a weak NP-hardness result for the square-root-rank (Math. Prog., 2015). We then show that LRMS can be solved in polynomial time when $r$ is fixed. Moreover, when the rank $r$ is part of the input, we show that for generic matrices the algorithm is fixed-parameter tractable (FPT) in the parameter $r$; in fact, the running time is fixed-parameter linear in the number of entries of the input matrix. In the approximate case using the Frobenius norm as an error measure, we show that EPMF is NP-hard, already when $r=2$, the smallest nontrivial case.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 5 linked inside Pith

  1. [1]

    In: ACM Symposium on Theory of computing, pp

    Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization–provably. In: ACM Symposium on Theory of computing, pp. 145–162 (2012)

    2012

  2. [2]

    arXiv preprint arXiv:2512.17473 (2025)

    Awari, A., Gillis, N., Vandaele, A.: Alternating direction method of multipliers for nonlinear matrix decompositions. arXiv preprint arXiv:2512.17473 (2025)

    arXiv 2025

  3. [3]

    In: European Signal Processing Conference (EUSIPCO), pp

    Awari, A., Nguyen, H., Wertz, S., Vandaele, A., Gillis, N.: Coordinate descent algorithm for nonlinear matrix decomposition with the relu function. In: European Signal Processing Conference (EUSIPCO), pp. 2622–2626 (2024)

    2024

  4. [4]

    arXiv preprint arXiv:1503.04486 (2015)

    Bhangale, A., Kopparty, S.: The complexity of computing the minimum rank of a sign pattern matrix. arXiv preprint arXiv:1503.04486 (2015)

    arXiv 2015

  5. [5]

    Springer, New York, NY (1997)

    Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and real computation, 1998 edn. Springer, New York, NY (1997)

    1998

  6. [6]

    In: Annual Symposium on Foundations of Computer Science, pp

    Blum, L., Shub, M., Smale, S.: On a theory of computation over the real numbers; NP completeness, re- cursive functions and universal machines. In: Annual Symposium on Foundations of Computer Science, pp. 387–397 (1988)

    1988

  7. [7]

    Camion, P., Hoffman, A.: On the nonsingularity of complex matrices. Pac. J. Math.17(2), 211–214 (1966) 25

    1966

  8. [8]

    In: 2010 IEEE sensor array and multichannel signal processing workshop, pp

    Cand` es, E., Li, X., Ma, Y., Wright, J.: Robust principal component analysis?: Recovering low-rank matrices from sparse errors. In: 2010 IEEE sensor array and multichannel signal processing workshop, pp. 201–204. IEEE (2010)

    2010

Show all 46 references
  1. [9]

    IEEE Trans- actions on Information Theory56(5), 2053–2080 (2010)

    Cand` es, E.J., Tao, T.: The power of convex relaxation: Near-optimal matrix completion. IEEE Trans- actions on Information Theory56(5), 2053–2080 (2010)

  2. [10]

    SIAM Journal on Optimization21(2), 572–596 (2011)

    Chandrasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization21(2), 572–596 (2011)

    2011

  3. [11]

    IEEE Transactions on Signal Processing67(20), 5239–5269 (2019)

    Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing67(20), 5239–5269 (2019)

    2019

  4. [12]

    Theoretical Computer Science 815, 147–152 (2020)

    Darmann, A., D¨ ocker, J.: On a simple hard variant of not-all-equal 3-sat. Theoretical Computer Science 815, 147–152 (2020)

    2020

  5. [13]

    Psychometrika1(3), 211–218 (1936)

    Eckart, C., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika1(3), 211–218 (1936)

    1936

  6. [14]

    Math- ematical Programming153(1), 133–177 (2015)

    Fawzi, H., Gouveia, J., Parrilo, P.A., Robinson, R.Z., Thomas, R.R.: Positive semidefinite rank. Math- ematical Programming153(1), 133–177 (2015)

    2015

  7. [15]

    Springer Berlin Heidelberg (1996)

    Federer, H.: Geometric Measure Theory. Springer Berlin Heidelberg (1996)

    1996

  8. [16]

    Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts

    Folland, G.: Real Analysis: Modern Techniques and Their Applications. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. Wiley (2013)

    2013

  9. [17]

    Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 29. wh freeman New York (2002)

    2002

  10. [18]

    In: International Conference on Machine Learning, pp

    Ge, R., Jin, C., Zheng, Y.: No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In: International Conference on Machine Learning, pp. 1233–1242 (2017)

    2017

  11. [19]

    Advances in neural information processing systems29(2016)

    Ge, R., Lee, J.D., Ma, T.: Matrix completion has no spurious local minimum. Advances in neural information processing systems29(2016)

    2016

  12. [20]

    SIAM Journal on Matrix Analysis and Applications32(4), 1149–1165 (2011)

    Gillis, N., Glineur, F.: Low-rank matrix approximation with weights or missing data is NP-hard. SIAM Journal on Matrix Analysis and Applications32(4), 1149–1165 (2011)

    2011

  13. [21]

    Gillis, N., Porcelli, M., Seraghiti, G.: An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function. SIAM J. on Mathematics of Data Science (2026). ArXiv:2503.23832

    2026

  14. [22]

    arXiv preprint arXiv:2605.28980 (2026)

    Gillis, N., Saha, S., Sicilia, S., Vandaele, A.: Manifold-based algorithms for the Hadamard decomposi- tion. arXiv preprint arXiv:2605.28980 (2026)

    2026 arXiv

  15. [23]

    Linear Algebra and its Applications581, 367–382 (2019)

    Gillis, N., Shitov, Y.: Low-rank matrix approximation in the infinity norm. Linear Algebra and its Applications581, 367–382 (2019)

    2019

  16. [24]

    Mathematics of Operations Research43(4), 1072–1084 (2018)

    Gillis, N., Vavasis, S.A.: On the complexity of robust PCA andℓ 1-norm low-rank matrix approximation. Mathematics of Operations Research43(4), 1072–1084 (2018)

    2018

  17. [25]

    Johns Hopkins University Press, Baltimore (2013)

    Golub, G.H., Van Loan, C.F.: Matrix computations. Johns Hopkins University Press, Baltimore (2013)

    2013

  18. [26]

    Linear algebra and its applications261(1-3), 1–21 (1997)

    Goreinov, S.A., Tyrtyshnikov, E.E., Zamarashkin, N.L.: A theory of pseudoskeleton approximations. Linear algebra and its applications261(1-3), 1–21 (1997)

    1997

  19. [27]

    SIAM Journal on Applied Algebra and Geometry5(3), 526–551 (2021)

    Goucha, A.P., Gouveia, J.: The phaseless rank of a matrix. SIAM Journal on Applied Algebra and Geometry5(3), 526–551 (2021)

    2021

  20. [28]

    Mathe- matical Programming153, 201–221 (2013)

    Gouveia, J., Robinson, R., Thomas, R.R.: Polytopes of minimum positive semidefinite rank. Mathe- matical Programming153, 201–221 (2013)

    2013

  21. [29]

    In: International Conference on Learning Representations (2025) 26

    Huang, Q., Ko, T., Zhuang, Z., Tang, L., Zhang, Y.: Hira: Parameter-efficient Hadamard high-rank adaptation for large language models. In: International Conference on Learning Representations (2025) 26

    2025

  22. [30]

    ICLR (2022)

    Hyeon-Woo, N., Ye-Bin, M., Oh, T.: Fedpara: Low-rank Hadamard product parameterization for efficient federated learning. ICLR (2022)

    2022

  23. [31]

    Linear and Multilinear Algebra65(11), 2212–2244 (2017)

    Kishore Kumar, N., Schneider, J.: Literature survey on low rank approximation of matrices. Linear and Multilinear Algebra65(11), 2212–2244 (2017)

    2017

  24. [32]

    arXiv preprint arXiv:1907.13602 (2019)

    Kueng, R., Tropp, J.A.: Binary component decomposition part II: The asymmetric case. arXiv preprint arXiv:1907.13602 (2019)

    1907 arXiv

  25. [33]

    SIAM Journal on Mathematics of Data Science3(2), 544–572 (2021)

    Kueng, R., Tropp, J.A.: Binary component decomposition part I: the positive-semidefinite case. SIAM Journal on Mathematics of Data Science3(2), 544–572 (2021)

    2021

  26. [34]

    SIAM Journal on Matrix Analysis and Applications44(2), 503–529 (2023)

    Le, Q.T., Riccietti, E., Gribonval, R.: Spurious valleys, NP-hardness, and tractability of sparse matrix factorization with fixed support. SIAM Journal on Matrix Analysis and Applications44(2), 503–529 (2023)

    2023

  27. [35]

    arXiv preprint arXiv:1411.6712 (2014)

    Lee, T., Wei, Z.: The square root rank of the correlation polytope is exponential. arXiv preprint arXiv:1411.6712 (2014)

    2014 arXiv

  28. [36]

    In: International Work- shop on Machine Learning for Signal Processing (MLSP) (2024)

    Lefebvre, J., Vandaele, A., Gillis, N.: Component-wise squared factorization. In: International Work- shop on Machine Learning for Signal Processing (MLSP) (2024)

    2024

  29. [37]

    In: International Conference on Learning Represen- tations, pp

    Loconte, L., Sladek, A., Mengel, S., Trapp, M., Solin, A., Gillis, N., Vergari, A.: Subtractive mixture models via squaring: Representation and learning. In: International Conference on Learning Represen- tations, pp. 15,751–15,785 (2024)

    2024

  30. [38]

    In: International Workshop on Machine Learning for Signal Processing (MLSP) (2025)

    Nguyen, H., Awari, A., Vandaele, A., Gillis, N.: Nonlinear matrix decomposition with the sigmoid function. In: International Workshop on Machine Learning for Signal Processing (MLSP) (2025)

    2025

  31. [39]

    SIAM review52(3), 471–501 (2010)

    Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review52(3), 471–501 (2010)

    2010

  32. [40]

    SIAM Journal on Mathematics of Data Science4(2), 431–463 (2022)

    Saul, L.K.: A nonlinear matrix decomposition for mining the zeros of sparse data. SIAM Journal on Mathematics of Data Science4(2), 431–463 (2022)

    2022

  33. [41]

    In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), pp

    Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), pp. 216–226. ACM, New York (1978)

    1978

  34. [42]

    SIAM Journal on Optimization28(3), 2067–2072 (2018)

    Shitov, Y.: Matrices of bounded PSD rank are easy to detect. SIAM Journal on Optimization28(3), 2067–2072 (2018)

  35. [43]

    SIAM, Philadelphia (2022)

    Trefethen, L.N., Bau, D.: Numerical linear algebra. SIAM, Philadelphia (2022)

    2022

  36. [44]

    Foundations and Trends®in Machine Learning9(1), 1–118 (2016)

    Udell, M., Horn, C., Zadeh, R., Boyd, S.: Generalized low rank models. Foundations and Trends®in Machine Learning9(1), 1–118 (2016)

    2016

  37. [45]

    SIAM Journal on Optimization 20(3), 1364–1377 (2010)

    Vavasis, S.A.: On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization 20(3), 1364–1377 (2010)

    2010

  38. [46]

    Wang, Q., Qu, Y., Cui, C., Han, D.: An accelerated alternating partial Bregman algorithm for ReLU- based matrix decomposition. Journal of Scientific Computing105(2), 48 (2025) 27 A Lemmas for the bounds on the coefficients around1/2 Lemma A.1(Bounds on the coefficients around ...

    2025

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.