BIHT Algorithm's Normalization Debate Settled with Optimal Convergence Proof

A decade-old convergence problem in the Binary Iterative Hard Thresholding (BIHT) algorithm has finally been resolved by researchers Arya Mazumdar and Prateeti Mukherjee. Their paper, "On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing," addresses a gap left open since the algorithm's introduction in 2011. BIHT is a greedy method used to recover sparse vectors from one-bit sign measurements, with applications in signal processing and machine learning. The original algorithm performed a gradient-descent step followed by hard thresholding, but its convergence analysis remained unresolved, leading subsequent work to study a normalized variant that projects each iterate onto the unit sphere. The new paper characterizes when this per-iteration normalization is algorithmically necessary.

In the noiseless setting, the authors prove a universal, sample-optimal convergence theorem for the original BIHT. Specifically, with Õ(s/ε) measurements, a deterministic finite-time iterate achieves directional error at most ε, simultaneously for every s-sparse unit vector—matching the optimal sample complexity of the normalized version. This shows that per-iterate normalization is unnecessary for optimal recovery without noise. However, under sign corruptions, a sharp separation emerges. If at most a τ fraction of signs are adversarially flipped, BIHT without normalization reaches a robust error floor with the same sample complexity, but the iterates oscillate indefinitely. The authors prove a scalar lower bound showing that even a single flipped sign forces oscillation, preventing any general last-iterate convergence theorem. In contrast, the normalized variant provably escapes this behavior, establishing when normalization is essential.