On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing

• URL: http://arxiv.org/abs/2607.15530v2
• Date: Wed, 22 Jul 2026 13:08:27 GMT
• Title: On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing
• Abstract summary: Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements.<n>A convergence analysis of this algorithm was left open in the introductory work of [Jac+11] and has remained unresolved for over a decade.<n>This paper resolves that gap and characterizes when per-iteration normalization is algorithmically necessary.
• Score: 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.

Related papers

• Approximate Message Passing with Random Initialization for Phase Retrieval [7.7572821781975]
  We prove a Gaussian decomposition of the AMP trajectory and control its error over the horizons required for recovery.<n>The majority of our analysis applies more generally to generalized AMP for single-index models.
  arXiv  Detail & Related papers  (2026-08-03T03:44:13Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions [1.0098114696565863]
  SupSplitLog is the first algorithm for logistic bandits that achieves $tildemathcalO(sqrtdT)$ regret without any context diversity assumption.<n>SupSplitLog strictly improves on the existing algorithms in terms of the dependence on dimension $d$ in the regret upper bound.
  arXiv  Detail & Related papers  (2026-04-24T02:21:59Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity [4.655159257282136]
  A major consideration in algorithms for phase retrieval is robustness against measurement errors.<n>In this paper, we study efficient algorithms for robust phase retrieval with heavy-tailed noise.
  arXiv  Detail & Related papers  (2026-01-26T08:06:16Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
  This paper investigates the iterates $hbb1,dots,hbbT$ obtained from iterative algorithms in high-dimensional linear regression problems. The analysis and proposed estimators are applicable to Gradient Descent (GD), GD and their accelerated variants such as Fast Iterative Soft-Thresholding (FISTA)
  arXiv  Detail & Related papers  (2024-04-27T10:20:41Z)
• Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing [29.570141048369297]
  We show that the BIHT algorithm converges with only $tildeO(frackepsilon) measurements. This is also an example of a linear descent algorithm converging to the correct solution for a non problem.
  arXiv  Detail & Related papers  (2022-07-07T16:52:50Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  We develop a variance reduction scheme for the two time-scale TDC algorithm in the off-policy setting. Experiments demonstrate that the proposed variance-reduced TDC achieves a smaller convergence error than both the conventional TDC and the variance-reduced TD.
  arXiv  Detail & Related papers  (2020-10-26T01:33:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.