{"id":"d9b97371-5ae1-4cd5-9dfb-42dc91e4d6f3","arxiv_id":"2607.15530","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Normalization-free BIHT is sample-optimal in the noiseless setting, but under any sign corruption its last-iterate provably oscillates forever.","lead":"This paper proves the original, normalization-free BIHT algorithm for 1-bit compressed sensing converges with the optimal O~(s/eps) measurement count, closing a decade-old open problem. Under adversarial sign flips, it shows the same algorithm reaches the optimal error floor early but never converges in the last iterate—oscillating forever unless normalized.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection to the noiseless theorem; the only soft spot is the unproven 'corrected' adversarial RAIC (Fact 2.7), which underpins the corruption results but not the central noiseless claim.","rationale":"The reader's weakest_assumption pointed to Fact 2.6 and Fact 2.7 collectively. I agree these are the only plausible weak points, but they are not on equal footing. Fact 2.6 is a published, unmodified theorem from [MM24a] and is the sole probabilistic input for the central noiseless claim (Theorem 4.1). There is no evidence it is false, and the deterministic argument in the paper is complete conditional on it. Fact 2.7, however, is explicitly modified in this paper ('sample complexity corrected via [MM24a]') and is not proved in the text; it underpins the corruption theorems, which are secondary to the main noiseless result. Since the concern is about an unproven modification rather than an identified error, and since the central claim does not rely on it, the reader's ACCEPT verdict should stand. A concrete verification of Fact 2.7 would remove this caveat, but its absence does not justify rejection or even a conditional verdict given the published status of the underlying facts and the internal consistency of the proofs.","tokens_in":22370,"tokens_out":11126,"duration_ms":107660,"concrete_test":"Obtain [MM24b] Theorem 3.1 and [MM24a] Fact 2.6. Re-derive Fact 2.7's stated sample complexity by following the covering/net argument with the adversarial corruption term, checking whether m ≳ (s/δ) log(en/s)√log(2e/δ) + (s/δ) log^{3/2}(2e/δ) + (1/δ) log(1/ρ)√log(2e/δ) suffices uniformly over all f ∈ F_A(τ) at δ = ε/(c2 L). Specifically, verify that the union bound over f and the handling of the τ-dependent terms produce no hidden factor in τ (such as (1−2τ)^{-2}) and no additional restrictions on τ beyond 0 ≤ τ ≤ 1. If the derivation requires extra assumptions or a worse m, Theorem 4.3's rate and Corollary 4.4's deterministic stopping rule need qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central noiseless theorem (Theorem 4.1) is internally consistent: the moving-reference decomposition, the radial-drift induction, and the constant choices in Appendix A.1 all check out. The proof depends on Fact 2.6 (RAIC), which is cited from the published JACM paper [MM24a]; this is a standard citation and not modified here. The genuine soft spot is Fact 2.7, which the paper itself flags as 'with the sample complexity corrected via [MM24a]' (Section 2.3). This is an unproven modification of a cited result, and Theorem 4.3 and Corollaries 4.4–4.5 rely on it. If the corrected sample complexity for adversarial RAIC is invalid, or if it requires extra restrictions (e.g., τ bounded away from 1/2), then the claimed matching Õ(s/ε) rate under sign corruptions would not follow from the cited papers. This does not affect Theorem 4.1, but it is the weakest load-bearing point in the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the original, normalization-free Binary Iterative Hard Thresholding (BIHT) algorithm for 1-bit compressed sensing. Its main contribution is a noiseless recovery theorem (Theorem 4.1) showing that with m = O~(s/eps) i.i.d. Gaussian measurements, T = O(log(1/eps)) iterations of BIHT — without any per-iterate normalization — yield an estimate whose ℓ2 directional error is at most eps, uniformly over all s-sparse unit targets, all sparse unit initializations, and all hard-thresholding tie-breaks. The proof introduces a 'moving reference' r(t)x* and a coupled induction controlling the directional error and the radial drift; the probabilistic input is a restricted approximate invertibility condition (RAIC, Fact 2.6) quoted from [MM24a]. Under adversarial sign corruptions, the paper proves a scalar lower bound (Theorem 4.2) showing that last-iterate convergence is impossible even for n=s=1 with any nonempty proper set of flipped signs, while a hitting-time guarantee (Theorem 4.3) asserts that an early normalized iterate reaches the same robust error floor as normalized BIHT. The corruption results rely on an 'adversarial RAIC' (Fact 2.7) whose sample complexity is stated as a corrected version of a result in [MM24b].","tokens_in":22746,"tokens_out":5788,"duration_ms":54353,"significance":"If the main noiseless theorem is correct, it closes a gap left open by [Jac+11] for over a decade and shows that per-iterate normalization is not needed for sample-optimal recovery in the noiseless regime. The moving-reference decomposition (Eq. (4)) is a genuine and elegant technical idea, and the proof of Theorem 4.1 appears internally consistent, with explicit constants in Appendix A.1. The scalar obstruction (Theorem 4.2) is sharp and conceptually important, establishing a clean separation between the normalized and unnormalized algorithms in a one-dimensional instance. The robustness results are significant if Fact 2.7 holds as stated. The paper also provides reproducible numerical experiments. However, the adversarial RAIC fact is a load-bearing import that is not proved in this manuscript, and its 'corrected' sample complexity is a nontrivial modification of a cited result; as a result, the corruption half of the paper is conditional on an unverified ingredient.","major_comments":[{"comment":"Fact 2.7 is stated with sample complexity identical to Fact 2.6 and is described as '[MM24b], with the sample complexity corrected via [MM24a]'. This is an unproven modification of a cited theorem, and Theorem 4.3 plus Corollaries 4.4–4.5 depend on it directly. The manuscript contains no proof of the corrected rate, and Appendix A.1 only asserts that constants dominate those in [MM24b]; it does not address the sample-dependence claim. Please either (i) prove Fact 2.7 in this paper, or (ii) cite the precise theorem in [MM24a] or [MM24b] that establishes the stated rate and verify that the hypotheses (including the range of tau and the uniformity over F_A(tau)) match. Without this, the corruption results are not established.","section":"§2.3, Fact 2.7"},{"comment":"The proof constructs a corruption function f defined by f(x*)=y and f(z)=sign(Az) otherwise, then applies Fact 2.7 uniformly over all f in F_A(tau). This is valid only if Fact 2.7 is actually true for the full class F_A(tau) at the stated sample complexity. If the corrected adversarial RAIC requires extra restrictions (for example tau bounded away from 1/2, or a different dependence on delta), the proof of the hitting-time guarantee, and hence the claimed matching O~(s/eps) rate under sign corruptions, would need to be revised. Please clarify the exact status of Fact 2.7 and its proof.","section":"§4.2.2, Theorem 4.3"},{"comment":"The noiseless proof is sound given Fact 2.6, but the choice of constants in Appendix A.1 introduces notational clutter: the proof of Theorem 4.3 uses 'c2 = c2_1' and later defines c1 = sqrt(c2), while the theorem statement presents c1 and c2 as independent absolute constants. The reader can verify the algebra, but the presentation should be cleaned up to avoid confusion about which constant is which.","section":"§4.1, Theorem 4.1"}],"minor_comments":[{"comment":"The typeset 'e𝑂(𝑠/𝜖)' appears to be a mangled tilde-O. Please correct the LaTeX to show the standard O-tilde notation.","section":"Abstract"},{"comment":"There are several typos in Section 2.1: 'The set 𝐽 usually often be selected' should read 'will usually be selected'; 'we use 𝒯𝑈 denotes coordinate restriction' is ungrammatical.","section":"§2.1"},{"comment":"The paragraph 'Per-iterate normalization escapes this instance' is a substantive result (the exponential concentration bound is used only there) but is typeset as an unnumbered continuation. Consider making it a numbered remark or a short subsection.","section":"§4.2.1"},{"comment":"The convention 'tau sqrt(log(2e/tau)) = 0 when tau=0' is stated, but the same convention should be stated explicitly in Fact 2.7 as well; currently it is only in the proof region.","section":"Theorem 4.3"},{"comment":"The constants in Fact 2.6 are reported as c1 ≈ 0.07125 and c2 ≈ 0.3349, but the reader may not have access to [MM24a] to verify these values. Please include a short derivation or a precise pointer to the lemma in [MM24a] where these values are defined.","section":"Appendix A.1"}],"recommendation":"major_revision","confidential_remarks":"The paper shares an author with the cited [MM24a] and [MM24b]. The noiseless theorem is an original contribution, but the 'corrected' adversarial RAIC (Fact 2.7) is a self-referential modification of a paper by the same group and is not proved here. I would encourage the editor to ask for independent verification of Fact 2.7 by the authors, or a qualified third party, before accepting the corruption results. If Fact 2.7 cannot be established, the paper could still be published with the noiseless theorem and the lower bound, but the robust positive claims would need to be downgraded to conditional statements."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this for Theorem 4.1. It settles the long-open BIHT convergence question: the original unnormalized algorithm, run for O(log(1/epsilon)) iterations, reaches directional error epsilon from O~(s/epsilon) Gaussian measurements, uniformly over targets, initializations, and tie-breaking choices. The key idea is to compare the dense update against r(t)x*, the target scaled by the current norm, rather than against x*. Then the radial mismatch becomes a product of two small quantities and gets absorbed into the contraction. I checked the induction and the constant ledger in A.1; it is sound. This is a genuine advance, not a restatement of the normalized analysis.\n\nThe corruption half is weaker. Theorem 4.3 and its corollaries rest on Fact 2.7, which is quoted with the phrase \"with the sample complexity corrected via [MM24a]\". That is a modified version of a cited result, it is not proved here, and it is load-bearing for the robustness claims. The stress-test note is right: if that adversarial RAIC is false or needs extra restrictions, those results fail. It does not touch Theorem 4.1, which uses only Fact 2.6 from the published JACM paper. The shared authorship of both facts is not itself a red flag, but the unproven correction is a real soft spot.\n\nOther limitations are smaller. Everything is Gaussian, and Section 5 says so honestly. The stopping certificate in Theorem 4.3 is tau-dependent, so the positive robust result is a hitting-time guarantee rather than a practical stopping rule unless an a priori tau_0 is known; the paper is transparent about that. The scalar lower bound is correct and decisive for fixed-step unnormalized BIHT, though it only concerns the fixed-step dynamics.\n\nMy recommendation: send this to peer review on the strength of Theorem 4.1. Ask the authors to prove or precisely state the adversarial RAIC they use, or to conditionalize the robustness claims on it. A good referee can verify the noiseless proof quickly and spend the rest of the effort on Fact 2.7.","headline":"The noiseless convergence theorem for BIHT is the real contribution and it is sound; the adversarial robustness claims depend on an unproven 'corrected' RAIC and should be reviewed with that in mind.","tokens_in":23156,"tokens_out":4922,"would_cite":true,"duration_ms":55082,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves the original BIHT algorithm, without per-iterate normalization, matches the optimal O~(s/ε) noiseless measurement rate, and that a single flipped sign forces its unnormalized iterates to oscillate forever—thereby pinpointin","keywords":["one-bit compressed sensing","binary iterative hard thresholding","sign measurements","sparse recovery","normalization","restricted approximate invertibility","adversarial sign flips","sample complexity"],"falsifier":"Simulate noiseless BIHT with i.i.d. Gaussian A at the prescribed m ≈ C s/ε for, say, s=5, n=2000, ε=0.01, over many trials; the proof predicts the first iterate has error ≤ 1/128 and the T-th iterate has directional error ≤ 0.01. If errors systematically exceed these bounds at the stated constant budget, the RAIC constants or the induction fail. For the lower bound, run the exact scalar recursion of Theorem 4.2 with Gaussian α, γ: the theorem says a nonzero fixed start never hits zero and changes sign infinitely often; observing a positive-probability hit of zero (or a finite stop in sign chan","tokens_in":22306,"feed_emoji":"📡","tokens_out":8975,"duration_ms":85606,"temperature":0.7,"pith_summary":"This paper closes a decade-plus gap in the theory of Binary Iterative Hard Thresholding (BIHT), the standard greedy baseline for recovering a sparse vector from one-bit sign measurements. It proves that the original algorithm, which never normalizes its intermediate iterates, converges to the true direction with the optimal O~(s/ε) Gaussian measurements—the same sample rate previously provable only for a variant that projects every iterate onto the unit sphere. The enabling move is a moving-reference analysis: each iterate is compared not to the fixed unit target but to the target scaled by the iterate's current norm, so the radial drift that normalization would remove becomes a harmless factor times the directional error. Under adversarial sign flips the paper proves a sharp separation: unnormalized BIHT reaches the robust error floor quickly but cannot settle—in dimension one, even one flipped sign among clean measurements makes the iterates change sign forever—whereas the normalized variant escapes. This settles when per-iterate normalization is algorithmically necessary: never for optimal noiseless recovery, always for any last-iterate guarantee under corruption.","feed_headline":"Original BIHT hits optimal 1-bit recovery with no normalization","feed_subtitle":"Classic BIHT matches optimal O~(s/ε) sample rate unnormalized; a single corrupted sign forces eternal oscillation.","key_machinery":"The key object is the moving-reference decomposition of the BIHT update. With z = r u, the population correction E[h_A(x*, z)] estimates x* − u, not x* − z; the paper rewrites the dense next iterate as r x* + (r−1)(u − x*), comparing against the target scaled by the current norm r x* rather than x*. This converts the radial drift that normalization would remove into a product |r−1| · ||u−x*||, which is harmless while the norm stays inside a constant window. The argument then invokes the restricted approximate invertibility condition (RAIC) on the unit pair (x*, u_t)—legitimate because sign measurements are norm-invariant—while hard-thresholding's two-approximate projection property and a rad","core_discovery":"The central discovery is two-sided. With m = O~(s/ε) i.i.d. Gaussian measurements, the original normalization-free BIHT algorithm, run for T = 1 + ceil(log2(1/(64ε))) iterations, returns an estimate with ℓ2 directional error at most ε for every s-sparse unit target, every sparse unit initialization, and every hard-thresholding tie-break, with probability at least 1−ρ over the matrix. This matches the optimal sample complexity previously known only for the normalized variant, so per-iterate normalization is unnecessary in the noiseless regime. Under sign corruptions the paper proves a sharp separation: if at most a τ fraction of signs are flipped, BIHT still reaches a robust error floor ε + c","pith_inferences":["The scalar oscillation argument is deterministic and generic: any fixed-step, unnormalized sign-mismatch recursion with asymmetric pushes will switch signs forever when a flipped bit biases each direction; this suggests the same phenomenon will appear in other non-normalized first-order methods for one-bit models, not just BIHT.","The moving-reference technique—keeping RAIC's domain (the sphere) intact and moving the comparison target instead—is transferable to other quantized or sign-based estimation problems where the likelihood is scale-invariant, such as dithered or multi-bit quantization schemes using projected-gradient steps.","A testable prediction: for sub-Gaussian or structured sensing matrices, the positive noiseless theorem may fail (the paper needs Gaussian angular geometry), but the oscillation lower bound survives because it is algebraic; so the normalization gap will widen for non-Gaussian designs.","The paper's 'never in the noiseless regime, always under corruption' phrasing suggests a threshold phenomenon: one could try to characterize how much corruption τ is needed to break last-iterate convergence as a function of step size and sparsity."],"forward_implications":["The 2011 BIHT algorithm as originally proposed is sample-optimal for noiseless one-bit recovery; practitioners can run it without per-iterate normalization and keep the same O~(s/ε) guarantee.","For any uniform last-iterate convergence under sign corruptions, per-iterate normalization is provably necessary; the fixed-step unnormalized dynamics forever oscillates past the correct direction.","With an a-priori corruption budget τ0, a deterministic stopping time T0 = 1 + ceil(log2(1/(64γ(ε,τ0)))) yields the robust error floor γ, and accuracy persists for a window of Ω(1/γ) further iterations.","The sample complexity under corruption matches that of the normalized surrogate: reaching the robust floor requires only O~(s/ε) Gaussian measurements, with the floor itself equal to the noiseless rate plus a √(ετ)+τ√log(1/τ) corruption penalty.","The separation is sharp: unnormalized BIHT fails last-iterate convergence even with a single flipped sign, isolating normalization as the mechanism that makes the trajectory stable."],"fun_headline_variants":["Unnormalized BIHT matches optimal 1-bit recovery in noiseless","Original BIHT: optimal sample complexity, no normalization needed","Minimal sign corruption forces BIHT to oscillate indefinitely","BIHT without normalization: optimal noiseless, unstable under corruption","No per-iteration normalization: BIHT still hits optimal rate"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire optimal-rate theory leans on two restricted-approximate-invertibility lemmas for Gaussian matrices imported from prior works by one of the authors; if either lemma is false or has worse sample dependence than O~(s/ε), both the noiseless convergence theorem and the corruption floor collapse.","fun_headline_variants_meta":{"raw":{"variants":["Unnormalized BIHT matches optimal 1-bit recovery in noiseless","Original BIHT: optimal sample complexity, no normalization needed","Minimal sign corruption forces BIHT to oscillate indefinitely","BIHT without normalization: optimal noiseless, unstable under corruption","No per-iteration normalization: BIHT still hits optimal rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001755,"raw_usage":{"total_tokens":6834,"prompt_tokens":882,"completion_tokens":5952,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":5864}},"tokens_in":626,"tokens_out":5952,"duration_ms":43196,"temperature":1.0,"reasoning_tokens":5864,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T23:03:21.103580+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate noiseless BIHT with i.i.d. Gaussian A at the prescribed m ≈ C s/ε for, say, s=5, n=2000, ε=0.01, over many trials; the proof predicts the first iterate has error ≤ 1/128 and the T-th iterate has directional error ≤ 0.01. If errors systematically exceed these bounds at the stated constant budget, the RAIC constants or the induction fail. For the lower bound, run the exact scalar recursion of Theorem 4.2 with Gaussian α, γ: the theorem says a nonzero fixed start never hits zero and changes sign infinitely often; observing a positive-probability hit of zero (or a finite stop in sign chan","supporting_citations":[],"review_version":1}