{"id":"1c485419-d1a7-47d3-94f7-002204a0602b","arxiv_id":"1908.06359","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"Two greedy hybrid compressed sensing algorithms are proposed, but their stated success-probability theorems assume an n-th order restricted isometry property that cannot hold when the number of measurements is less than the signal dimension.","lead":"This paper proposes two greedy algorithms that mix traditional and one-bit compressed sensing measurements, using binary measurements to detect signal support and linear measurements to refine estimates. The algorithms beat standard greedy methods in simulations, but the theoretical guarantees rely on an impossible assumption about the measurement matrix.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 5 and 6 assume RIP of order n for an m_r×n matrix with m_r<n, an impossible condition; the main theoretical guarantees are vacuous in the paper's own measurement regime.","rationale":"The reader's weakest assumption identifies exactly the load-bearing failure: Theorems 5 and 6 condition on δ_n∈(0,0.5] for an m_r×n matrix with m_r<n in the intended regime. Since RIP of order n is impossible for a fat matrix, the theorems are vacuously true but provide no guarantee for the algorithms whose empirical behavior is the paper's claim. This is not a stylistic or incremental issue; it directly undermines the abstract's assertion that each proposed algorithm is backed by a theorem with proof analyzing its capabilities. The simulation results in Sec. V remain suggestive but cannot repair a vacuous theoretical statement, and the paper does not provide any alternative analysis of the algorithms' success conditions. The concrete test is a one-line rank argument plus a nullspace computation; it will definitively confirm the impossibility. Because this is the same concern the reader raised and it supports the REJECT verdict, no change to the reader's verdict is needed.","tokens_in":23616,"tokens_out":7710,"duration_ms":70636,"concrete_test":"Analytical verification: fix the Sec. V-A setup with n=256, s=4, so m_r=6. Draw A_r∈R^{6×256} with iid standard normal entries and compute a nonzero vector z with A_r z=0, e.g., via the nullspace of A_r. Then ||A_r z||_2=0, while the RIP-of-order-n lower bound would require (1-δ_n)||z||_2^2≤0; hence any valid δ_n satisfies δ_n≥1. Repeating this for every Monte-Carlo trial in Fig. 1 would confirm no trial satisfies the hypothesis δ_n∈(0,0.5] of Theorems 5 and 6. Alternatively, rerun the theorem under RIP of order 2s and check whether the proofs of Appendix B/C can be completed without the order-n RIP step at Eq. (49).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 5 (Sec. IV-A) and 6 (Sec. IV-B) both assume that the linear measurement matrix A_r satisfies the restricted isometry property of order n with constant δ_n in (0,0.5]. RIP of order n requires (1-δ_n)||z||_2^2 ≤ ||A_r z||_2^2 for every z∈R^n. In the hybrid-CS regime of the paper, A_r is m_r×n with m_r<n: e.g., Sec. V-A sets n=256 and m_r=⌈1.5s⌉, so m_r≤48 for s≤32, and for s=4, m_r=6. Every such matrix has a nontrivial nullspace by rank-nullity. For any nonzero z in that nullspace, the lower RIP bound demands (1-δ_n)||z||_2^2 ≤ 0, forcing δ_n≥1, which contradicts δ_n∈(0,0.5]. The assumption is therefore unsatisfiable whenever m_r<n, which is exactly the setting used in the simulations and the motivating compressed-measurement regime. Consequently, Theorems 5 and 6 have empty hypotheses in the regime of interest: the probability lower bounds do not apply to the algorithms as implemented. This is an internal inconsistency between the theorem statement and the measurement budget, not a disagreement with prior consensus, and it removes the paper's central theoretical support for the two greedy algorithms.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies hybrid compressed sensing, in which measurements consist of noisy linear measurements y_r = A_r x + e_r and noisy binary measurements y_o = sign(A_o x + e_o). The authors first prove a theorem on random uniform tessellations for sparse signals (Theorem 4), and then propose two greedy algorithms that use the one-bit measurements for support detection and the linear measurements for residue updates and signal estimates. The main advertised theoretical results are Theorem 5, a lower bound on the probability that Algorithm 1 detects the true support after s iterations, and Theorem 6, a lower bound on the probability that Algorithm 2 turns an initial support into the true support. Simulations compare the two algorithms with OMP, SP, and CoSaMP under equal bit budgets for n=256 and several sparsity levels.","tokens_in":24053,"tokens_out":10044,"duration_ms":97399,"significance":"Hybrid compressed sensing is a relevant and under-studied problem, and the proposed algorithms are clearly specified and intuitively motivated. The simulation study covers a reasonable range of parameters and shows consistent gains over the selected classical greedy algorithms, which is an encouraging empirical result. The paper is also clearly written and does not rely on circular reasoning or fitted parameters in its theoretical statements. However, the central theoretical contribution is invalid: both algorithm theorems are conditioned on an impossible restricted-isometry assumption, and the proofs contain additional algebraic steps that fail within the range of the stated parameters. If the theorems were corrected, the paper could make a useful contribution; as it stands, the claimed guarantees are vacuous in the paper's own measurement regime.","major_comments":[{"comment":"The assumption that A_r ∈ R^{m_r × n} satisfies the restricted isometry property of order n with δ_n ∈ (0, 0.5] is impossible whenever m_r < n, which is exactly the regime considered in this paper. For example, Section V-A sets n = 256 and m_r = ⌈1.5s⌉, so m_r = 6 for s = 4. By the rank-nullity theorem, every such A_r has a nonzero vector z in its nullspace; the RIP lower bound of order n would require (1 - δ_n)||z||_2^2 ≤ ||A_r z||_2^2 = 0, forcing δ_n ≥ 1. This contradicts δ_n < 1 and therefore the hypotheses of Theorems 5 and 6 are empty. Consequently, the probability lower bounds (25) and (26) do not apply to the algorithms as implemented in the simulations, and the principal theoretical claims of the paper are vacuous.","section":"Section IV-A, Theorem 5; Section IV-B, Theorem 6"},{"comment":"Even if one disregarded the impossible RIP order-n assumption, the proof of Theorem 5 contains a false inequality. The step (1 + sqrt((1 + δ_n)/(1 - δ_j))) ≤ 1 + sqrt(2) is asserted in the derivation of Eq. (51). Since Lemma 1 gives δ_j ≤ δ_n, the ratio (1 + δ_n)/(1 - δ_j) can be as large as (1 + δ_n)/(1 - δ_n), which equals 3 when δ_n = 0.5; hence sqrt(3) > sqrt(2) and the displayed bound fails for parameters allowed by the theorem. Similarly, the inference from the bound on ||e_r||_2 to the bound on ||u||_2 in Eq. (50) requires δ_n ≤ 1 - (1 + sqrt(2))/(2 + sqrt(2)) ≈ 0.293, which is not implied by δ_n ∈ (0, 0.5]. Theorem 6 uses the same argument through Eq. (60), so both probability bounds are demonstrably incorrect even under a hypothetical valid RIP assumption.","section":"Appendix B, around Eq. (51); Appendix C, Eq. (60)"}],"minor_comments":[{"comment":"The initial detected support set is written as \\tilde{Ω}_0 = {i_{s'+1}, i_{s'+2}, ..., i_{s'}}; the last index should be i_s, not i_{s'}. The proof in Appendix C correctly uses the index set {s'+1, ..., s}.","section":"Theorem 6 statement"},{"comment":"The legends in Figures 1 and 2 contain the typographical errors 'Algotithm 1' and 'Algotithm 2'; these should read 'Algorithm 1' and 'Algorithm 2'.","section":"Figures 1 and 2"},{"comment":"The simulation section does not report how the free threshold parameters c_j, n_j for Algorithm 1 and \\hat{n}_j, \\tilde{n}_j for Algorithm 2 are chosen; without this information, the reader cannot tell whether the simulation configuration is compatible with the conditions in Theorems 5 and 6, even setting aside the vacuous RIP assumption.","section":"Section V-A and V-B"},{"comment":"Definition 2 contains a typo: 'F or' should be 'For' at the beginning of the definition.","section":"Definition 2"}],"recommendation":"reject","confidential_remarks":"The manuscript would need a fundamentally different theoretical analysis to support its main claims; the unsatifiable RIP order-n assumption is not a local fix, because the proofs rely on cross-term bounds involving the full n×n Gram structure. The empirical results are interesting, but they do not compensate for the vacuous theoretical guarantees in a paper whose abstract and contributions emphasize the provided theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper has a plausible empirical idea, but its central theoretical guarantees—Theorems 5 and 6—rest on an assumption no matrix can satisfy. The assumption that A_r (an m_r×n matrix with m_r < n) satisfies RIP of order n with δ_n ∈ (0, 0.5] is impossible: any nonzero vector in the nullspace violates the lower bound and forces δ_n ≥ 1. The authors' own experiments set m_r = ⌈1.5s⌉ with n = 256, so m_r < n exactly; the theorems have empty hypotheses in the regime they actually test. The proof then compounds this with the inequality (1+δ_n)/(1−δ_j) ≤ 2, which fails for δ_n = δ_j = 0.5 (it gives 3). So the support-detection and support-modification results are vacuous as stated.\n\nThe paper does have real content. The greedy design—one-bit measurements for support detection and linear residuals for amplitude update—is new in the hybrid-CS literature; the only prior hybrid work the authors cite, [46], uses an optimization approach. The simulations show consistent gains over OMP, SP, and CoSaMP under a fixed bit budget, though without error bars the comparison is suggestive rather than conclusive. Theorem 4 on random uniform tessellations for sparse signals is a genuine extension of Plan–Vershynin, and the proof sketch, using the ℓ1-quotient property and mean-width bounds, is coherent as far as I can tell.\n\nThe soft spots beyond the RIP issue: the thresholds c_j, n_j, etc. are free parameters in the theorems and are not specified algorithmically, so the bounds are not directly actionable; and the empirical study covers only two configurations and does not report variance. Minor, relative to the load-bearing flaw.\n\nWho this is for: readers working on one-bit or hybrid CS will find the algorithm design and the empirical comparison worth a look, and Theorem 4 is a nice standalone result. But the manuscript as it stands needs a serious rework of the theoretical analysis—either replace the order-n RIP with conditions that actually hold for underdetermined matrices, or reframe the contribution as primarily empirical. I would still send it to peer review, because the errors are specific and fixable in principle, and the algorithmic idea deserves referee time. A serious editor could send it to reviewers with a request to examine exactly this RIP assumption, rather than desk-reject on novelty.","headline":"The hybrid-CS algorithms and Theorem 4 are worth a look, but the main theory is vacuous: an m_r×n matrix with m_r<n cannot satisfy RIP of order n, so Theorems 5–6 do not apply to the paper's own experiments.","tokens_in":24469,"tokens_out":5733,"would_cite":false,"duration_ms":53001,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","94A20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes two greedy algorithms for hybrid compressed sensing—one-bit measurements for support detection, analog measurements for residue updates—and proves success-probability bounds for both.","keywords":["hybrid compressed sensing","one-bit compressed sensing","greedy algorithms","support detection","random uniform tessellations","restricted isometry property","sparse recovery","bit budget"],"falsifier":"Take any $m_r \\times n$ measurement matrix $A_r$ with $m_r < n$, for instance the paper's simulation choice $m_r = 6$, $n = 256$. Pick a nonzero vector $v$ with $A_r v = 0$; then $\\lVert A_r v \\rVert_2 = 0$ while $\\lVert v \\rVert_2 > 0$, so the restricted-isometry inequality $(1-\\delta_n)\\lVert v \\rVert_2^2 \\le \\lVert A_r v \\rVert_2^2$ forces $\\delta_n \\ge 1$. Since the theorems assume $\\delta_n \\in (0, 0.5]$, their probability bounds cannot apply to any matrix of the intended size.","tokens_in":23433,"feed_emoji":"📶","tokens_out":11540,"duration_ms":101447,"temperature":0.7,"pith_summary":"The paper is trying to establish that hybrid compressed sensing—collecting a small number of ordinary linear measurements alongside a larger number of one-bit sign measurements—can be decoded by greedy algorithms. Its first algorithm detects the support of a sparse signal by repeatedly testing candidate supports against the one-bit inequalities, then updating the residue with a least-squares projection from the linear measurements. Its second algorithm takes an initial support guess and greedily swaps one index at a time until the guess stops changing. For both algorithms the paper proves lower bounds on the probability of success, and for one-bit measurements it proves an error bound based on random uniform tessellations. The practical point is that one-bit measurements are cheap in storage and robust to noise, while linear measurements carry the scale information that one-bit measurements discard; if the claims hold, hybrid CS gives a bit-efficient recovery route when signal energy is unknown.","feed_headline":"One-bit measurements can steer greedy sparse recovery","feed_subtitle":"Hybrid CS with analog residue updates matches or beats classic greedy methods at equal bit budgets.","key_machinery":"The load-bearing object is the hybrid measurement pair $y_r = A_r\\tilde{x}$ and $y_o = \\operatorname{sign}(A_o\\tilde{x})$ with $\\tilde{x}=x+u$, together with a greedy selection rule. For a candidate support set $S$, the algorithms form the least-squares estimate $\\tau_n(A_{rS}^{\\dagger} y_r, S)$ and count how many of the one-bit inequalities $[y_o]_i \\langle a_{o,i}, \\hat{x}\\rangle \\ge 0$ it satisfies; the candidate with the largest count wins. Algorithm 1 then removes the contribution of the selected support from the linear measurements via the residue update $r_j = y_r - A_{r\\Omega_j} A_{r\\Omega_j}^{\\dagger} y_r$, while Algorithm 2 repeatedly adds the best new index and prunes the worst current one. The theoretical bridge is the random-uniform-tessellation bound, restated for sparse signals in Theorem 4, which links normalized recovery error to the fraction of separating hyperplanes; the probability theorems then convert the sign-change probability for a single Gaussian hyperplane into binomial success counts.","core_discovery":"On the paper's own terms, the central claim is that support information can be extracted from binary measurements by a greedy counting rule, provided the candidate estimates are formed from the traditional linear measurements, and that a second greedy pass can repair a wrong initial support. Theorem 4 says that for sparse signals the normalized recovery error is bounded by $\\delta + d_{A_o}(\\tilde{x}, \\hat{x})$, where $d_{A_o}$ is the fraction of one-bit hyperplanes separating the noisy signal from the estimate. Theorem 5 gives a lower bound on the probability that Algorithm 1 detects the true support after $s$ iterations, and Theorem 6 gives a lower bound on the probability that Algorithm 2 turns the initial support into the true support. The simulation section reports that both algorithms outperform three classic greedy algorithms for traditional compressed sensing under the same bit budget in noisy experiments.","pith_inferences":["A natural repair, not explored in the paper, would replace the order-$n$ restricted isometry assumption with an order-$2s$ or coherence condition; whether the same proof skeleton then yields non-vacuous probability bounds is left open.","The success bounds in Theorems 5 and 6 depend on per-iteration thresholds and reference values that the paper does not specify, so choosing those parameters is an empirical degree of freedom that could change which algorithm wins.","The same greedy binary-inequality scoring could be applied to multi-bit or dithered quantized measurements and to block-sparse signals, since only the sign agreement between measurement and estimate is used in the selection rule."],"forward_implications":["At a fixed storage budget, moving some budget from high-precision linear measurements to one-bit measurements can preserve or improve recovery accuracy; the simulations show the hybrid algorithms at 64s bits at least matching the classic greedy methods.","Support detection can proceed without prior knowledge of signal energy: one-bit measurements decide direction, while linear measurements provide scale and the residue for the next iteration.","The support-modification pass of Algorithm 2 means hybrid CS can be initialized from any rough support guess and then refined, so it can be chained after another detector.","The random-tessellation error bound implies that the one-bit reconstruction error shrinks as the estimate satisfies more binary inequalities, which is exactly the score each greedy step maximizes."],"supporting_citations":[{"why":"Justifies the design choice that one-bit measurements are optimal for direction estimation under a fixed bit budget, motivating binary-inequality support detection.","marker":"[10]"},{"why":"Orthogonal matching pursuit is a baseline in the simulation comparison and a representative greedy algorithm for traditional CS.","marker":"[20]"},{"why":"CoSaMP is a baseline in the simulation comparison.","marker":"[24]"},{"why":"Provides the Gaussian mean width bound $w^2(\\Sigma'_{n,s}) \\le C s \\log(n/s)$ used to set measurement counts in Theorem 4.","marker":"[36]"},{"why":"Yields the simultaneous $(\\ell_2,\\ell_1)$-quotient property that bounds the noise vector in the proof of Theorem 4.","marker":"[41]"},{"why":"Provides the cumulative binomial distribution expression used in the success-probability formulas of Theorems 5 and 6.","marker":"[47]"},{"why":"Defines the restricted isometry property and its monotonicity lemma, which the proofs of Theorems 5 and 6 rely on.","marker":"[48]"},{"why":"Supplies the cross-column inner-product bound (Lemma 3) used to control the distance between the signal and support-restricted estimates.","marker":"[49]"},{"why":"Gives the probability that a random hyperplane separates two vectors as $\\theta(x,y)/\\pi$, the basis for the binomial success counts.","marker":"[51]"},{"why":"Supplies Theorem 3, the random-uniform-tessellation error bound that Theorem 4 extends to sparse signals and one-bit measurements.","marker":"[52]"}],"fun_headline_variants":["Greedy hybrid CS splits support and residue","One bit for support, analog for residue","Hybrid CS greedy: one-bit detect, analog refine","Bit-saving greedy rules for hybrid CS","Greedy one-bit support, then analog update"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main theorems assume the small linear measurement matrix preserves distances for every vector in the full $n$-dimensional space, but a matrix with more columns than rows always sends some nonzero vector to zero, so the assumption cannot hold in the regime the algorithms are designed for.","fun_headline_variants_meta":{"raw":{"variants":["Greedy hybrid CS splits support and residue","One bit for support, analog for residue","Hybrid CS greedy: one-bit detect, analog refine","Bit-saving greedy rules for hybrid CS","Greedy one-bit support, then analog update"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000975,"raw_usage":{"total_tokens":4150,"prompt_tokens":959,"completion_tokens":3191,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":3120}},"tokens_in":575,"tokens_out":3191,"duration_ms":22615,"temperature":1.0,"reasoning_tokens":3120,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:48:24.958983+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any $m_r \\times n$ measurement matrix $A_r$ with $m_r < n$, for instance the paper's simulation choice $m_r = 6$, $n = 256$. Pick a nonzero vector $v$ with $A_r v = 0$; then $\\lVert A_r v \\rVert_2 = 0$ while $\\lVert v \\rVert_2 > 0$, so the restricted-isometry inequality $(1-\\delta_n)\\lVert v \\rVert_2^2 \\le \\lVert A_r v \\rVert_2^2$ forces $\\delta_n \\ge 1$. Since the theorems assume $\\delta_n \\in (0, 0.5]$, their probability bounds cannot apply to any matrix of the intended size.","supporting_citations":[{"cited_title":"On the Trade-Off Between Bit Depth and Number of Samples for a Basic Approach to Structured Signal R ecovery Fromb-Bit Quantized Linear Measurements,","cited_arxiv_id":null,"evidence_quote":"Justifies the design choice that one-bit measurements are optimal for direction estimation under a fixed bit budget, motivating binary-inequality support detection."},{"cited_title":"Signal Recovery From Rand om Measurements Via Orthogonal Matching Pursuit,","cited_arxiv_id":null,"evidence_quote":"Orthogonal matching pursuit is a baseline in the simulation comparison and a representative greedy algorithm for traditional CS."},{"cited_title":"CoSaMP: Iterative signal reco very from incomplete and inaccurate samples,","cited_arxiv_id":null,"evidence_quote":"CoSaMP is a baseline in the simulation comparison."},{"cited_title":"Robust 1-bit Compressed Sens ing and Sparse Logistic Regression: A Convex Programming Approach ,","cited_arxiv_id":null,"evidence_quote":"Provides the Gaussian mean width bound $w^2(\\Sigma'_{n,s}) \\le C s \\log(n/s)$ used to set measurement counts in Theorem 4."},{"cited_title":"Ex- ponential Decay of Reconstruction Error From Binary Measur ements of Sparse Signals,","cited_arxiv_id":null,"evidence_quote":"Yields the simultaneous $(\\ell_2,\\ell_1)$-quotient property that bounds the noise vector in the proof of Theorem 4."},{"cited_title":"Wadsworth and J","cited_arxiv_id":null,"evidence_quote":"Provides the cumulative binomial distribution expression used in the success-probability formulas of Theorems 5 and 6."},{"cited_title":"Decoding by linear programming ,","cited_arxiv_id":null,"evidence_quote":"Defines the restricted isometry property and its monotonicity lemma, which the proofs of Theorems 5 and 6 rely on."},{"cited_title":"The restricted isometry property and it s implications for compressed sensing,","cited_arxiv_id":null,"evidence_quote":"Supplies the cross-column inner-product bound (Lemma 3) used to control the distance between the signal and support-restricted estimates."},{"cited_title":"Dimension Reduction by Rando m Hyperplane Tessellations,","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 3, the random-uniform-tessellation error bound that Theorem 4 extends to sparse signals and one-bit measurements."}],"review_version":1}