📊 statistics

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

This paper resolves a decade-old open problem by proving that the original, unnormalized Binary Iterative Hard Thresholding (BIHT) algorithm achieves optimal convergence in noiseless 1-bit compressed sensing, while demonstrating that per-iteration normalization becomes algorithmically necessary to ensure stable last-iterate convergence when sign corruptions are present.

Original authors: Arya Mazumdar, Prateeti Mukherjee

Published 2026-07-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Arya Mazumdar, Prateeti Mukherjee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy room, but you are only allowed to whisper a single word: "Yes" or "No." You can't say how loud the message is, or how long it is, or even what the tone was. You can only say if the sound was positive or negative. This is the world of one-bit compressed sensing. In this high-tech game, scientists try to reconstruct a complex, hidden picture (like a face or a medical scan) using only a massive list of "Yes/No" answers. It's like trying to guess the shape of a sculpture by only feeling whether a stick poking it is pointing left or right, thousands of times.

The challenge is that these "Yes/No" clues are often messy. Sometimes the wind blows, or someone sneezes, and a "Yes" gets flipped to a "No." To fix this, researchers use a clever detective tool called Binary Iterative Hard Thresholding (BIHT). Think of BIHT as a hiker trying to find a hidden treasure (the true signal) in a foggy forest. The hiker takes a step based on the compass (the data), checks if they are on the right path, and then "snaps" their position to the nearest known trail (a process called thresholding). For years, there was a debate among the hikers: should they stop after every step to check their height and force themselves to stand exactly on a specific altitude line (normalization), or should they just keep walking naturally, letting their height vary?

This paper, written by Arya Mazumdar and Prateeti Mukherjee, settles that decade-old argument with a definitive map. They prove that in a perfect, quiet forest (no noise), the hiker does not need to stop and check their height. They can just keep walking, and they will find the treasure just as fast and accurately as if they had been checking their altitude every single time. However, the story changes when the forest gets stormy (when the "Yes/No" clues are corrupted). In the storm, the hiker who refuses to check their height will eventually start walking in circles, flipping back and forth forever, never quite settling on the treasure. The paper proves that in this noisy scenario, the "check your height" step is absolutely necessary to stop the hiker from getting lost in an endless loop.

The Big Discovery: When to Check Your Altitude

The authors tackled a question that had been hanging over the field of one-bit compressed sensing for more than ten years. The original algorithm, proposed in 2011, was simple and effective but lacked a mathematical proof that it would always work. Later, researchers found that if you added a "normalization" step—forcing the algorithm to reset its "size" to exactly 1 after every move—it was easier to prove that the method worked. But was that extra step actually needed? Or was it just a safety blanket that made the math easier but slowed down the process?

The paper answers this with a clear "it depends on the weather."

In the Perfect World (Noiseless Setting)
If the "Yes/No" clues are perfect and no signs have been flipped by mistake, the authors prove that the original, "un-normalized" version of BIHT is just as good as the fancy, normalized version. They show that with a specific number of measurements (roughly proportional to the complexity of the signal divided by the desired accuracy), the algorithm will converge to the correct answer. It finds the treasure in a finite number of steps, and it does so without ever needing to stop and force its size to be exactly 1. In fact, the paper proves that the algorithm naturally stays close enough to the right size on its own. This is a big deal because it means the simpler, faster version of the algorithm is mathematically sound and doesn't need the extra computational step of normalization to be optimal.

In the Stormy World (Sign Corruptions)
However, the story takes a twist when the data is corrupted. Imagine that a mischievous wind flips a few of the "Yes" signs to "No" and vice versa. The authors prove that if you use the original, un-normalized algorithm in this scenario, it hits a wall. Specifically, they construct a simple, one-dimensional example (a tiny, simple version of the problem) where the algorithm gets stuck in an infinite loop.

Here is how the trap works: If the algorithm is slightly off, the corrupted clues push it in one direction. If it crosses the center line, the clues push it back the other way. Without the "normalization" step to reset its position, the algorithm's "size" drifts. It gets pushed across the zero line, then pushed back, then across again, forever. The authors prove that for this specific type of corruption, the algorithm's direction will flip back and forth infinitely often, meaning it never settles on the correct answer. The "last step" of the algorithm is useless because it keeps oscillating.

