論文の概要: The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model

• arxiv url: http://arxiv.org/abs/2511.06040v2
• Date: Fri, 14 Nov 2025 01:35:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 13:23:30.431989
• Title: The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model
• Title（参考訳）: 対称性関連スパイクウィグナーモデルにおけるアルゴリズム的相転移
• Authors: Zhangsong Li,
• Abstract要約: 本研究では,一対のスパイクされたウィグナー行列における相関信号の検出と推定の計算タスクについて検討する。 アルゴリズムはスパイク間の相関を利用して、$X$から$x$を効率よく回収するか、$Y$から$y$を効率よく回収するかのどちらかが計算不可能な状態であっても信号を検出して推定することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational task of detecting and estimating correlated signals in a pair of spiked Wigner matrices. Our model consists of observations $$ X = \tfracλ{\sqrt{n}} xx^{\top} + W \,, \quad Y = \tfracμ{\sqrt{n}} yy^{\top} + Z \,. $$ where $x,y \in \mathbb R^n$ are signal vectors with norm $\|x\|,\|y\| \approx\sqrt{n}$ and correlation $\langle x,y \rangle \approx ρ\|x\|\|y\|$, while $W,Z$ are independent Gaussian Wigner matrices. We propose an efficient algorithm that succeeds whenever $F(λ,μ,ρ)>1$, where $$ F(λ,μ,ρ)=\max\Big\{ λ,μ, \frac{ λ^2 ρ^2 }{ 1-λ^2+λ^2 ρ^2 } + \frac{ μ^2 ρ^2 }{ 1-μ^2+μ^2 ρ^2 } \Big\} \,. $$ Our result shows that an algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either $x$ from $X$ alone or $y$ from $Y$ alone is believed to be computationally infeasible. We complement our algorithmic result with evidence for a matching computational lower bound. In particular, we prove that when $F(λ,μ,ρ)<1$, all algorithms based on {\em low-degree polynomials} fails to distinguish $(X,Y)$ with two independent Wigner matrices. This low-degree analysis strongly suggests that $F(λ,μ,ρ)=1$ is the precise computation threshold for this problem.
• Abstract（参考訳）: 本研究では,一対のスパイクされたウィグナー行列における相関信号の検出と推定の計算タスクについて検討する。 X = \tfracλ{\sqrt{n}} xx^{\top} + W \, \quad Y = \tfracμ{\sqrt{n}} yy^{\top} + Z \。 $x,y \in \mathbb R^n$ はノルム $\|x\|,\|y\| \approx\sqrt{n}$ と相関 $\langle x,y \rangle \approx ρ\|x\|\|y\|$ の信号ベクトルであり、$W,Z$ は独立ガウスウィグナー行列である。 F(λ,μ,ρ)>1$,$$$$F(λ,μ,ρ)=\max\Big{ λ,μ, \frac{ λ^2 }{ 1-λ^2+λ^2 ρ^2 } + \frac{ μ^2 }{ 1-μ^2+μ^2 ρ^2 } \Big\} \, 我々の結果は、スパイク間の相関を利用して、効率的に$X$から$x$を回収するか、$Y$から$y$を効率よく回収するかのどちらかが計算不可能な状態であっても、信号を検出して推定することができることを示している。 アルゴリズムの結果を、一致した計算下界の証拠で補完する。 特に、$F(λ,μ,ρ)<1$のとき、すべてのアルゴリズムが2つの独立なウィグナー行列で$(X,Y)$を区別できないことを証明している。 この低次解析は、$F(λ,μ,ρ)=1$がこの問題の正確な計算しきい値であることを強く示唆している。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs [0.0]
  2つの問題に対して計算硬度を示す。 我々の証明の主な要素の1つは、2つの確率測度の間の近位関係を導出することである。 このフレームワークは、異なるタスク間のリダクションを実行するための便利なツールを提供する。
  論文  参考訳（メタデータ） (2025-02-14T00:24:51Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
  2つの相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon)$ からサブサンプリングする。 このモデルを一対の独立した ErdHos'enyi グラフと区別する検出問題に対して、隣接点のエントリのエンブロー度に基づくテストに焦点をあてる。
  論文  参考訳（メタデータ） (2024-09-02T06:14:05Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• 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)
• The Complexity of Sparse Tensor PCA [1.90365714903665]
  1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。 PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
  論文  参考訳（メタデータ） (2021-06-11T10:57:00Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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