論文の概要: Reconstructing Sparse Signals via Greedy Monte-Carlo Search

• arxiv url: http://arxiv.org/abs/2008.03175v3
• Date: Fri, 29 Jan 2021 09:05:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-02 01:02:08.389131
• Title: Reconstructing Sparse Signals via Greedy Monte-Carlo Search
• Title（参考訳）: グレディモンテカルロ探索によるスパース信号の再構成
• Authors: Kao Hayashi, Tomoyuki Obuchi, Yoshiyuki Kabashima
• Abstract要約: 高次元環境下でスパース信号を再構成するモンテカルロ法を提案する。 欲求モンテカルロ探索アルゴリズムは、欲求モンテカルロ探索アルゴリズム (greedy Monte-Carlo search algorithm) と呼ばれる。
• 参考スコア（独自算出の注目度）: 6.660458629649825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a Monte-Carlo-based method for reconstructing sparse signals in the formulation of sparse linear regression in a high-dimensional setting. The basic idea of this algorithm is to explicitly select variables or covariates to represent a given data vector or responses and accept randomly generated updates of that selection if and only if the energy or cost function decreases. This algorithm is called the greedy Monte-Carlo (GMC) search algorithm. Its performance is examined via numerical experiments, which suggests that in the noiseless case, GMC can achieve perfect reconstruction in undersampling situations of a reasonable level: it can outperform the $\ell_1$ relaxation but does not reach the algorithmic limit of MC-based methods theoretically clarified by an earlier analysis. The necessary computational time is also examined and compared with that of an algorithm using simulated annealing. Additionally, experiments on the noisy case are conducted on synthetic datasets and on a real-world dataset, supporting the practicality of GMC.
• Abstract（参考訳）: 高次元空間におけるスパース線形回帰の定式化におけるスパース信号を再構成するモンテカルロ法を提案する。 このアルゴリズムの基本的な考え方は、与えられたデータベクトルまたは応答を表す変数または共変数を明示的に選択し、その選択のランダムに生成された更新を受け付けることである。 このアルゴリズムは greedy monte-carlo (gmc) search algorithm と呼ばれる。 その性能は数値実験によって検証され、ノイズレスの場合、GCCは妥当なレベルのアンダーサンプリングの状況において完全な再構築を達成でき、$\ell_1$緩和よりも優れているが、理論上はMCベースの手法のアルゴリズム的限界に到達しない。 必要な計算時間についても検討し,シミュレーションアニーリングを用いたアルゴリズムと比較した。 さらに, 合成データセットと実世界のデータセットを用いて, GMCの実用性を支持するノイズケース実験を行った。

関連論文リスト

• Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
  人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。 提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。 結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-10-23T04:19:35Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Greedy versus Map-based Optimized Adaptive Algorithms for random-telegraph-noise mitigation by spectator qubits [6.305016513788048]
  データストレージキュービットを可能な限り分離したままにしておくシナリオでは、ノイズプローブを追加してノイズ軽減を行うことができる。 量子ビット上の射影的測定を仮定した理論モデルを構築し、異なる測定・制御戦略の性能を導出する。 解析的および数値的に、MOAAARは、特にSQの高雑音感度状態において、Greedyアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-25T08:25:10Z)
• 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)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。 我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。 数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2020-11-18T16:40:45Z)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。 行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-15T13:40:07Z)
• Semi-analytic approximate stability selection for correlated data in generalized linear models [3.42658286826597]
  そこで本研究では,繰り返しのフィッティングを行なわずに安定選択を行うことのできる,新しい近似推論アルゴリズムを提案する。 このアルゴリズムは,情報理論の統計力学とベクトル近似メッセージパッシングの複製法に基づく。 数値実験により, このアルゴリズムは, 合成データと実世界のデータの両方に対して, 高速収束と高い近似精度を示すことを示した。
  論文  参考訳（メタデータ） (2020-03-19T10:43:12Z)

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

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