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

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.