Pith. sign in

REVIEW 6 minor 30 references

Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals

T0 review · 0 major / 6 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read One-bit recovery of approximately sparse signals cannot beat uniform Euclidean error of order (k/m) to the power 1/3.

desk verdict Clean matching lower bounds for the (k/m)^{1/3} rate in one-bit CS of approximately sparse signals; the construction is elementary and the open question is closed under standard random designs. read the letter →

arxiv 2607.06750 v1 pith:XW3NR3AF submitted 2026-07-07 cs.IT eess.SPmath.IT

Junren Chen , Arya Mazumdar , Ming Yuan This is my paper · ORCID
classification cs.ITeess.SPmath.IT MSC 94A1262B10
keywords one-bitcompressedsensingapproximatesparsitylowerboundsditheringℓqballsuniformrecoveryhyperplanetessellations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that when signals live only in a scaled ℓ1 ball rather than being exactly k-sparse, any decoder that sees only the signs of m linear measurements must suffer uniform Euclidean error at least on the order of (k/m)^{1/3}, up to logs. The same near-matching lower bound holds for the uniformly dithered model. Earlier work already attained this rate by algorithms and by Hamming-distance minimization, yet no information-theoretic lower bound of matching strength was known; the only prior lower bound was the much smaller Ω(k/m) that applies to exact sparsity. The argument first embeds a small Euclidean ball inside the approximately sparse set (directly for the dithered model, via a lifting map for the undithered sphere) and then constructs two points inside that ball that are far apart yet produce identical binary measurements. The same technique yields a continuous family of rates for ℓq-balls that interpolates between exact sparsity and ℓ1 sparsity, and extends to adversarial flips, low-rank matrices, and the transition into the non-sparse regime.

What carries the argument

A construction lemma that, inside a small Euclidean sphere of radius r and dimension s, produces a unit vector u* satisfying sign(Z(ru*)+ξ)=sign(ξ) whenever s/(m√log m) is at least a constant times r; combined with an embedding (or lifting) of that sphere into the approximately sparse set, this forces two indistinguishable signals separated by distance Ω(r).

What would settle it

Produce a sub-Gaussian ensemble together with a decoder that, with high probability, recovers every vector in the scaled ℓ1 ball to uniform Euclidean accuracy o((k/m)^{1/3}); or exhibit a fixed deterministic matrix for which some decoder beats that rate uniformly.

Watch

Extended reading notes

Core claim

Under independent sub-Gaussian sensing matrices, every measurable decoder for signals in the scaled ℓ1 ball K_{1,k} (or its unit-sphere version) from m one-bit observations incurs uniform Euclidean error Ω̃((k/m)^{1/3}). The identical rate is optimal for the uniformly dithered model, and the construction extends to scaled ℓq balls, producing the matching lower bound Ω̃((k/m)^{(2-q)/(2+q)}) for every q in [0,1].

Load-bearing premise

The sensing rows must be independent and sub-Gaussian (or at least sub-Weibull) so that a single carefully chosen direction can be made invisible to every measurement at once.

Editorial extensions

If this is right

  • Known algorithmic upper bounds of order (k/m)^{1/3} for ℓ1-sparse one-bit CS are information-theoretically tight up to logarithmic factors.
  • The optimal uniform rate for ℓq-sparse signals is Θ̃((k/m)^{(2-q)/(2+q)}), continuously bridging exact sparsity and ℓ1 sparsity.
  • A β-fraction of adversarial bit flips forces an unavoidable additive error of order β (or λβ in the dithered model).
  • Approximately low-rank matrix recovery from one-bit measurements obeys the same (r-bar max(n1,n2)/m)^{1/3} lower bound.
  • As sparsity approaches ambient dimension the lower bound transitions smoothly to the non-sparse rate n/m.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same embedding-plus-indistinguishability idea is likely to yield matching lower bounds for multi-bit dithered quantization and for one-bit phase retrieval, both of which currently show m^{-1/3} upper bounds for soft-sparse signals.
  • Removing the residual √log m factor from the lower bound would require a tighter small-ball or tail analysis and would fully close the gap with the best upper bounds.
  • If the lower bound fails for deterministic designs with large row norms, approximate sparsity would exhibit a genuine random-versus-adversarial separation that exact sparsity does not.
  • The continuous ℓq family of rates suggests that intermediate sparsity models can be tuned to trade sample complexity against recoverable accuracy in a predictable way.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper proves the first near-optimal uniform lower bounds for one-bit compressed sensing of approximately sparse signals. For signals in the scaled ℓ₁ ball K_{1,k} (or its spherical version K^*_{1,k}), under independent sub-Gaussian rows (Assumptions 1–3), any decoder from m binary measurements must incur Euclidean error Ω̃((k/m)^{1/3}) in both the canonical model y = sign(Ax) and the uniformly dithered model y = sign(Ax + τ). The argument embeds a small Euclidean ball of radius r into the signal set (directly for the dithered model; via a lifting map Φ_s for the undithered model) and then, via a construction lemma, produces two points inside that ball that are separated by Θ(r) yet produce identical binary observations. The same technique yields the interpolating rate Ω̃((k/m)^{(2-q)/(2+q)}) for scaled ℓ_q balls, q ∈ [0,1], and is extended to sub-Weibull designs, adversarial bit flips, nuclear-norm matrix recovery, and the sparse-to-dense transition.

