論文の概要: Robust 1-bit Compressed Sensing with Iterative Hard Thresholding
- arxiv url: http://arxiv.org/abs/2310.08019v1
- Date: Thu, 12 Oct 2023 03:41:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-14 13:03:52.779680
- Title: Robust 1-bit Compressed Sensing with Iterative Hard Thresholding
- Title（参考訳）: 反復型ハードThresholdingを用いたロバスト1ビット圧縮センシング
- Authors: Namiko Matsumoto, Arya Mazumdar
- Abstract要約: 1ビット圧縮センシングでは、$k$スパース単位ベクトル$xin Sn-1$を$epsilon$エラー内で推定する。
本稿では,一部の計測値のフリップが可能な雑音バージョンを,潜在的に敵によって検討する。
BIHTallyは$tildeO(epsilon+tau)$エラーで$x$と見積もる。
- 参考スコア（独自算出の注目度）: 18.05573480691047
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In 1-bit compressed sensing, the aim is to estimate a $k$-sparse unit vector
$x\in S^{n-1}$ within an $\epsilon$ error (in $\ell_2$) from minimal number of
linear measurements that are quantized to just their signs, i.e., from
measurements of the form $y = \mathrm{Sign}(\langle a, x\rangle).$ In this
paper, we study a noisy version where a fraction of the measurements can be
flipped, potentially by an adversary. In particular, we analyze the Binary
Iterative Hard Thresholding (BIHT) algorithm, a proximal gradient descent on a
properly defined loss function used for 1-bit compressed sensing, in this noisy
setting. It is known from recent results that, with
$\tilde{O}(\frac{k}{\epsilon})$ noiseless measurements, BIHT provides an
estimate within $\epsilon$ error. This result is optimal and universal, meaning
one set of measurements work for all sparse vectors. In this paper, we show
that BIHT also provides better results than all known methods for the noisy
setting. We show that when up to $\tau$-fraction of the sign measurements are
incorrect (adversarial error), with the same number of measurements as before,
BIHT agnostically provides an estimate of $x$ within an
$\tilde{O}(\epsilon+\tau)$ error, maintaining the universality of measurements.
This establishes stability of iterative hard thresholding in the presence of
measurement error. To obtain the result, we use the restricted approximate
invertibility of Gaussian matrices, as well as a tight analysis of the
high-dimensional geometry of the adversarially corrupted measurements.
- Abstract（参考訳）: 1ビット圧縮センシングでは、$k$-sparse単位ベクトル$x\in S^{n-1}$を$\epsilon$エラー($\ell_2$)の中で、符号のみに量子化される最小の線形測度、すなわち、$y = \mathrm{Sign}(\langle a, x\rangle a, x\rangle)から推定する。
この論文では、一部の測定値が反転しうるノイズのあるバージョンを、潜在的に敵対者によって研究する。
特に,1ビット圧縮センシングに使用される正規な損失関数上での近位勾配降下であるbihtアルゴリズムを,この雑音条件下で解析した。
最近の結果から、$\tilde{O}(\frac{k}{\epsilon})$ noiseless Measurement で BIHT は $\epsilon$ error 内で推定値を提供することが知られている。
この結果は最適かつ普遍的であり、一組の計測がすべてのスパースベクトルに対して働くことを意味する。
本稿では, BIHTが, ノイズ設定のためのすべての既知の手法よりも優れた結果を提供することを示す。
符号測定値の最大$\tau$-フラクテーションが誤り(逆誤差)である場合、bihtは従来と同じ数の測定値を持つ場合、$\tilde{o}(\epsilon+\tau)$エラーの範囲内でx$の見積もりを提供し、測定の普遍性を維持する。
これにより、測定誤差の存在下で繰り返しハードしきい値の安定性が確立される。
この結果を得るために、ガウス行列の制限された近似的可逆性と、逆向きに破損した測定の高次元幾何学の厳密な解析を用いる。
関連論文リスト
- Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data [3.1138411427556445]
測定制約のある問題では、大きなデータセットが利用可能であるにもかかわらず、大きなデータセットのごく一部でラベルを観測するのに手頃な価格にしかならない。
このことは、どのデータポイントが予算制約のあるラベルに最も有益であるかという重要な疑問を引き起こします。
本稿では,測定制約付きM推定フレームワークにおける最適個別化しきい値の推定に焦点をあてる。
論文 参考訳（メタデータ） (2024-11-21T00:21:17Z) - Binary Iterative Hard Thresholding Converges with Optimal Number of
Measurements for 1-Bit Compressed Sensing [29.570141048369297]
BIHT アルゴリズムは $tildeO (frackepsilon) 測定でのみ収束することを示す。
これは非問題に対する正しい解に収束する線形降下アルゴリズムの例でもある。
論文 参考訳（メタデータ） (2022-07-07T16:52:50Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - Support Recovery in Universal One-bit Compressed Sensing [54.26691979520478]
1ビット圧縮センシング (1bCS) は極端量子化信号取得法である。
少数の偽陽性で支持を普遍的に回復することは可能であることを示す。
論文 参考訳（メタデータ） (2021-07-19T18:10:51Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Online Robust Regression via SGD on the l1 loss [19.087335681007477]
ストリーミング方式でデータにアクセス可能なオンライン環境において、ロバストな線形回帰問題を考察する。
この研究で、$ell_O( 1 / (1 - eta)2 n )$損失の降下は、汚染された測定値に依存しない$tildeO( 1 / (1 - eta)2 n )$レートで真のパラメータベクトルに収束することを示した。
論文 参考訳（メタデータ） (2020-07-01T11:38:21Z) - The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
我々は、幅広い測定モデルで満たされるガウス下測度を仮定する。
この結果から, 局所埋込特性を仮定して, 均一回復保証まで拡張できることが示唆された。
論文 参考訳（メタデータ） (2020-06-22T16:43:35Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳（メタデータ） (2020-06-09T02:05:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。