論文の概要: Error-Correction for Sparse Support Recovery Algorithms
- arxiv url: http://arxiv.org/abs/2103.03801v1
- Date: Fri, 5 Mar 2021 17:05:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-11 08:33:18.452595
- Title: Error-Correction for Sparse Support Recovery Algorithms
- Title（参考訳）: Sparse Support Recoveryアルゴリズムの誤り訂正
- Authors: Mohammad Mehrabi and Aslan Tchamkerten
- Abstract要約: LiREはノイズレス測定のためのシンプルなエラー補正モジュールです。
orthogonal Matching Pursuitのサブリニアを$m$のエラー数で修正することができる。
実験によると、LiREは完全なサポート回復に必要な測定値を大幅に削減します。
- 参考スコア（独自算出の注目度）: 17.13291434132985
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Consider the compressed sensing setup where the support $s^*$ of an
$m$-sparse $d$-dimensional signal $x$ is to be recovered from $n$ linear
measurements with a given algorithm. Suppose that the measurements are such
that the algorithm does not guarantee perfect support recovery and that true
features may be missed. Can they efficiently be retrieved? This paper addresses
this question through a simple error-correction module referred to as LiRE.
LiRE takes as input an estimate $s_{in}$ of the true support $s^*$, and outputs
a refined support estimate $s_{out}$. In the noiseless measurement setup,
sufficient conditions are established under which LiRE is guaranteed to recover
the entire support, that is $s_{out}$ contains $s^*$. These conditions imply,
for instance, that in the high-dimensional regime LiRE can correct a sublinear
in $m$ number of errors made by Orthogonal Matching Pursuit (OMP). The
computational complexity of LiRE is $O(mnd)$. Experimental results with random
Gaussian design matrices show that LiRE substantially reduces the number of
measurements needed for perfect support recovery via Compressive Sampling
Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to
OMP yields a support recovery procedure that is more accurate and significantly
faster than BP. This observation carries over in the noisy measurement setup.
Finally, as a standalone support recovery algorithm with a random
initialization, experiments show that LiRE's reconstruction performance lies
between OMP and BP. These results suggest that LiRE may be used generically, on
top of any suboptimal baseline support recovery algorithm, to improve support
recovery or to operate with a smaller number of measurements, at the cost of a
relatively small computational overhead. Alternatively, LiRE may be used as a
standalone support recovery algorithm that is competitive with respect to OMP.
- Abstract（参考訳）: a $m$-sparse $d$-dimensional signal $x$の$s^*$が与えられたアルゴリズムで$n$の線形測定から回収されるような圧縮されたセンシング設定を考えてみましょう。
測定値が、アルゴリズムが完全なサポート回復を保証せず、真の特徴が失われる可能性があると仮定する。
効率よく回収できますか。
本稿では,LiREと呼ばれる単純なエラー訂正モジュールを用いてこの問題に対処する。
LiRE は、真のサポート $s^*$ の見積 $s_{in}$ を入力とし、洗練されたサポートの見積 $s_{out}$ を出力する。
ノイズレス測定設定では、LiRE が $s_{out}$ が $s^*$ を含むサポート全体を回復することを保証した十分な条件が確立される。
これらの条件は、例えば、高次元の規則では、LiRE は直交整合法 (OMP) による誤り数$m$$のサブ線形を補正できることを意味する。
LiREの計算複雑性は$O(mnd)$である。
ランダムガウス設計行列を用いた実験の結果、LiREは圧縮サンプリングマッチングスーツ、Basis Pursuit(BP)、OMPを介して完全なサポート回復に必要な測定値を大幅に削減できることが示された。
興味深いことに、LiREをOMPに追加すると、BPよりも正確ではるかに高速なサポート回復手順が得られる。
この観測はノイズ測定装置で継続される。
最後に、ランダム初期化を伴うスタンドアローンサポート回復アルゴリズムとして、LiREの再構成性能がOMPとBPの間にあることを示す実験を行った。
これらの結果は、LiREを任意の最適ベースライン回復アルゴリズムの上に汎用的に使用して、比較的少ない計算オーバーヘッドで、サポートリカバリを改善したり、より少ない測定値で運用することができることを示唆している。
また、LiREは、OMPに関して競争力のあるスタンドアロンのサポートリカバリアルゴリズムとして使用することができる。
関連論文リスト
- Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
政策改善と政策評価の段階を交互に行うモデルフリー学習アルゴリズムであるLoRa-PI(Low-Rank Policy Iteration)を提案する。
LoRa-PIは$widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$サンプルを使用して$varepsilon$-optimal Policyを学習する。
論文 参考訳（メタデータ） (2024-10-30T20:22:17Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。
これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。
本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
論文 参考訳（メタデータ） (2024-02-06T18:59:30Z) - Straight-Through meets Sparse Recovery: the Support Exploration Algorithm [6.12477318852572]
本稿では,スパーシリティを促進する新しいアルゴリズムであるSEA(Support Exploration Algorithm)を導入し,その性能を回復支援問題において解析する。
SEAは最先端技術よりも多くのサポートを探求し、実験において優れたパフォーマンスを実現している。
回復の十分な条件は同等だが、スパースサポートリカバリにおける最先端の条件よりも厳密である。
論文 参考訳（メタデータ） (2023-01-31T12:31:13Z) - Meta Sparse Principal Component Analysis [31.403997435274604]
高次元主成分分析における支援のためのメタラーニング(非零成分集合)について検討した。
補助的なタスクから学習した情報を用いて,新しいタスクにおける十分なサンプルの複雑さを低減する。
論文 参考訳（メタデータ） (2022-08-18T16:28:31Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization
Approach [6.952045528182883]
スパースプラス低ランク分解問題(SLR)について検討する。
SLRはオペレーションリサーチと機械学習の基本的な問題である。
本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
論文 参考訳（メタデータ） (2021-09-26T20:49:16Z) - Multiple Support Recovery Using Very Few Measurements Per Sample [33.20967869233738]
我々は$mathbbRd$で複数のスパースサンプルの線形測定にアクセスできる。
これらのサンプルは$ell$グループに分割することができ、同じグループに属する同じサポートを持つサンプルがある。
サンプルあたりの$m$測定の予算について、その目標は、$ell$の基盤となるサポートを回復することである。
論文 参考訳（メタデータ） (2021-05-20T16:02:27Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Meta Learning for Support Recovery in High-dimensional Precision Matrix
Estimation [31.41834200409171]
高次元精度行列推定における支援のためのメタラーニング(非ゼロ成分の集合)について検討する。
我々の設定では、各タスクは異なるランダムな真の精度行列を持ち、それぞれが異なる可能性がある。
我々は,Omega(log N)/K)$$nのサンプル数に対して,一致する情報理論の下界を証明した。
論文 参考訳（メタデータ） (2020-06-22T20:24:52Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。