論文の概要: On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization

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

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

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