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

arXiv: https://arxiv.org/abs/2607.04875 · HTML: https://mlsanity.com/paper/2607.04875/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 47 references that are in the map.
- First posted on arXiv 6 Jul 2026.

## Builds on (most cited first, 16 of 16)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Positive semidefinite rank](https://mlsanity.com/paper/1407.4095/) (2014)
- [On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation](https://mlsanity.com/paper/1509.09236/) (2015)
- [Low-Rank Matrix Approximation in the Infinity Norm](https://mlsanity.com/paper/1706.00078/) (2017)
- [Binary Component Decomposition Part I: The Positive-Semidefinite Case](https://mlsanity.com/paper/1907.13603/) (2019)
- [The square root rank of the correlation polytope is exponential](https://mlsanity.com/paper/1411.6712/) (2014)
- [An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition](https://mlsanity.com/paper/2503.02386/) (2025)
- [An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function](https://mlsanity.com/paper/2503.23832/) (2025)
- [Binary component decomposition Part II: The asymmetric case](https://mlsanity.com/paper/1907.13602/) (2019)
- [Alternating Direction Method of Multipliers for Nonlinear Matrix Decompositions](https://mlsanity.com/paper/2512.17473/) (2025)
- [Manifold-based Algorithms for the Hadamard Decomposition](https://mlsanity.com/paper/2605.28980/) (2026)
- [The phaseless rank of a matrix](https://mlsanity.com/paper/1909.02417/) (2019)

## Abstract (arXiv)

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 Xr such that X = |Xr|circ p (exact case) or X ≈ |Xr|circ p (approximate case), where (·)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.