Support Recovery in Universal One-bit Compressed Sensing

on YouTube ↗19m

" summary

Universal one-bit schemes recover support with concrete measurement bounds: exact recovery requires roughly O(K^2 log(N/K)) measurements unless the dynamic range or binary assumption holds; epsilon-approximate recovery needs O((K/epsilon) log(N/K)) measurements with a nearly matching lower bound and improves to O(K/√epsilon log N) for binary signals; superset recovery uses O(K^{3/2}/√epsilon log(N/K)) measurements with a √K gap to lower bounds. Construction combines a list union free family, a list disjunct matrix, and a polynomial/powers trick to produce the needed independent rows.

AI-written summary · about

" chapters (6)

1. 0:00Intro
2. 1:36Signal Acquisition and Reconstruction
3. 2:391-bit Compressed Sensing (Problem Statement)
4. 5:38Notions of Support Recovery with minimum measurement
5. 11:06Parallels with Group Testing
6. 14:40Approximate Support Recovery

" related talks

• 28mCombinatorial Problems in Support Recovery for 1-bit Compressed SensingArya Mazumdar · Application-Driven Coding Theory 2024
• 29mCompressive SensingIman Mossavat · PyData Eindhoven 2021
• 26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement ProcessesSidharth Jaggi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 42mAdaptive Sparse Recovery with Limited AdaptivityEric Price · Sublinear Algorithms and Nearest-Neighbor Search
• 45mSemi-Random Models and Robustness in Unsupervised LearningAravindan Vijayaraghavan · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 05mRecovering Hidden Sparsity via Sum of SquaresJonathan Kelner · Semidefinite Optimization, Approximation and Applications 2014
• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)