論文の概要: Dynamic Sample Complexity for Exact Sparse Recovery using Sequential Iterative Hard Thresholding

• arxiv url: http://arxiv.org/abs/2103.00449v1
• Date: Sun, 28 Feb 2021 10:37:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-03 15:46:01.121115
• Title: Dynamic Sample Complexity for Exact Sparse Recovery using Sequential Iterative Hard Thresholding
• Title（参考訳）: 逐次反復ハードホールドを用いた正確なスパース回収のための動的サンプル複雑性
• Authors: Samrat Mukhopadhyay
• Abstract要約: 測定行列が対応する測定値とともに連続的に到着する固定スパースベクトルの正確な回復問題を考察する。 連続IHTと呼ばれる反復的ハードしきい値化アルゴリズムの拡張を提案し、総時間の地平線を数段階に分割する。 各段階における測定行列の大きさと、その期間と位相の数に依存する特定の動的サンプルの複雑さが、一定の下限を満たす場合、固定時間線上のSIHTの推定誤差は急速に崩壊することを証明します。
• 参考スコア（独自算出の注目度）: 0.9137554315375919
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we consider the problem of exact recovery of a fixed sparse vector with the measurement matrices sequentially arriving along with corresponding measurements. We propose an extension of the iterative hard thresholding (IHT) algorithm, termed as sequential IHT (SIHT) which breaks the total time horizon into several phases such that IHT is executed in each of these phases using a fixed measurement matrix obtained at the beginning of that phase. We consider a stochastic setting where the measurement matrices obtained at each phase are independent samples of a sub Gaussian random matrix. We prove that if a certain dynamic sample complexity that depends on the sizes of the measurement matrices at each phase, along with their duration and the number of phases, satisfy certain lower bound, the estimation error of SIHT over a fixed time horizon decays rapidly. Interestingly, this bound reveals that the probability of decay of estimation error is hardly affected even if very small number measurements are sporadically used in different phases. This theoretical observation is also corroborated using numerical experiments demonstrating that SIHT enjoys improved probability of recovery compared to offline IHT.
• Abstract（参考訳）: 本稿では,連続的に到達する測定行列と対応する測定値との固定スパースベクトルの正確な回復の問題を検討する。 本研究では, 繰り返しハードしきい値化 (IHT) アルゴリズムの拡張を提案する。このアルゴリズムはシーケンシャル IHT (SIHT) と呼ばれ, 総時間線を各フェーズでIHTが実行されるような数段階に分割する。 我々は,各位相で得られる測定行列が,ガウスの確率行列の独立なサンプルである確率的集合を考える。 各段階における測定行列の大きさと、その期間と位相の数に依存する特定の動的サンプルの複雑さが、一定の下限を満たす場合、固定時間線上のSIHTの推定誤差は急速に崩壊することを証明します。 興味深いことに、この境界は、非常に小さな数の測定が異なる位相で散発的に使われているとしても、推定誤差の崩壊の確率がほとんど影響しないことを示している。 この理論的観察は、SIHTがオフラインIHTと比較して回復の確率を改善することを実証した数値実験を用いても相関する。

関連論文リスト

• On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs) [12.810268045479992]
  本研究では,DiTsスコア関数の普遍近似とサンプル複雑性について検討した。 我々は、潜伏型DiTが初期データの高次元性に関わる課題を回避できる可能性を示している。
  論文  参考訳（メタデータ） (2024-07-01T08:34:40Z)
• Compatible Transformer for Irregularly Sampled Multivariate Time Series [75.79309862085303]
  本研究では,各サンプルに対して総合的な時間的相互作用特徴学習を実現するためのトランスフォーマーベースのエンコーダを提案する。 実世界の3つのデータセットについて広範な実験を行い、提案したCoFormerが既存の手法を大幅に上回っていることを検証した。
  論文  参考訳（メタデータ） (2023-10-17T06:29:09Z)
• Provable Phase Retrieval with Mirror Descent [1.1662472705038338]
  我々は,その挙動の程度から$n$-mの実ベクトルを復元する位相探索の問題を考察する。 2つの測定値について、n$の値が十分であれば、ほとんどすべての初期化子に対して高い確率で元のベクトルが符号まで回復することを示す。
  論文  参考訳（メタデータ） (2022-10-17T16:40:02Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Anomaly Attribution of Multivariate Time Series using Counterfactual Reasoning [7.616400192843963]
  我々は,反実的推論に基づく多変量時系列の新しい帰属スキームを開発した。 MDI(Maximally Divergent Interval)アルゴリズムを用いて異常区間を検出する。
  論文  参考訳（メタデータ） (2021-09-14T10:15:52Z)
• Generalized quantum measurements with matrix product states: Entanglement phase transition and clusterization [58.720142291102135]
  本研究では,多体量子格子系の時間的発展を連続的およびサイト分解的測定により研究する手法を提案する。 測定によって引き起こされる粒子クラスター化の現象は, 頻繁な中等度な測定のためではなく, 頻繁な測定のためにのみ発生する。
  論文  参考訳（メタデータ） (2021-04-21T10:36:57Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。 この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
  論文  参考訳（メタデータ） (2021-01-16T17:11:02Z)
• Multi-time correlations in the positive-P, Q, and doubled phase-space representations [0.0]
  正-P分布における時間順序正規順序量子オブザーバの式は、ハイゼンベルク作用素を素時間依存変数に置き換えることが示されている。 位相空間表現におけるマルチ時間可観測性の理論は拡張され、多くのケースの非摂動的処理が可能である。
  論文  参考訳（メタデータ） (2020-11-19T21:17:31Z)
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval [24.17778927729799]
  スパース位相探索に適用した連続時間ミラーを解析する。 これは、測定のみの集合からスパース信号を復元する問題である。 この問題に対して収束解析アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-20T10:03:44Z)
• Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states [48.705095800341944]
  隠れマルコフモデルのためのマルコフ連鎖モンテカルロ (MCMC) アルゴリズムは、しばしば前向きのサンプリング器に依存する。 これにより、時系列の長さが増加するにつれて計算が遅くなり、サブサンプリングベースのアプローチの開発が動機となる。 本稿では,パラメータの勾配を計算する際に,希少な潜伏状態に対応するオーバーサンプリング観測を対象とするサブサンプリング手法を提案する。
  論文  参考訳（メタデータ） (2018-10-31T17:44:20Z)

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

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