The Silver Lining: Hitting the Floor Early
Does this mean the un-normalized algorithm is useless in the storm? Not quite. The authors show that while the algorithm eventually starts oscillating, it doesn't start immediately. It actually reaches a "robust error floor"—a point where it is very close to the treasure—very quickly. They prove that if you stop the algorithm at just the right time (a "hitting time"), you can get a result that is just as accurate as the normalized version. The catch is that you need to know roughly how bad the storm is (the corruption level) to know exactly when to stop. If you don't know the storm's intensity, you might stop too early or too late. But if you have a rough estimate, you can run the simple algorithm, stop it at a specific moment, and get a great result.

Why This Matters

This paper is a masterclass in understanding the limits of simple tools. It tells us that we don't always need to over-engineer our solutions. In a clean environment, the simplest path is often the best one, and adding extra constraints (like normalization) is unnecessary. But in a messy, unpredictable world, those extra constraints become vital safety rails to keep us from spinning in circles.

The authors didn't just guess this; they proved it with rigorous mathematics. They showed that the "un-normalized" algorithm is a winner in perfect conditions but a loser in the long run if the data is corrupted. Conversely, the "normalized" algorithm is a reliable survivor in both worlds. This distinction helps engineers and scientists decide when to use the faster, simpler method and when they absolutely must use the more robust, normalized version to ensure their data recovery doesn't fail. It turns a decade of uncertainty into a clear set of rules for navigating the foggy forest of one-bit data.

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

Problem Statement

The paper addresses the problem of 1-bit compressed sensing, where a high-dimensional sparse signal $x^\star \in \mathbb{R}^n$ (specifically, an $s$ -sparse unit vector) is recovered from $m$ linear measurements that are quantized to their signs: $y = \text{sign}(Ax^\star) \in \{\pm 1\}^m$ . The objective is to estimate the direction of $x^\star$ within an $\ell_2$ error of $\epsilon$ using as few measurements as possible.

The focus is on Binary Iterative Hard Thresholding (BIHT), a greedy algorithm proposed by Jacques et al. [Jac+11]. The original BIHT algorithm performs a gradient-descent-like step based on sign mismatches, followed by hard thresholding to enforce sparsity. Crucially, the original formulation applies normalization only to the final output, not to intermediate iterates. While a normalized variant (which projects every iterate onto the unit sphere) has been shown to converge with optimal sample complexity, the convergence of the original, unnormalized BIHT remained an open problem for over a decade.

Methodology and Technical Approach

The authors resolve the open convergence question for the original BIHT by developing a novel geometric analysis that avoids the need for per-iterate normalization.

1. Moving Reference Frame and Population Geometry

The core technical insight is a shift in the reference frame for error analysis. Previous analyses of normalized BIHT relied on the Restricted Approximate Invertibility Condition (RAIC), which guarantees that the empirical sign correction approximates the true direction difference for unit vectors. The authors argue that extending RAIC to non-unit vectors is impossible because sign measurements are invariant to positive scaling; thus, the measurements contain no information about the signal's magnitude.

Instead of forcing iterates to the unit sphere, the authors analyze the algorithm relative to a moving reference $r^{(t)}x^\star$ , where $r^{(t)} = \|x^{(t)}\|_2$ is the norm of the current iterate.

Population Dynamics: In the population limit (infinite measurements), the update for a non-unit vector $z = ru$ (where $u$ is the direction) is shown to be $z + \mathbb{E}[\text{correction}] = r x^\star + (r-1)(u - x^\star)$ .
Error Decomposition: The error is decomposed into a directional component ( $u - x^\star$ ) and a radial component ( $(r-1)(u - x^\star)$ ). The authors prove that as long as the norm $r^{(t)}$ remains within a constant window around 1, the radial error is controlled by the directional error.
Inductive Coupling: The proof employs a coupled induction showing that the directional error contracts geometrically while the norm drifts by at most the magnitude of the one-step error. This ensures the iterates stay within a "basin" where the analysis holds, without requiring explicit projection.

