Combinatorial Problems in Support Recovery for 1-bit Compressed Sensing
summary
One-bit compressed sensing support recovery needs far more non-adaptive, universal measurements than information theory suggests: prior lower bounds are about k^2 (up to logs) and matching constructions use robust union-free families to get ~k^2 log n rows and O(n)-time decoding. This work reduces measurements for superset/approximate recovery using list union-free matrices plus algebraically independent scalings, producing superset guarantees when false positives ≤ εk with ε ≤ 1/√k and requiring roughly max(k^{3/2} log n, (k/ε) log n) measurements.
AI-written summary · about
chapters (8)
- 0:00One-bit compressed sensing intro
- 3:41Why one-bit sensing is interesting
- 6:58Support recovery in one-bit sensing
- 13:32Group testing to list union-free
- 17:26Superset recovery with list disjunct
- 20:16Algebraic independence for recovery
- 23:13Real vs rational vectors gap
- 26:47Open problems and future
related talks
19mSupport Recovery in Universal One-bit Compressed Sensing
29mCompressive Sensing
26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement Processes
42mAdaptive Sparse Recovery with Limited Adaptivity
39mProbabilistic Hashing Methods for Succinct Data Representations and Applications
01h 05mRecovering Hidden Sparsity via Sum of Squares
01h 26mStreaming, Sketching and Sufficient Statistics II
45mSemi-Random Models and Robustness in Unsupervised Learning