論文の概要: A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP)
Algorithm
- arxiv url: http://arxiv.org/abs/2008.08031v1
- Date: Tue, 18 Aug 2020 17:00:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 22:30:59.615154
- Title: A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP)
Algorithm
- Title(参考訳): 2段階一般化ブロック直交マッチング追従法(tsgbomp)アルゴリズム
- Authors: Samrat Mukhopadhyay, and Mrityunjoy Chakraborty
- Abstract要約: いくつかの投射からの未知のスパース信号の回収は、圧縮センシングの重要な目的である。
BOMPのような既存のブロックスパース回復アルゴリズムは、一様ブロックサイズと既知のブロック境界を仮定する。
本稿では,第1段階が粗いブロック位置同定段階である2段階の手順を提案する。
第2のステージは、第1のステージで選択されたウィンドウ内の非ゼロクラスタのより微細なローカライズを実行する。
- 参考スコア(独自算出の注目度): 0.3867363075280543
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recovery of an unknown sparse signal from a few of its projections is the key
objective of compressed sensing. Often one comes across signals that are not
ordinarily sparse but are sparse blockwise. Existing block sparse recovery
algorithms like BOMP make the assumption of uniform block size and known block
boundaries, which are, however, not very practical in many applications. This
paper addresses this problem and proposes a two step procedure, where the first
stage is a coarse block location identification stage while the second stage
carries out finer localization of a non-zero cluster within the window selected
in the first stage. A detailed convergence analysis of the proposed algorithm
is carried out by first defining the so-called pseudoblock-interleaved block
RIP of the given generalized block sparse signal and then imposing upper bounds
on the corresponding RIC. We also extend the analysis for complex vector as
well as matrix entries where it turns out that the extension is non-trivial and
requires special care. Furthermore, assuming real Gaussian sensing matrix
entries, we find a lower bound on the probability that the derived recovery
bounds are satisfied. The lower bound suggests that there are sets of
parameters such that the derived bound is satisfied with high probability.
Simulation results confirm significantly improved performance of the proposed
algorithm as compared to BOMP.
- Abstract(参考訳): いくつかの投射から未知のスパース信号を回収することが圧縮センシングの重要な目的である。
通常はスパースでないがブロック単位でスパースする信号に遭遇することが多い。
BOMPのような既存のブロックスパース回復アルゴリズムは、一様ブロックサイズと既知のブロック境界を仮定するが、多くのアプリケーションではあまり実用的ではない。
本稿では,この問題に対処し,第1段が粗いブロック位置識別段階であり,第2段が第1段で選択されたウィンドウ内の非ゼロクラスタの細かい位置決めを行う2段階の手順を提案する。
提案アルゴリズムの詳細な収束解析は、まず、与えられた一般化ブロックスパース信号のいわゆる擬似ブロックインターリーブブロック RIP を定義し、次に対応する RIC に上限を与える。
複素ベクトルの解析や行列のエントリも拡張し、拡張は非自明で特別な注意が必要であることが分かりました。
さらに,実ガウスセンシング行列エントリを仮定すると,導出回復境界が満たされる確率が下限となる。
下限は、導出境界が高い確率で満たされるようなパラメータの集合が存在することを示唆する。
シミュレーションの結果,BOMPと比較して提案アルゴリズムの性能は有意に向上した。
関連論文リスト
- Group Projected Subspace Pursuit for Block Sparse Signal Reconstruction: Convergence Analysis and Applications [4.297249011611168]
本稿では,グループ・プロジェクテッド・サブスペース・パースーツ(GPSP)アルゴリズムの収束解析について述べる。
GPSPは、観測がうるさいときに真のブロックスパース信号を回復する。
GPSPは様々なブロック間隔やブロックサイズに対して,ほとんどの場合,他のアルゴリズムよりも優れています。
論文 参考訳(メタデータ) (2024-06-01T08:48:06Z) - Convergence and complexity of block majorization-minimization for
constrained block-Riemannian optimization [20.128697661112618]
ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
論文 参考訳(メタデータ) (2023-12-16T05:40:19Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳(メタデータ) (2023-06-15T15:37:31Z) - Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W(W)
論文 参考訳(メタデータ) (2023-06-04T17:52:49Z) - Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization [43.74656748515853]
非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。
a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
論文 参考訳(メタデータ) (2023-05-30T04:10:11Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳(メタデータ) (2021-11-14T21:49:58Z) - Block majorization-minimization with diminishing radius for constrained
nonconvex optimization [9.907540661545328]
BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。
凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
論文 参考訳(メタデータ) (2020-12-07T07:53:09Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。