研究低秩矩阵符号翻转与幂次分解的计算复杂性，揭示其在不同条件下的可解性边界。
On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization
- 将矩阵幂次分解转化为符号翻转问题，构建低秩矩阵签名新模型。
- 证明精确情形下问题为强NP难，但固定秩时可在多项式时间内求解。
- 近似情形下即使秩为2也属NP难，但高秩通用矩阵具参数可解性优势。
给定非负矩阵 $X$、因子秩 $r$ 及正整数 $p$，分量幂次矩阵分解（EPMF）旨在寻找低秩矩阵 $X_r$，使得 $X = |X_r|^{ ext{∘}p}$（精确情形）或 $X riangleq |X_r|^{ ext{∘}p}$（近似情形），其中 $( ext{⋅})^{ ext{∘}p}$ 表示逐元素幂运算。EPMF包含模值模型（$p=1$）和分量平方分解（$p=2$）作为特例，后者与平方根秩密切相关。本文分析精确判定问题与弗罗比尼乌斯范数近似问题的计算复杂性，建立完整复杂性图景。在精确情形下，证明 EPMF 等价于对给定矩阵 $X$ 的元素符号进行翻转以获得秩 $r$ 矩阵的组合问题，即低秩矩阵签名（LRMS）问题。首先证明 LRMS 及其等价的精确 EPMF 为强 NP 难，改进了此前关于平方根秩的弱 NP 难结果（Math. Prog., 2015）。接着证明当 $r$ 固定时，LRMS 可在多项式时间内求解。此外，当 $r$ 作为输入的一部分时，对一般矩阵，算法在参数 $r$ 下是固定参数可追踪（FPT）的，实际运行时间在输入矩阵元素数量上呈线性。在使用弗罗比尼乌斯范数的近似情形中，我们证明即使 $r=2$（最小非平凡情况），EPMF 也是 NP 难的。
原文摘要 · Abstract (English)
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 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。