{"ID":5937167,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T09:46:01.859313918Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04875","arxiv_id":"2607.04875","title":"On the Complexity of Entrywise Power Matrix Factorization","abstract":"Given a nonnegative matrix $X$, a factorization rank $r$ and a real parameter $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 component-wise exponent. EPMF includes the modulus model ($p=1$) and component-wise 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 signing problem. We first show that the signing problem, and hence exact EPMF, is strongly NP-hard, improving a weak NP-hardness result for the square-root-rank of Fawzi et al. (Math. Prog., 2015). We then show that the signing problem 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 linear in the input size $X$. 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.","short_abstract":"Given a nonnegative matrix $X$, a factorization rank $r$ and a real parameter $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 component-wise exponent....","url_abs":"https://arxiv.org/abs/2607.04875","url_pdf":"https://arxiv.org/pdf/2607.04875v1","authors":"[\"Nicolas Gillis\",\"Subhayan Saha\",\"Stefano Sicilia\",\"Arnaud Vandaele\"]","published":"2026-07-06T09:50:20Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.IR\",\"math.CO\",\"stat.ML\"]","methods":"[]","has_code":false}