論文の概要: On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing
- arxiv url: http://arxiv.org/abs/2607.15530v1
- Date: Fri, 17 Jul 2026 00:44:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-20 17:56:52.723042
- Title: On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing
- Title（参考訳）: 1ビット圧縮センシングにおける2成分繰り返しハード閾値の正規化の役割について
- Abstract要約: Binary Iterative Hard Thresholding (BIHT) は、1ビットの符号測定からスパースベクトルを復元するための単純かつ効果的で欲求的な方法である。
このアルゴリズムの収束解析は [Jac+11] の入門研究に残され、10年以上未解決のままである。
本論文は, アルゴリズムによる定位正規化が必要とされる場合に, ギャップを解消し, 特徴付ける。
- 参考スコア（独自算出の注目度）: 18.637825309463125
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements. In its original form, BIHT performs a ``gradient-descent'' step, followed by hard thresholding. A convergence analysis of this algorithm was left open in the introductory work of [Jac+11] and has remained unresolved for over a decade, with subsequent sharp analyses studying a normalized variant instead, that additionally projects every iterate onto the unit sphere. This paper resolves that gap and characterizes when per-iteration normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with $\widetilde O(s/ε)$ measurements, a deterministic finite-time iterate has directional error at most $ε$, simultaneously for every $s$-sparse unit vector. This matches the optimal sample dependence achieved by normalized BIHT in prior work. Thus, in the noiseless regime, per-iterate normalization is unnecessary for optimal recovery. Under sign corruptions, we prove a sharp separation. If at most a $τ$ fraction of signs are flipped adversarially, then BIHT, without per-iterate normalization, still reaches the robust error floor at an early iterate with a matching $\widetilde O(s/ε)$ sample complexity rate as its normalized variant. This recovery, however, is not stable. We prove a scalar lower bound showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely. Consequently, no general last-iterate convergence theorem can hold for BIHT under sign corruptions, while its normalized surrogate provably escapes this instance.
- Abstract（参考訳）: Binary Iterative Hard Thresholding (BIHT) は、1ビットの符号測定からスパースベクトルを復元するための単純かつ効果的で欲求的な方法である。
BIHT は元々の形式で `gradient-descent'' ステップを実行し、その後にハードしきい値が続く。
このアルゴリズムの収束解析は [Jac+11] の入門研究に残され、その後10年以上も未解決のままであり、その後に正規化された変種を研究し、さらに全ての反復を単位球に投影した。
本論文は, アルゴリズムによる定位正規化が必要とされる場合に, ギャップを解消し, 特徴付ける。
ノイズのない環境では、元のBIHTアルゴリズムに対する普遍的、標本最適収束定理が証明される。
具体的には、$\widetilde O(s/ε)$測定では、決定論的有限時間イテレートは、任意の$s$スパース単位ベクトルに対して、最大$ε$の方向誤差を持つ。
これは、前の作業で正常化されたBIHTによって達成された最適なサンプル依存と一致する。
したがって、ノイズレス方式では、最適回復には石材ごとの正規化は不要である。
汚職のサインのもと、我々は急激な分離を証明した。
もし少なくとも$τ$の符号が逆向きに反転するなら、BIHTは単体正規化なしでも、一致する$\widetilde O(s/ε)$サンプル複雑性率を正規化された変種として、早期反復で頑健なエラーフロアに到達する。
しかし、この回復は安定していない。
我々は、任意の非自明な汚職パターン、つまり、1つのフリップされたサインと1つのクリーンサインを同時に含むものでさえも、イテレーションを無期限に振動させてしまうことを示すスカラーな下界を証明した。
したがって、符号の汚職の下では、BIHT に対する一般的な最終点収束定理は持たないが、正規化された代理は、この例を確実に逃がす。
関連論文リスト
- Approximate Message Passing with Random Initialization for Phase Retrieval [7.7572821781975]
AMP軌道のガウス分解を証明し、回復に必要な水平線上の誤差を制御する。
我々の分析の大部分は、より一般的に単射モデルに対する一般化AMPに適用される。
論文 参考訳（メタデータ） (2026-08-03T03:44:13Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions [1.0098114696565863]
SupSplitLogは、コンテキストの多様性を仮定せずに$tildemathcalO(sqrtdT)$ regretを達成するロジスティックバンディットのための最初のアルゴリズムである。
SupSplitLogは、後悔の上限における次元$d$への依存の観点から、既存のアルゴリズムを厳密に改善する。
論文 参考訳（メタデータ） (2026-04-24T02:21:59Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity [4.655159257282136]
位相探索のアルゴリズムにおける主要な考慮事項は、測定誤差に対する堅牢性である。
本稿では,重み付き雑音を用いたロバスト位相探索のための効率的なアルゴリズムについて検討する。
論文 参考訳（メタデータ） (2026-01-26T08:06:16Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。
解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
論文 参考訳（メタデータ） (2024-04-27T10:20:41Z) - 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) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - 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) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳（メタデータ） (2020-10-26T01:33:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。