{"id":"arxiv/2607.04875","url":"https://arxiv.org/abs/2607.04875","tags":["cs.CC","cs.IR","math.CO","stat.ML"],"score":0,"title":"On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization","domain":"cs.CC","source":"arxiv","authors":["Nicolas Gillis","Subhayan Saha","Stefano Sicilia","Arnaud Vandaele"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-06","reactions":{}}