Significance. The (k/m)^{1/3} upper bound for ℓ₁-sparse one-bit CS has appeared in several works (Hamming-distance minimization, Adaboost, projected gradient descent) and was repeatedly flagged as possibly suboptimal. Matching lower bounds close that gap up to logarithmic factors and thereby settle the information-theoretic rate for the most common convex relaxation of exact sparsity. The construction is elementary (Chernoff + kernel + sub-Gaussian tail), self-contained, and flexible enough to cover dithered/undithered models, ℓ_q sparsity, and low-rank matrices with essentially the same argument. Full proofs of the main theorems are supplied; the paper also cleanly recovers earlier hyperplane-tessellation lower bounds as corollaries. These are solid, reusable contributions to the foundations of quantized compressed sensing.

minor comments (6)
  1. Throughout (abstract, introduction, takeaways) the notation “eO / eΩ / eΘ” is used for soft-O; standard Õ / Ω̃ / Θ̃ (or Õ) would improve readability and match the rest of the literature.
  2. Section 4 takeaway boxes contain the typographical artifact “T akeaway” (space after T). Same for a few other line-break artifacts in the arXiv source.
  3. Lemma 1, display (28): the bound P̄_i ≤ s/(4m) is written with a chain of inequalities that mixes the hypothesis (25) and the trivial s ≤ m; a short parenthetical “using (25) and s ≤ m” would make the arithmetic immediate.
  4. Corollary 2: the numerical prefactor (π/4)^{1/6}/8 is correct but opaque; a one-line derivation from the choice of r in the proof of Corollary 2 would help readers who only consult the statement.
  5. Section 4.2 (sub-Weibull) and 4.4 (matrices) are sketched at the level of “the same argument yields \\ldots”. For archival value it would be useful to state the precise analogues of Theorems 1–2 (even if proofs are left as exercises).
  6. References [6] and [7] are cited heavily for matching upper bounds; ensuring that the arXiv versions (or final journal versions) are the ones actually used for the sample-complexity claims in Remarks 1 and 3 would avoid future citation drift.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower bounds rest on an explicit probabilistic construction of indistinguishable pairs, not on fitted quantities or self-referential premises.

full rationale

The derivation chain is self-contained. Theorems 1–2 and Corollaries 1–2 follow from two elementary steps that are proved in full: (i) embedding a Euclidean ball of radius r into K_{1,k} (or its spherical version via the lifting map Φ_s of Lemma 2) under the dimension condition s ≲ k/r², and (ii) the construction lemma (Lemma 1) that produces, with high probability under the stated sub-Gaussian/small-ball assumptions, a vector u* on the sphere of that ball satisfying sign(Z(ru*)+ξ)=sign(ξ). The resulting maximal r is of order (k/m)^{1/3} (up to logs). Both steps use only Chernoff bounds, union bounds and elementary linear algebra; they do not invoke any fitted constant, any uniqueness theorem, or any prior result of the authors as a premise. Self-citations (chiefly to the authors’ own upper-bound paper [6]) appear only for context and rate-matching statements and are never load-bearing inside the proofs. The same constructive pattern extends verbatim to the ℓ_q, sub-Weibull, adversarial-flip and low-rank settings of Section 4. Consequently the claimed lower bounds are independent of the inputs they are compared against.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims rest on standard concentration and small-ball assumptions for random matrices and dithers, plus elementary embedding facts for ℓ_q balls. No free parameters are fitted; no new physical or mathematical entities are postulated. All probabilistic tools (Chernoff, sub-Gaussian tails, union bounds) are classical.

