論文の概要: Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise
- arxiv url: http://arxiv.org/abs/2405.18081v1
- Date: Tue, 28 May 2024 11:42:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-29 18:48:53.632104
- Title: Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise
- Title(参考訳): 回転不変雑音を有するスパイク行列モデルに対する近似メッセージパッシングアルゴリズムの最適性
- Authors: Rishabh Dudeja, Songbin Liu, Junjie Ma,
- Abstract要約: 本研究では,信号に加法的回転不変雑音を付加して発生する観測行列からランク1信号行列を推定する問題について検討する。
この問題に対する近似メッセージパッシングアルゴリズムの新たなクラスを開発し、高次元極限におけるそれらのダイナミクスの簡易かつ簡潔な特徴付けを提供する。
- 参考スコア(独自算出の注目度): 12.64438771302935
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of estimating a rank one signal matrix from an observed matrix generated by corrupting the signal with additive rotationally invariant noise. We develop a new class of approximate message-passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit. At each iteration, these algorithms exploit prior knowledge about the noise structure by applying a non-linear matrix denoiser to the eigenvalues of the observed matrix and prior information regarding the signal structure by applying a non-linear iterate denoiser to the previous iterates generated by the algorithm. We exploit our result on the dynamics of these algorithms to derive the optimal choices for the matrix and iterate denoisers. We show that the resulting algorithm achieves the smallest possible asymptotic estimation error among a broad class of iterative algorithms under a fixed iteration budget.
- Abstract(参考訳): 本研究では,信号に加法的回転不変雑音を付加して発生する観測行列からランク1信号行列を推定する問題について検討する。
この問題に対する近似メッセージパッシングアルゴリズムの新たなクラスを開発し、高次元極限におけるそれらのダイナミクスの簡易かつ簡潔な特徴付けを提供する。
各繰り返しにおいて、これらのアルゴリズムは、観測された行列の固有値に非線形行列 denoiser を適用することで、ノイズ構造に関する事前知識と、そのアルゴリズムが生成した前のイテレーションに非線形反復行列 denoiser を適用することによって、信号構造に関する事前情報を利用する。
我々は,これらのアルゴリズムのダイナミクスを利用して,行列と反復デノイザの最適選択を導出する。
提案手法は,固定反復予算の下で,広範囲な反復アルゴリズムのうち,最小限の漸近推定誤差を達成できることを示す。
関連論文リスト
- Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks [15.074950361970194]
我々は、IRLS、最近提案されたリンリン-RFMアルゴリズム、交互対角ニューラルネットワークを含むアルゴリズム群を統一的に分析する。
適切に選択された再重み付けポリシーにより、少数のスパース構造が良好な性能が得られることを示す。
また、これを再重み付け方式で活用することで、座標ワイド再重み付けよりもテスト誤差が良好に向上することを示す。
論文 参考訳(メタデータ) (2024-06-04T20:37:17Z) - Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise [19.496063739638924]
構造スパイクモデルに対するベイズ推定の飽和問題を考える。
適応的なThouless-Anderson-Palmer方程式の理論にインスパイアされた効率的なアルゴリズムを用いて、統計的限界を予測する方法を示す。
論文 参考訳(メタデータ) (2024-05-31T16:38:35Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-30T15:57:14Z) - Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
我々はロバスト成分分析のためのアルゴリズムを設計する(A)
行列を低主行列とスパース主行列の和に分解する。
論文 参考訳(メタデータ) (2023-07-12T03:48:26Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-11T07:28:35Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳(メタデータ) (2023-02-13T19:57:17Z) - Learning Sparse Graphs via Majorization-Minimization for Smooth Node
Signals [8.140698535149042]
本稿では,その隣接行列を推定することにより,スパース重み付きグラフを学習するアルゴリズムを提案する。
提案アルゴリズムは,本論文におけるいくつかの既存手法よりも,平均反復回数の観点から,より高速に収束することを示す。
論文 参考訳(メタデータ) (2022-02-06T17:06:13Z) - Matrix Reordering for Noisy Disordered Matrices: Optimality and
Computationally Efficient Algorithms [9.245687221460654]
単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。
我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。
そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-01-17T14:53:52Z) - Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。
行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-15T13:40:07Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳(メタデータ) (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。