研究人员分析了逐项幂次矩阵分解（EPMF）的计算复杂度，该问题包含模数模型和分量平方分解作为特例。他们为精确和近似EPMF建立了完整的复杂度图谱。对于精确情况，他们证明了它等价于符号问题，该问题是强NP难的，但对于固定秩可以在多项式时间内解决。在近似情况下，即使秩为二，EPMF也被证明是NP难的。 AI
影响 这项研究为矩阵分解技术提供了理论见解，可能为机器学习中的未来算法开发提供信息。
排序理由 该集群包含一篇详细介绍数学问题计算复杂度分析的研究论文。[lever_c_demoted from research: ic=1 ai=0.7]
AI 生成摘要 · Google Gemini · 来自 2 个来源。 我们如何撰写摘要 →
arXiv:2607.04875v1 Announce Type: cross 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|^{\ci…
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…