assumptions (3)
  • domain assumption Rows of A are independent and L-sub-Gaussian (or sub-Weibull with parameter α); last coordinate or dither satisfies a uniform small-ball bound P(|ξ_i|≤t)≤2 ho t.
    Assumptions 1–3 and the hypothesis of Lemma 1; required for the high-probability construction of an orthogonal vector that stays below the large dither entries.
  • standard math Chernoff bound and standard sub-Gaussian maximal inequalities hold for independent rows.
    Used repeatedly in the proof of Lemma 1 to control |I| and max |z_i^ op u*|.
  • standard math The scaled ℓ_q ball K_{q,k} contains a Euclidean ball of radius r and dimension s whenever s≤k/r^{2q/(2-q)} (or the lifted version for the spherical case).
    Lemma 3; elementary Hölder comparison, used to embed the construction space inside the signal set.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals." pith.science (2026). https://pith.science/paper/XW3NR3AF

@misc{pith2026260706750,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XW3NR3AF}},
  note         = {Machine review of arXiv:2607.06750}
}
abstract

This paper provides the first near-optimal lower bounds for one-bit compressed sensing of approximately sparse signals lying in a scaled $\ell_1$ ball, which is a commonly adopted relaxation of the exactly $k$-sparse assumption. In prior works, the best known upper bounds on uniform Euclidean error are of order $\widetilde{O}((k/m)^{1/3})$, where $m$ is the number of measurements. Under sub-Gaussian matrices, we establish nearly matching lower bounds for both the canonical one-bit compressed sensing model and the uniformly dithered model. Our argument is to first embed a small Euclidean ball into the signal set, which is straightforward for the dithered model but relies on a lifting map for the canonical model, and then construct two signals in this small ball that are separated in Euclidean distance by at least $(k/m)^{1/3}$ (up to logarithmic factor) but are indistinguishable from the binary measurements. Moreover, our argument extends to approximately sparse signals that live in a properly scaled $\ell_q$ ball $(q\in [0,1])$, yielding a lower bound $\widetilde{\Omega}((k/m)^{\frac{2-q}{2+q}})$ that smoothly bridges the cases of exact sparsity ($q=0$) and $\ell_1$ sparsity ($q=1$). Finally, we discuss the extensions of our lower bounds to sub-Weibull matrices, adversarial bit flipping, matrix recovery, and characterize the transition to the non-sparse case.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Improved bounds for universal one-bit compressive sensing

    Jayadev Acharya, Arnab Bhattacharyya, and Pritish Kamath. Improved bounds for universal one-bit compressive sensing. In2017 IEEE International Symposium on Information Theory (ISIT), pages 2353–2357. IEEE, 2017

    work page 2017

  2. [2]

    Milman.Asymptotic Geometric Analysis, Part I, volume 202 ofMathematical Surveys and Monographs

    Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman.Asymptotic Geometric Analysis, Part I, volume 202 ofMathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2015

    work page 2015

  3. [3]

    Learning and 1-bit compressed sensing under asymmetric noise

    Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learning and 1-bit compressed sensing under asymmetric noise. InConference on Learning Theory, pages 152–192. PMLR, 2016

    work page 2016

  4. [4]

    1-bit compressive sensing

    Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In2008 42nd Annual Conference on Information Sciences and Systems, pages 16–21. IEEE, 2008

    work page 2008

  5. [5]

    Robust instance optimal phase-only com- pressed sensing.Information and Inference: A Journal of the IMA, 15(2):iaag014, 06 2026

    Junren Chen, Michael K Ng, and Jonathan Scarlett. Robust instance optimal phase-only com- pressed sensing.Information and Inference: A Journal of the IMA, 15(2):iaag014, 06 2026

    work page 2026

  6. [6]

    Optimal Quantized Compressed Sensing via Projected Gradient Descent

    Junren Chen and Ming Yuan. Optimal quantized compressed sensing via projected gradient descent.arXiv preprint arXiv:2407.04951, 2024

    work page Pith review arXiv 2024

  7. [7]

    One-bit phase retrieval: Optimal rates and efficient algorithms

    Junren Chen and Ming Yuan. One-bit phase retrieval: Optimal rates and efficient algorithms. IEEE Transactions on Information Theory, 72(7):5251–5292, 2026

    work page 2026

  8. [8]

    Adaboost and robust one-bit compressed sensing.Mathematical Statistics and Learning, 5(1):117–158, 2022

    Geoffrey Chinot, Felix Kuchelmeister, Matthias Löffler, and Sara van de Geer. Adaboost and robust one-bit compressed sensing.Mathematical Statistics and Learning, 5(1):117–158, 2022

    work page 2022