2. Finite-Sample Analysis via RAIC

To transition from population dynamics to finite samples, the authors utilize the RAIC for Gaussian matrices. They demonstrate that the empirical correction term behaves like its expectation uniformly over sparse directions. By restricting the analysis to the support of the current iterate and the target, they apply RAIC to the pair of unit vectors $(x^\star, u^{(t)})$ , effectively absorbing the norm into the comparison point rather than the probabilistic bound.

3. Adversarial Corruption Analysis

For the setting with adversarial sign corruptions (where up to a $\tau$ fraction of signs are flipped), the authors employ a scalar lower-bound construction ( $n=s=1$ ) to demonstrate that the unnormalized trajectory cannot converge to a fixed point. Instead, it oscillates indefinitely. However, they prove that the trajectory still reaches a robust error floor at an early "hitting time" before the oscillations dominate.

Key Results

1. Noiseless Convergence (Theorem 1.1 / 4.1)

The paper proves a universal, sample-optimal convergence theorem for the original, unnormalized BIHT in the noiseless setting.

Sample Complexity: With $m = \tilde{O}(s/\epsilon)$ Gaussian measurements, the algorithm converges to an $\epsilon$ -accurate estimate.
Convergence: The directional error $\| \frac{x^{(T)}}{\|x^{(T)}\|} - x^\star \|_2 \le \epsilon$ is achieved in $T = O(\log(1/\epsilon))$ iterations.
Significance: This matches the optimal sample dependence of the normalized variant. It establishes that per-iterate normalization is algorithmically unnecessary for optimal recovery in the noiseless regime.

2. Impossibility of Last-Iterate Convergence under Corruption (Theorem 1.2 / 4.2)

Under adversarial sign corruptions, the authors prove a sharp separation between normalized and unnormalized BIHT regarding last-iterate convergence.

Oscillation: Even with a single flipped sign, the unnormalized iterates change sign infinitely often. The directional error returns to its maximum value ( $\approx 2$ ) infinitely often.
Contrast: The normalized variant avoids this oscillation and converges to the correct sign with high probability.
Conclusion: No general last-iterate convergence theorem can hold for unnormalized BIHT under corruptions.

3. Early Hitting-Time Guarantee (Theorem 1.3 / 4.3)

Despite the lack of last-iterate convergence, the unnormalized BIHT achieves the optimal robust error floor at an early iterate.

Robust Error Floor: The algorithm reaches an error of $\gamma(\epsilon, \tau) \approx \epsilon + \sqrt{\epsilon\tau} + \tau\sqrt{\log(1/\tau)}$ within $O(\log(1/\gamma))$ iterations.
Stability: If an upper bound on the corruption rate $\tau_0$ is known, the algorithm can be stopped at a deterministic time $T_0$ to guarantee this accuracy. Furthermore, the solution remains stable within this error bound for a window of $\Omega(1/\gamma)$ subsequent iterations.

Significance and Claims

The paper claims to resolve a decade-old open problem regarding the convergence of the original BIHT algorithm. Its primary contributions are:

Necessity of Normalization: It characterizes exactly when normalization is necessary. The authors conclude that in the noiseless regime, normalization is never necessary for optimal recovery. However, in the presence of corruptions, normalization is necessary to prevent indefinite oscillation and ensure last-iterate convergence.
Theoretical Justification for Empirical Observations: The results explain empirical phenomena observed in prior work (e.g., [MM25]), where unnormalized BIHT error curves drop to a robust floor and then oscillate. The theory provides the mathematical basis for both the initial drop (Theorem 4.3) and the subsequent oscillation (Theorem 4.2).
Optimality: The paper establishes that the simple, unnormalized BIHT is sample-optimal ( $\tilde{O}(s/\epsilon)$ ) for noiseless recovery, removing the need for the more complex normalized variant in that setting.

The authors maintain a modest stance, noting that their analysis relies heavily on the Gaussian measurement model and the specific geometry of sign measurements. They acknowledge that extending these guarantees to sub-Gaussian ensembles or other structured matrices remains an open direction for future work.