論文の概要: Easy, robust approximate message passing for planted spike models

• arxiv url: http://arxiv.org/abs/2606.00500v1
• Date: Sat, 30 May 2026 03:18:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:28.493157
• Title: Easy, robust approximate message passing for planted spike models
• Title（参考訳）: 植付スパイクモデルのための簡易でロバストな近似メッセージパッシング
• Abstract要約: 本稿では,スパイク行列設定において,ロバストな近似メッセージパッシング(AMP)のための単純かつ効率的なアルゴリズムを提案する。 我々のアルゴリズムは、スペクトル前処理ステップと頑健なスペクトル手順を組み合わせることで構成されており、これらの入力を考慮すれば、AMPが頑健であること(おそらく意外なことに)が証明できる。
• 参考スコア（独自算出の注目度）: 1.0269997499911663
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let $\varepsilon$ be a sufficiently small constant, and suppose that $X \in \mathbb R^{n \times n}$ is a Gaussian matrix with a planted rank-$1$ spike, and $E \in \mathbb R^{n \times n}$ is an adversarially chosen matrix supported on an $\varepsilon n \times \varepsilon n$ principal minor. Let $v_{\mathrm{AMP}}(X)$ be the output of an AMP iteration on the uncorrupted matrix $X$. We give a procedure that, given access only to the corrupted matrix $Y = X + E$, computes a vector $v_{\mathrm{ALG}}(Y)$ which is $\tilde{O}(\sqrt{\varepsilon})$-close to $v_{\mathrm{AMP}}(X)$, for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and $\mathbb Z_2$ synchronization. Our algorithm consists of a spectral pre-processing step combined with a robust spectral initialization procedure; given these inputs, we prove that (perhaps surprisingly) AMP is robust out-of-the-box.
• Abstract（参考訳）: 本稿では,スパイク行列設定において,ロバストな近似メッセージパッシング(AMP)のための単純かつ効率的なアルゴリズムを提案する。 特に、$\varepsilon$ を十分小さな定数とし、$X \in \mathbb R^{n \times n}$ が植込み階数 1$ スパイクを持つガウス行列であり、$E \in \mathbb R^{n \times n}$ が $\varepsilon n \times \varepsilon n$プリンシパルマイナーであるとする。 v_{\mathrm{AMP}}(X)$ を未破裂行列 $X$ 上の AMP 反復の出力とする。 破損した行列 $Y = X + E$ にのみアクセスすると、ベクトル $v_{\mathrm{ALG}}(Y)$ が $\tilde{O}(\sqrt{\varepsilon})$-close to $v_{\mathrm{AMP}}(X)$ となる。 我々のアルゴリズムは、スペクトル前処理ステップと頑健なスペクトル初期化手順を組み合わせたもので、これらの入力を考えると、AMPが(意外なことに)頑健であることを証明する。

関連論文リスト

• Sparse Linear Regression is Easy on Random Supports [20.128442161507582]
  我々は mathbbRN times d$ で設計行列 $X を入力し、 mathbbRN times d$ で測定やラベル $y を入力します。 w*$がランダムに選択されると、およそ$N = O(klog d/epsilon)$サンプルで予測エラー$epsilon$が得られる。
  論文  参考訳（メタデータ） (2025-11-09T03:48:21Z)
• Fast, robust approximate message passing [2.668787455520979]
  本稿では,AMPアルゴリズムを頑健に実装するための高速なスペクトル計算法を提案する。 提案アルゴリズムはスペクトル前処理のステップを実行し,$mathcal A$の摂動を緩やかに修正する。
  論文  参考訳（メタデータ） (2024-11-05T03:20:14Z)
• 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)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。 Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T16:36:48Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
  任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。 我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
  論文  参考訳（メタデータ） (2023-04-06T16:15:19Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• 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)

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

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