Show all 30 references
  1. [9]

    One-bit compressed sensing with partial gaussian circulant matrices.Information and Inference: A Journal of the IMA, 9(3):601– 626, 2020

    Sjoerd Dirksen, Hans Christian Jung, and Holger Rauhut. One-bit compressed sensing with partial gaussian circulant matrices.Information and Inference: A Journal of the IMA, 9(3):601– 626, 2020

    2020

  2. [10]

    Non-gaussian hyperplane tessellations and robust one-bit compressed sensing.Journal of the European Mathematical Society, 23(9):2913–2947, 2021

    Sjoerd Dirksen and Shahar Mendelson. Non-gaussian hyperplane tessellations and robust one-bit compressed sensing.Journal of the European Mathematical Society, 23(9):2913–2947, 2021

    2021

  3. [11]

    Robust one-bit compressed sensing with partial circulant matrices.The Annals of Applied Probability, 33(3):1874–1903, 2023

    Sjoerd Dirksen and Shahar Mendelson. Robust one-bit compressed sensing with partial circulant matrices.The Annals of Applied Probability, 33(3):1874–1903, 2023. 23

    1903

  4. [12]

    Sharp estimates on random hyperplane tessellations.SIAM Journal on Mathematics of Data Science, 4(4):1396–1419, 2022

    Sjoerd Dirksen, Shahar Mendelson, and Alexander Stollenwerk. Sharp estimates on random hyperplane tessellations.SIAM Journal on Mathematics of Data Science, 4(4):1396–1419, 2022

    2022

  5. [13]

    A resolution of the gaussian hyperplane tessellation conjecture on the sphere.Applied and Computational Harmonic Analysis, page 101903, 2026

    Sjoerd Dirksen and Nigel QD Strachan. A resolution of the gaussian hyperplane tessellation conjecture on the sphere.Applied and Computational Harmonic Analysis, page 101903, 2026

    2026

  6. [14]

    Nbiht: An efficient algorithm for 1-bit compressed sensing with optimal error decay rate.IEEE Transactions on Information Theory, 68(2):1157–1177, 2021

    Michael P Friedlander, Halyun Jeong, Yaniv Plan, and Özgür Yılmaz. Nbiht: An efficient algorithm for 1-bit compressed sensing with optimal error decay rate.IEEE Transactions on Information Theory, 68(2):1157–1177, 2021

    2021

  7. [15]

    On the sample complexity of parameter estimation in logistic regression with normal design

    Daniel Hsu and Arya Mazumdar. On the sample complexity of parameter estimation in logistic regression with normal design. InThe Thirty Seventh Annual Conference on Learning Theory, pages 2418–2437. PMLR, 2024

    2024

  8. [16]

    Robust 1- bit compressive sensing via binary stable embeddings of sparse vectors.IEEE Transactions on Information Theory, 59(4):2082–2102, 2013

    Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1- bit compressive sensing via binary stable embeddings of sparse vectors.IEEE Transactions on Information Theory, 59(4):2082–2102, 2013

  9. [17]

    Quantized com- pressed sensing by rectified linear units.IEEE Transactions on Information Theory, 67(6):4125– 4149, 2021

    Hans Christian Jung, Johannes Maly, Lars Palzer, and Alexander Stollenwerk. Quantized com- pressed sensing by rectified linear units.IEEE Transactions on Information Theory, 67(6):4125– 4149, 2021

    2021

  10. [18]

    Efficient learning of gener- alized linear and single index models with isotonic regression.Advances in Neural Information Processing Systems, 24, 2011

    Sham M Kakade, Varun Kanade, Ohad Shamir, and Adam Kalai. Efficient learning of gener- alized linear and single index models with isotonic regression.Advances in Neural Information Processing Systems, 24, 2011

    2011

  11. [19]

    One-bit compressive sensing with norm estima- tion.IEEE Transactions on Information Theory, 62(5):2748–2758, 2016

    Karin Knudson, Rayan Saab, and Rachel Ward. One-bit compressive sensing with norm estima- tion.IEEE Transactions on Information Theory, 62(5):2748–2758, 2016

    2016

  12. [20]

    Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub-gaussianity in high- dimensional statistics: Applications in covariance estimation and linear regression.Information and Inference: A Journal of the IMA, 11(4):1389–1456, 2022

    2022

  13. [21]

    On the sample complexity of pac learning half-spaces against the uniform distribution.IEEE Transactions on Neural Networks, 6(6):1556–1559, 1995

    Philip M Long. On the sample complexity of pac learning half-spaces against the uniform distribution.IEEE Transactions on Neural Networks, 6(6):1556–1559, 1995

    1995

  14. [22]

    Binary iterative hard thresholding converges with optimal number of measurements for 1-bit compressed sensing.Journal of the ACM, 71(5):1–64, 2024

    Namiko Matsumoto and Arya Mazumdar. Binary iterative hard thresholding converges with optimal number of measurements for 1-bit compressed sensing.Journal of the ACM, 71(5):1–64, 2024

    2024

  15. [23]

    Robust 1-bit compressed sensing with iterative hard thresholding

    Namiko Matsumoto and Arya Mazumdar. Robust 1-bit compressed sensing with iterative hard thresholding. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2941–2979. SIAM, 2024

    2024

  16. [24]

    Near-optimal bounds for binary embeddings of arbitrary sets

    Samet Oymak and Ben Recht. Near-optimal bounds for binary embeddings of arbitrary sets. arXiv preprint arXiv:1512.04433, 2015. 24

    2015 arXiv

  17. [25]

    Robust 1-bit compressed sensing and sparse logistic regres- sion: A convex programming approach.IEEE Transactions on Information Theory, 59(1):482– 494, 2012

    Yaniv Plan and Roman Vershynin. Robust 1-bit compressed sensing and sparse logistic regres- sion: A convex programming approach.IEEE Transactions on Information Theory, 59(1):482– 494, 2012

    2012

  18. [26]

    One-bit compressed sensing by linear programming.Com- munications on Pure and Applied Mathematics, 66(8):1275–1297, 2013

    Yaniv Plan and Roman Vershynin. One-bit compressed sensing by linear programming.Com- munications on Pure and Applied Mathematics, 66(8):1275–1297, 2013

    2013

  19. [27]

    Dimension reduction by random hyperplane tessellations

    Yaniv Plan and Roman Vershynin. Dimension reduction by random hyperplane tessellations. Discrete & Computational Geometry, 51(2):438–461, 2014

    2014

  20. [28]

    The generalized lasso for sub-gaussian measure- ments with dithered quantization.IEEE Transactions on Information Theory, 66(4):2487–2500, 2020

    Christos Thrampoulidis and Ankit Singh Rawat. The generalized lasso for sub-gaussian measure- ments with dithered quantization.IEEE Transactions on Information Theory, 66(4):2487–2500, 2020

    2020

  21. [29]

    Quantized compressive sensing with rip matrices: The benefit of dithering.Information and Inference: A Journal of the IMA, 9(3):543–586, 2020

    Chunlei Xu and Laurent Jacques. Quantized compressive sensing with rip matrices: The benefit of dithering.Information and Inference: A Journal of the IMA, 9(3):543–586, 2020. A Proof of Lemma 3 Proof of Lemma 3.For anyq∈(0,1]we shall repeatedly use the elementary bound ∥u∥q q ...

    2020

  22. [30]

    Now notice that the condition (58) is equivalent tos1− q 2 rq ≤k 1− q 2 .Hence∥u∥ q ≤k 1 q − 1 2, meaning thatu∈k 1 q − 1 2 Bn q by viewinguas(u ⊤,0 n−s)⊤

    Moreover, using (69) and∥u∥2 ≤r, ∥u∥q q ≤s 1− q 2 ∥u∥q 2 ≤s 1− q 2 rq. Now notice that the condition (58) is equivalent tos1− q 2 rq ≤k 1− q 2 .Hence∥u∥ q ≤k 1 q − 1 2, meaning thatu∈k 1 q − 1 2 Bn q by viewinguas(u ⊤,0 n−s)⊤. This provesrB s 2 ⊂ K q,k. For the second claim, t...

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.