論文の概要: Fast OMP for Exact Recovery and Sparse Approximation

• arxiv url: http://arxiv.org/abs/2404.00146v1
• Date: Fri, 29 Mar 2024 20:39:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 07:07:01.804524
• Title: Fast OMP for Exact Recovery and Sparse Approximation
• Title（参考訳）: エクササイズリカバリとスパース近似のための高速OMP
• Authors: Huiyuan Yu, Jia He, Maggie Cheng,
• Abstract要約: 本論文は, オリゴナル・マッチング・パースーツ(OMP)を2つの面で前進させる。 各イテレーションで入力信号の投影を高速に行うアルゴリズムと、グリーディ選択のための新しい選択基準を提供する。 実験結果は計算時間において古典的なOMPよりも大幅に改善したことを示している。
• 参考スコア（独自算出の注目度）: 4.915061940934031
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Orthogonal Matching Pursuit (OMP) has been a powerful method in sparse signal recovery and approximation. However OMP suffers computational issue when the signal has large number of non-zeros. This paper advances OMP in two fronts: it offers a fast algorithm for the orthogonal projection of the input signal at each iteration, and a new selection criterion for making the greedy choice, which reduces the number of iterations it takes to recover the signal. The proposed modifications to OMP directly reduce the computational complexity. Experiment results show significant improvement over the classical OMP in computation time. The paper also provided a sufficient condition for exact recovery under the new greedy choice criterion. For general signals that may not have sparse representations, the paper provides a bound for the approximation error. The approximation error is at the same order as OMP but is obtained within fewer iterations and less time.
• Abstract（参考訳）: OMP (Orthogonal Matching Pursuit) はスパース信号の回復と近似において強力な手法である。 しかし、OMPは信号が多数非ゼロであるときに計算上の問題に悩まされる。 本稿では,入力信号の各繰り返しの直交射影に対する高速なアルゴリズムと,信号の回復に要する繰り返し数を削減した欲求選択のための新しい選択基準を提供する。 提案したOMPの修正により、計算複雑性は直接的に減少する。 実験結果は計算時間において古典的なOMPよりも大幅に改善したことを示している。 また,新たな欲求選択基準の下での正確な回復に十分な条件も提示した。 スパース表現を持たない一般的な信号に対しては、近似誤差のバウンダリを提供する。 近似誤差はOMPと同じ順序であるが、より少ないイテレーションと少ない時間で得られる。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
  マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。 我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
  論文  参考訳（メタデータ） (2023-10-01T03:57:13Z)
• Provably Convergent Subgraph-wise Sampling for Fast GNN Training [122.68566970275683]
  収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。 LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。 大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。
  論文  参考訳（メタデータ） (2023-03-17T05:16:49Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering [18.888312436971187]
  本稿では,一般化OMP(GOMP)を用いた新しいSSC方式を提案する。 GOMPはイテレーションが少ないため、アルゴリズムの複雑さが低い。 提案した停止規則は,部分空間次元と雑音パワーのオフライン推定が不要である。
  論文  参考訳（メタデータ） (2022-04-06T04:20:35Z)
• Fast, Accurate and Memory-Efficient Partial Permutation Synchronization [15.813217907813778]
  観測された部分置換の劣化レベルを推定するための改良されたアルゴリズムCEMP-Partialを提案する。 敵対的腐敗の下では、付加的なノイズが無く、特定の仮定でCEMP-Partialは、破損した部分置換を正確に分類することができる。 提案手法の精度,高速化,メモリ効率を,合成データと実データの両方で実証する。
  論文  参考訳（メタデータ） (2022-03-30T17:41:17Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• DeepMP for Non-Negative Sparse Decomposition [14.790515227906257]
  非負の信号はスパース信号の重要なクラスを形成する。 greedyとconvexの緩和アルゴリズムは、最も人気のある方法のひとつです。 このような修正の1つは、Matching Pursuit (MP) ベースのアルゴリズムのために提案されている。
  論文  参考訳（メタデータ） (2020-07-28T14:52:06Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

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

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