On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing
Information TheoryData Structures and Algorithms
Summary
The authors studied a method called Binary Iterative Hard Thresholding (BIHT) that recovers sparse signals from just the signs of measurements. They proved the original BIHT algorithm converges efficiently in noiseless cases without needing each step to be normalized, matching previous results for normalized versions. However, when some sign measurements are corrupted, they found BIHT can still recover the signal but becomes unstable and the computations keep oscillating. This shows normalization is needed for guaranteed stable recovery under corrupted data. Their work solves a decade-old open problem about BIHT's convergence.
Authors
Arya Mazumdar, Prateeti Mukherjee
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.