Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917400796987392 |
|---|---|
| author | Li, Xiaxin Mazumdar, Arya |
| author_facet | Li, Xiaxin Mazumdar, Arya |
| contents | One-bit compressed sensing (1bCS) addresses the recovery of sparse signals from highly quantized measurements, retaining only the sign of each linear measurement. In the support recovery setting, the goal is to identify $\text{supp}(x)$, the nonzero coordinates of an unknown signal $x \in \mathbb{R}^n$ from $y = \text{sign}(Ax)$, where $A \in \mathbb{R}^{m \times n}$ and $|\text{supp}(x)| \le k \ll n$. Existing methods minimize the number of measurements but often incur $Ω(n)$ decoding complexity, limiting large-scale applicability.
We propose new 1bCS schemes that achieve sublinear decoding complexity while maintaining near-optimal measurement bounds. For universal support recovery, our framework provides: (i) exact recovery with $m = O(k^2 \log(n/k) \log n)$ measurements and decoding complexity $D=O(km)$, and (ii) $ε$-approximate recovery with $m = O(k ε^{-1} \log(n/k) \log n)$ and $D=O(ε^{-1} m)$. For probabilistic exact recovery, we design a scheme with $m = O\big(k \frac{\log k}{\log\log k} \log n\big)$ and $D=O(m)$, achieving vanishing error probability.
Our approach leverages ideas from group testing to bridge classical sparse recovery techniques with modern algorithmic efficiency considerations, highlighting a new trade-off between compression efficiency and computational complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10777 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time Li, Xiaxin Mazumdar, Arya Information Theory Discrete Mathematics Data Structures and Algorithms One-bit compressed sensing (1bCS) addresses the recovery of sparse signals from highly quantized measurements, retaining only the sign of each linear measurement. In the support recovery setting, the goal is to identify $\text{supp}(x)$, the nonzero coordinates of an unknown signal $x \in \mathbb{R}^n$ from $y = \text{sign}(Ax)$, where $A \in \mathbb{R}^{m \times n}$ and $|\text{supp}(x)| \le k \ll n$. Existing methods minimize the number of measurements but often incur $Ω(n)$ decoding complexity, limiting large-scale applicability. We propose new 1bCS schemes that achieve sublinear decoding complexity while maintaining near-optimal measurement bounds. For universal support recovery, our framework provides: (i) exact recovery with $m = O(k^2 \log(n/k) \log n)$ measurements and decoding complexity $D=O(km)$, and (ii) $ε$-approximate recovery with $m = O(k ε^{-1} \log(n/k) \log n)$ and $D=O(ε^{-1} m)$. For probabilistic exact recovery, we design a scheme with $m = O\big(k \frac{\log k}{\log\log k} \log n\big)$ and $D=O(m)$, achieving vanishing error probability. Our approach leverages ideas from group testing to bridge classical sparse recovery techniques with modern algorithmic efficiency considerations, highlighting a new trade-off between compression efficiency and computational complexity. |
| title | Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time |
| topic | Information Theory Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.10777 |