論文の概要: Revisiting Matching Pursuit: Beyond Approximate Submodularity
- arxiv url: http://arxiv.org/abs/2305.07782v1
- Date: Fri, 12 May 2023 22:03:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 19:47:34.214472
- Title: Revisiting Matching Pursuit: Beyond Approximate Submodularity
- Title（参考訳）: マッチング追跡の再検討:近似部分モジュラリティを超えて
- Authors: Ehsan Tohidi, Mario Coutino, David Gesbert
- Abstract要約: 本研究では,大集合からベクトルの部分集合を選択する問題について検討し,関数群に対する最良の信号表現を得る。
期待において劣モジュラであることを示す関数を導入する。
この関数は、期待するときにグリーディアルゴリズムによってほぼ最適性を保証するだけでなく、よく使われるマッチング追従法(MP)アルゴリズムの既存の欠陥を緩和する。
- 参考スコア（独自算出の注目度）: 27.284246496104238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of selecting a subset of vectors from a large set, to
obtain the best signal representation over a family of functions. Although
greedy methods have been widely used for tackling this problem and many of
those have been analyzed under the lens of (weak) submodularity, none of these
algorithms are explicitly devised using such a functional property. Here, we
revisit the vector-selection problem and introduce a function which is shown to
be submodular in expectation. This function does not only guarantee
near-optimality through a greedy algorithm in expectation, but also alleviates
the existing deficiencies in commonly used matching pursuit (MP) algorithms. We
further show the relation between the single-point-estimate version of the
proposed greedy algorithm and MP variants. Our theoretical results are
supported by numerical experiments for the angle of arrival estimation problem,
a typical signal representation task; the experiments demonstrate the benefits
of the proposed method with respect to the traditional MP algorithms.
- Abstract（参考訳）: 本研究では,大集合からベクトルの部分集合を選択する問題について検討し,関数群に対する最良の信号表現を得る。
グリード法はこの問題に対処するために広く使われており、その多くが(弱)部分モジュラリティのレンズの下で解析されているが、これらのアルゴリズムはそのような機能的特性を用いて明示的に考案されていない。
本稿では,ベクトル選択問題を再検討し,期待される部分モジュラー関数を導入する。
この関数は、期待するときにグリーディアルゴリズムによってほぼ最適性を保証するだけでなく、よく使われるマッチング追従(MP)アルゴリズムの既存の欠陥を軽減する。
さらに,提案アルゴリズムの単一点推定バージョンとMP変異との関係について述べる。
本研究は,従来のMPアルゴリズムに対して提案手法の利点を実証した,典型的な信号表現課題である到着推定問題の角度に関する数値実験によって支持された。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Fast Feature Selection with Fairness Constraints [49.142308856826396]
モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
論文 参考訳（メタデータ） (2022-02-28T12:26:47Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie [13.476505672245603]
本稿では,ベイズ推定を事前に行うための理論,方法,および証明可能な収束アルゴリズムを開発する。
モンテカルロサンプリングとMMSEに対する-ULA(Unadjusted Langevin)アルゴリズム推論と、推論のための定量的SGD(Stochastic Gradient Descent)の2つのアルゴリズムを紹介します。
このアルゴリズムは、点推定や不確実性の可視化や規則性に使用される画像のノイズ除去、インペインティング、ノイズ除去などのいくつかの問題で実証されています。
論文 参考訳（メタデータ） (2021-03-08T12:46:53Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。
リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。
このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文 参考訳（メタデータ） (2021-02-27T19:28:39Z) - Efficient Consensus Model based on Proximal Gradient Method applied to
Convolutional Sparse Problems [2.335152769484957]
我々は、勾配近似(PG)アプローチに基づく効率的なコンセンサスアルゴリズムの理論解析を導出し、詳述する。
提案アルゴリズムは、異常検出タスクに対する別の特別な畳み込み問題にも適用できる。
論文 参考訳（メタデータ） (2020-11-19T20:52:48Z) - 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) - Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。
GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。
実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
論文 参考訳（メタデータ） (2020-06-20T00:17:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。