論文の概要: On the Complexity of Entrywise Power Matrix Factorization

• arxiv url: http://arxiv.org/abs/2607.04875v1
• Date: Mon, 06 Jul 2026 09:50:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:30.106539
• Title: On the Complexity of Entrywise Power Matrix Factorization
• Title（参考訳）: エントリエント・パワーマトリックス因子化の複雑さについて
• Authors: Nicolas Gillis, Subhayan Saha, Stefano Sicilia, Arnaud Vandaele,
• Abstract要約: 入出力行列分解(EPMF)は、$X = |X_r|circ p$ (exact case) あるいは $X approx |X_r|circ p$ (approximate case) となるような低ランク行列 $X_r$ を求める。 次に、$r$が修正された場合、署名問題はリアルタイムで解決できることを示す。 誤り測度としてフロベニウスノルムを用いる近似ケースでは、EPMF が NP-hard であることが示され、既に$r=2$ のとき、最小の非自明なケースである。
• 参考スコア（独自算出の注目度）: 9.842769671181276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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|^{\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.
• Abstract（参考訳）: 非負行列 $X$, a factorization rank $r$, a real parameter $p$, entrywise power matrix factorization (EPMF) が与えられたとき、$X = |X_r|^{\circ p}$ (exact case) あるいは $X \approx |X_r|^{\circ p}$ (approximate case) となるような低ランク行列 $X_r$ を求める。 EPMF は、特別の場合としてモジュラーモデル (p=1$) と成分単位の平方分解 (p=2$) を含み、後者は平方根のランクと密接に関連している。 決定問題とフロベニウス-ノルム近似問題の計算複雑性を解析し、完全な複雑性の展望を確立する。 正確な場合、 EPMF は与えられた行列の成分の符号を$X$で反転させてランク-$r$行列を得る組合せ問題と等価であることを示す。 まず、署名問題、すなわち正確な EPMF が強いNPハードであることを示し、Fawzi et al (Math. Prog., 2015) の平方根ランクに対する弱いNPハード化結果を改善する。 すると、$r$が固定されたとき、符号問題は多項式時間で解くことができることを示す。 さらに、階数$r$が入力の一部である場合、アルゴリズムはパラメータ$r$の固定パラメータ(FPT)であり、実際に、実行時間は入力サイズ$X$で線形であることを示す。 フロベニウスノルムを誤差測度として用いた近似ケースでは、EPMF が NP-ハードであることを示し、既に$r=2$ のとき、最小の非自明なケースである。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• On the computational and statistical complexity of over-parameterized matrix sensing [30.785670369640872]
  FGD法(Factorized Gradient Descend)を用いた低ランク行列検出の解法を検討する。 分解行列 $mathbff$ を分離列空間に分解することにより、$|mathbff_t - mathbff_t - mathbfx*|_f2$ が統計誤差に収束することを示す。
  論文  参考訳（メタデータ） (2021-01-27T04:23:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。