論文の概要: Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
- arxiv url: http://arxiv.org/abs/2302.06665v1
- Date: Mon, 13 Feb 2023 19:57:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-15 17:25:45.600501
- Title: Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
- Title（参考訳）: 不均質スパイクウィグナーモデルに対する最適アルゴリズム
- Authors: Aleksandr Pak, Justin Ko, Florent Krzakala
- Abstract要約: 不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
- 参考スコア（独自算出の注目度）: 89.1371983413931
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a spiked Wigner problem with an inhomogeneous noise
profile. Our aim in this problem is to recover the signal passed through an
inhomogeneous low-rank matrix channel. While the information-theoretic
performances are well-known, we focus on the algorithmic problem. We derive an
approximate message-passing algorithm (AMP) for the inhomogeneous problem and
show that its rigorous state evolution coincides with the information-theoretic
optimal Bayes fixed-point equations. We identify in particular the existence of
a statistical-to-computational gap where known algorithms require a
signal-to-noise ratio bigger than the information-theoretic threshold to
perform better than random. Finally, from the adapted AMP iteration we deduce a
simple and efficient spectral method that can be used to recover the transition
for matrices with general variance profiles. This spectral method matches the
conjectured optimal computational phase transition.
- Abstract（参考訳）: 本稿では,不均質な雑音プロファイルを持つスパイクウィグナー問題について検討する。
この問題における我々の目的は、不均質な低ランクマトリクスチャネルを通過する信号を回復することである。
情報理論のパフォーマンスはよく知られているが,アルゴリズムの問題に注目する。
非均質問題に対する近似メッセージパッシングアルゴリズム(amp)を導出し、その厳密な状態進化が情報理論上最適ベイズ固定点方程式と一致することを示す。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
最後に、適応amp反復から、一般的な分散プロファイルを持つ行列の遷移を回復するために使用できる単純で効率的なスペクトル法を推定する。
このスペクトル法は予測された最適計算相転移と一致する。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Poisson-Gaussian Holographic Phase Retrieval with Score-based Image
Prior [19.231581775644617]
本稿では,スコア関数を先行生成関数とする高速化されたWirtinger Flow (AWF) を用いた新しいアルゴリズム"AWFS"を提案する。
PRの対数様関数の勾配を計算し、リプシッツ定数を決定する。
本稿では,提案アルゴリズムの臨界点収束保証を確立する理論的解析を行う。
論文 参考訳（メタデータ） (2023-05-12T18:08:47Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Learning Sparse Graphs via Majorization-Minimization for Smooth Node
Signals [8.140698535149042]
本稿では,その隣接行列を推定することにより,スパース重み付きグラフを学習するアルゴリズムを提案する。
提案アルゴリズムは,本論文におけるいくつかの既存手法よりも,平均反復回数の観点から,より高速に収束することを示す。
論文 参考訳（メタデータ） (2022-02-06T17:06:13Z) - Fully Adaptive Bayesian Algorithm for Data Analysis, FABADA [0.0]
本稿では,ベイズ推定の観点から,新しい非パラメトリック雑音低減手法について述べる。
データのスムーズなバージョン、スムーズなモデルを繰り返し評価し、基礎となる信号の推定値を得る。
繰り返しは、最後の滑らかなモデルの証拠と$chi2$統計に基づいて停止し、信号の期待値を計算する。
論文 参考訳（メタデータ） (2022-01-13T18:54:31Z) - Matrix completion based on Gaussian belief propagation [5.685589351789462]
行列ファクタリゼーションに基づく雑音マトリクス補完問題に対するメッセージパッシングアルゴリズムの開発を行う。
近似メッセージパッシングの文献によく用いられる摂動処理を適用することにより,提案アルゴリズムのメモリフレンドリーなバージョンを導出する。
合成データセットの実験により, 提案アルゴリズムは, 先行アルゴリズムが最適となる条件下では, ほぼ同じ性能を示すが, 非ガウス雑音により観測されたデータセットが破損した場合に有利であることがわかった。
論文 参考訳（メタデータ） (2021-05-01T12:16:49Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳（メタデータ） (2020-11-18T16:40:45Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Sparse recovery by reduced variance stochastic approximation [5.672132510411465]
雑音観測によるスパース信号回復問題に対する反復2次最適化ルーチンの適用について論じる。
本稿では,Median-of-Meansのような手法を用いて,対応するソリューションの信頼性を向上する方法について述べる。
論文 参考訳（メタデータ） (2020-06-11T12:31:20Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。