論文の概要: Analysis of The Ratio of $\ell_1$ and $\ell_2$ Norms in Compressed
Sensing
- arxiv url: http://arxiv.org/abs/2004.05873v2
- Date: Thu, 28 Jan 2021 00:09:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-14 00:38:07.470917
- Title: Analysis of The Ratio of $\ell_1$ and $\ell_2$ Norms in Compressed
Sensing
- Title(参考訳): 圧縮センシングにおける$\ell_1$および$\ell_2$ノルム比の解析
- Authors: Yiming Xu, Akil Narayan, Hoang Tran and Clayton G. Webster
- Abstract要約: まず、$ssparser信号が$ell_1/ell$アルゴリズムのローカル$sparserであることを保証する新しい基準を提案する。
次に、幾何学的零空間を用いて、最初の一様回復条件を与える。
実験により、ノイズがデータに汚染されると、この条件は容易に満たされることが示された。
- 参考スコア(独自算出の注目度): 4.755908500065439
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We first propose a novel criterion that guarantees that an $s$-sparse signal
is the local minimizer of the $\ell_1/\ell_2$ objective; our criterion is
interpretable and useful in practice. We also give the first uniform recovery
condition using a geometric characterization of the null space of the
measurement matrix, and show that this condition is easily satisfied for a
class of random matrices. We also present analysis on the robustness of the
procedure when noise pollutes data. Numerical experiments are provided that
compare $\ell_1/\ell_2$ with some other popular non-convex methods in
compressed sensing. Finally, we propose a novel initialization approach to
accelerate the numerical optimization procedure. We call this initialization
approach \emph{support selection}, and we demonstrate that it empirically
improves the performance of existing $\ell_1/\ell_2$ algorithms.
- Abstract(参考訳): まず,$s$-sparse信号が$\ell_1/\ell_2$目的の局所最小値であることを保証する新しい基準を提案する。
また, 測定行列の零空間の幾何学的特徴を用いた最初の均一回復条件を与え, ランダム行列のクラスに対して, この条件が容易に満たされることを示す。
また,ノイズがデータを汚染する場合のロバスト性について解析する。
圧縮センシングにおいて、$\ell_1/\ell_2$と他の一般的な非凸法を比較する数値実験が提供される。
最後に,数値最適化手法を高速化する新しい初期化手法を提案する。
この初期化手法をemph{ Support selection}と呼び、既存の$\ell_1/\ell_2$アルゴリズムの性能を実証的に改善することを示した。
関連論文リスト
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳(メタデータ) (2024-01-14T14:14:19Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳(メタデータ) (2023-01-26T05:34:21Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。
理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
論文 参考訳(メタデータ) (2022-07-30T13:05:01Z) - Alternating minimization for generalized rank one matrix sensing: Sharp
predictions from a random initialization [10.516962652888989]
ランクランダム行列の特性をdで推定する手法を示す。
鋭い収束は、単一のステップで正確な回復を保証する。
我々の分析は、この問題の他のいくつかの特性も明らかにしている。
論文 参考訳(メタデータ) (2022-07-20T05:31:05Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳(メタデータ) (2021-06-29T12:49:54Z) - Debiasing Distributed Second Order Optimization with Surrogate Sketching
and Scaled Regularization [101.5159744660701]
分散第2次最適化において、標準的な戦略は、データの小さなスケッチやバッチに基づいて、多くの局所的な見積もりを平均化することである。
本稿では,分散二階法における収束率の理論的および実証的改善を両立させるため,局所的な推定を嫌悪する新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-02T18:08:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。