論文の概要: New Hardness Results for Low-Rank Matrix Completion
- arxiv url: http://arxiv.org/abs/2506.18440v1
- Date: Mon, 23 Jun 2025 09:22:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-24 19:06:36.922208
- Title: New Hardness Results for Low-Rank Matrix Completion
- Title（参考訳）: 低ランクマトリックス補修における新しい硬さ評価法
- Authors: Dror Chawin, Ishay Haviv,
- Abstract要約: 本稿では,低ランク行列補完問題に対する新しい$mathsfNP $-hardness結果を提案する。
十分大きな整数 $d$ と [ 2-O(d),frac17]$ の任意の実数 $varepsilon に対して、最大で 1 ドルの値が露出する部分行列 $A$ が与えられたとき、ランク $d$ の正の半有限完備化を許容するとすると、正の半定行列を見つけることは $mathsfNP$-hard である。
私たちの証明にはaが含まれる
- 参考スコア（独自算出の注目度）: 2.7624021966289605
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new $\mathsf{NP} $-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer $d$ and any real number $\varepsilon \in [ 2^{-O(d)},\frac{1}{7}]$, given a partial matrix $A$ with exposed values of magnitude at most $1$ that admits a positive semi-definite completion of rank $d$, it is $\mathsf{NP}$-hard to find a positive semi-definite matrix that agrees with each given value of $A$ up to an additive error of at most $\varepsilon$, even when the rank is allowed to exceed $d$ by a multiplicative factor of $O (\frac{1}{\varepsilon ^2 \cdot \log(1/\varepsilon)} )$. This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than $2$ and to $\varepsilon $ that decays polynomially in $d$. We establish similar $\mathsf{NP}$-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.
- Abstract（参考訳）: 低ランク行列完備問題では、与えられた値の無い実行列が、結果として得られる行列が低ランクであるか、低ランク行列に近いかを問う。
完備行列は、正の半無限性や有界無限ノルムのような追加の構造的制約を満たすためにしばしば必要とされる。
この問題は、機械学習、統計学、理論計算機科学など様々な研究分野に現れ、幅広い現実世界の応用がある。
本稿では,低ランク行列補完問題に対する新しい$\mathsf{NP} $-hardness結果を提案する。
すべての十分大きな整数 $d$ と任意の実数 $\varepsilon \in [ 2^{-O(d)},\frac{1}{7}]$ に対し、ある部分行列 $A$ が最大 1$ で露出すると、ランク $d$ の正の半定完備化を許容するとすると、$\mathsf{NP}$-hard が$A$ の任意の値に一致する正の半定行列を最大 $\varepsilon$ の加法誤差まで見つけることを示し、そのランクが$O (\frac{1}{\varepsilon ^2 \cdot \log(1/\varepsilon$) の乗法係数によって$d$を超えることが許される。
これはハルト、メカ、ラガヴェンドラ、ワイツ(COLT, 2014)の結果を強化し、$d$で多項式的に崩壊する2ドル以下の乗法的因子と$\varepsilon $に適用される。
同様の$\mathsf{NP}$-hardnessの結果は、完備行列が(正の半定値ではなく)有界無限ノルムを持つように制約されている場合に成立する。
我々の証明には、グラフのほぼ正則表現という新しい概念、線図の概念、摂動ID行列の階数上の有界性が含まれる。
関連論文リスト
- 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) - Quantum and classical query complexities of functions of matrices [0.0]
任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
論文 参考訳（メタデータ） (2023-11-13T00:45:41Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。
我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
論文 参考訳（メタデータ） (2023-04-25T12:42:59Z) - A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。
本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
論文 参考訳（メタデータ） (2023-03-22T04:07:26Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - 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) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳（メタデータ） (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。