Fugu-MT 論文翻訳(概要): On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization

論文の概要: 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（参考訳）: 低ランク行列符号の複雑さと入出力行列因子化について
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$ のとき、最小の非自明なケースである。

関連論文リスト

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions [23.539428616884035]
非対称ガウス・ケルネル行列に対する行列ベクトル積の高速アルゴリズムについて研究する。我々のアルゴリズムは、$K$に関する以下のモデリング仮定に依存している: 最悪のケースの成長とは対照的に、$K$のエントリの合計は$n$で線形にスケールする。我々は、この仮定の下で動作し、制約のない計算を行う最初の準四進時間アルゴリズムを得る。
論文参考訳（メタデータ） (2025-07-31T13:29:43Z)
Query Efficient Structured Matrix Learning [32.0553563150929]
我々は任意の有限サイズの行列族、$mathcalF$から、ほぼ最適の$A$の近似を求める。驚くべきことに、マットベックモデルでは、複雑さの2次的な改善を$tildeO(sqrtlog|mathcalF|)$にすることができる。例えば、次元$q$の任意の楕円行列族から準最適近似が $tildeO(sqrt) で学習できることを確かめる。
論文参考訳（メタデータ） (2025-07-25T14:04:20Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文参考訳（メタデータ） (2024-08-27T18:28:31Z)
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)
Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文参考訳（メタデータ） (2021-09-06T14:21:43Z)
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)
Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
論文参考訳（メタデータ） (2020-09-08T05:39:19Z)

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

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