Binary Iterative Hard Thresholding (BIHT) is a simple greedy algorithm for recovering sparse signals from one-bit sign measurements. Since its introduction in 2013, a convergence proof for the original version has been missing; later analyses focused on a normalized variant that projects each iterate onto the unit sphere.

Mazumdar and Mukherjee now prove that the original BIHT converges in the noiseless case. With O~(s/epsilon) measurements, a deterministic finite-time iterate achieves directional error at most epsilon for every s-sparse unit vector, matching the sample complexity of the normalized variant.

Under adversarial sign flips, the picture changes. The authors show that BIHT without normalization still reaches the robust error floor early on, but the iterates are not stable: even a single flipped sign combined with one clean sign can force indefinite oscillation. The normalized variant provably escapes this failure, so no general last-iterate convergence theorem can hold for the original algorithm under sign corruptions.

The paper thus characterizes exactly when per-iteration normalization is algorithmically necessary, closing a gap that has been open for over a decade. It is scheduled to appear at SODA 2027.