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

Jul 16, 2026

Upload by Asher

This paper establishes the first near-optimal lower bounds for one-bit compressed sensing of approximately sparse signals modeled as lying in a scaled ℓ1 ball, a standard relaxation of the exact k-sparse assumption. The work strengthens information-theoretic arguments by constructing pairs of signals inside a small Euclidean ball that remain well separated in ℓ2 distance (up to log factors) while producing indistinguishable binary measurements, extending the results to properly scaled ℓq balls (q in [0,1]).

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages25

Reading Time1 h 3 min

Abstract

Introduction

One-bit compressed sensing formulation

Approximately sparse signal models

Prior recovery guarantees and algorithms

Dithering model and motivation for lower bounds

arXiv :2607 .06750v 1 [ cs .IT] 7 Jul 2026 Near-Optimal Lower Bounds on One-Bit Compressed Sensing of Approximately Sparse Signals Junren Chen∗ Arya Mazumdar† Ming Yuan‡ July 9, 2026 Abstract This paper provides the first near-optimal lower bounds for one-bit compressed sensing of approximately sparse signals lying in a scaled ℓ 1 ball, which is a commonly adopted relaxation of the exactly k-sparse assumption. In prior works, the best known upper bounds on uniform EGcoucaumlispdsreaianessneemdrrasortrenicsaresineg, ofwmoeoreddseetlrabas(h(kth/mneeau)1rln/3yifo)mr,watmlhcyehreindimgthleiors tweedher bmnooduuembndlserfOoorurf mebotargahusutmreheenmtecintans tsoo.nUicfirndalsteoernemsb-ubbeitda 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 ℓq ball (q ∈ [0 , 1]), yielding a lower bb(oqitd1ip)iFn( g(kin, /mallmya)t, )drthiscecatuovsesms try,hoeaoenthxtdlyenchbsiarrioadgnscteoersfitozehuerthlcoeawtsererasbnoosifutienoxdnasctttoosstpuhaber-sWnoityeni-bs(qupla0atc)raaniceseds, ℓ 1advsparsersariityal 1 Introduction In one-bit compressed sensing (1bCS), one seeks to recover sparse vectors from the signs of linear measurements [4, 16 , 25 , 26], that is, to recover some x ∈ Σnk ,∗ := Σnk ∩ Sn−1 from y = sign(Ax) (1) and a known measurement matrix A ∈ Rm ×n. Here, Σnk = {u ∈ Rn : ∥u∥0 ≤ k} denotes the cone of k-sparse vectors in Rn , Sn−1 = {u ∈ Rn : ∥u∥2 = 1} denotes the unit Euclidean sphere, and sign(a) := 1 (a ≥ 0)−1(a < 0) is applied element-wise to vectors. Note that it is standard to assume x ∈ Sn−1 in 1bCS since the quantization loses all the information of signal norm. For arbitrary matrix A, any estimator ˆx that is a measurable function of (A, y) admits a uniform recovery ℓ2 error lower ∗ Department of Statistics, Columbia University. (Email: [jc6315@columbia.edu](jc6315@columbia.edu))†Halıcıoğlu Data Science Institute, UC San Diego. (Email: [arya@ucsd.edu](arya@ucsd.edu))‡Department of Statistics, Columbia University. (Email: [my2550@columbia.edu](my2550@columbia.edu)) bound sup ∥ˆx − x∥2 ≳ k . (2) x∈Σnk , ∗ m See [16, Theorem 2] and [1, Theorem 6] . Throughout this paper, we write T1 = Ω(T2 ) or T1 ≳ T2 to denote T1 ≥ cT2 for some universal constant c > 0. Under Gaussian design A that has i.i.d. N(0, 1) entries, it was shown [22] that an efficient algorithm called normalized binary iterative hard thresholding (NBIHT) achieves the lower bound (2) up to logarithmic factors, i.e. , xpnk, ∗ ∥ˆxnbiht − x∥2 = 􀀐 km􀀑 , (3) where ˆxnbiht denotes the output of NBIHT. (See also the earlier analysis in [14].) By convention, T1anwe( lod) ohlrieTdette1lrTaror2 dithveenmctiotcorefasscahodatrsmTofat1r(i,Cns, T)r2iengfoOulras(ro)lmaetudersniΩfv(oer)r,saresclsalcpaoernctsstantively. CT>hr0ou, anghdouhuesepae(·r), However, signals in real applications are typically only approximately sparse rather than exactly living in Σnk for some k. For any q > 0, let Bnq = {u ∈ Rn : ∥u∥q := (P |ui|q )1/q ≤ 1} denote the unit ℓq ball. The most common formulation of the set of approximately (or effectively) k-sparse signals in the unit Euclidean ball Bn2 is via K 1,k := √kBn1 ∩ Bn2 . This is a relaxation of Σnk ∩ Bn2 in view of K 1,k ⊃ Σnk ∩ Bn2, and indeed, K 1,k can be viewed as the convex hull of Σnk ∩Bn2 [26, Lemma 3.1] . In the sequel, we may refer to the vectors in K 1,k as ℓ1-sparse signals, implicitly for some sparsity level k. Motivated by this consideration, previous works have established a number of recovery guarantees for 1bCS of x ∈ K ∗1,k := √kBn1 ∩ Sn−1 [25 , 26 , 3 , 8 , 6 , 9] . For simplicity we assume k is known.

FAQs

What problem does the paper study in one-bit compressed sensing?

The paper studies information-theoretic lower bounds for recovering approximately sparse signals from the signs of linear measurements in the one-bit compressed sensing model.

How does the paper model approximately sparse signals?

It uses a scaled ℓ1-ball relaxation of exact k-sparsity, and extends the analysis to signals in properly scaled ℓq balls for q in [0,1].

What is the key strategy used to prove the lower bounds?

The proof constructs two signals inside a small Euclidean ball that are separated in ℓ2 distance (up to logarithmic factors) yet become indistinguishable under the binary measurement outcomes.

Jul 16, 2026

Upload by Asher