On the Complexity of Entrywise Power Matrix Factorization

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.