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

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 Jacques, Laska, Boufounos, and Baraniuk [IEEE Trans. Inform. Theory (2013)] 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-iterate normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with Õ(s/ε) measurements, a deterministic, computable 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. 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 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.

Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization
Xiaoxin Huang, Masayuki Ohzeki
arXiv15 Sep 2026PreprintarXiv licenceFull textGeneral mathematics Quantum physics & quantum informationarXiv
Superfast Spectral Compressed Sensing with Quadratic Convergence
Xunmeng Wu, Jian-Feng Cai, Zongben Xu +1
arXiv15 Oct 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing
Jing Ma, Yujia Wu, Zhaoqiang Liu
arXiv12 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
Compressed Sensing with Quantized Tensor Trains (QTTs)
Jingchun Shao
arXiv29 Sep 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
Xunmeng Wu, Jian-Feng Cai, Zongben Xu +1
arXiv13 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{mazumdar2026role,
  title = {{On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing}},
  author = {Arya Mazumdar and Prateeti Mukherjee},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.15530},
  eprint = {2607.15530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.15530},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing
AU  - Arya Mazumdar
AU  - Prateeti Mukherjee
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2607.15530
UR  - https://arxiv.org/abs/2607.15530
AB  - 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 Jacques, Laska, Boufounos, and Baraniuk [IEEE Trans. Inform. Theory (2013)] 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-iterate normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with Õ(s/ε) measurements, a deterministic, computable 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. 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 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.
ER  -

Abstract

Related

Cite