Learning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement Processes

on YouTube ↗26m

" summary

This framework unifies compressed sensing, network tomography, phase retrieval and group testing and claims near‑optimal sample complexity (order k measurements up to small constants) with near‑linear decoding time (roughly k log k or constant‑factor overheads). It uses sparse bipartite graph measurement designs, leverages singletons and iterative peeling decoding, and for nonlinear cases introduces sigma structures plus algebraic tricks (solve small quadratic systems) to recover phases. The constructions specify measurement values, not just graph topology, and empirically match the stated complexities.

AI-written summary · about

" chapters (17)

1. 0:00Start
2. 1:21Sparse Recovery
3. 2:00Compressive Sensing - Linear Measurement
4. 4:42Network Tomography - Restricted Linear Measurements
5. 5:21Problem 3: Compressive Phase Retrieval - Non-Linear (Intensity) Measurement
6. 6:05Group Testing - Non-Linear (OR) Measurement
7. 11:06"Gold Bar" Puzzle II
8. 12:00Measurement Structure: Bipartite Graph
9. 12:38Decoding Process: Picking & Peeling
10. 15:26SHO-FA: Compressive Sensing
11. 16:29Problem 1: Compressive Sensing
12. 18:54"Gold Bar" Puzzle Recap
13. 19:32Phases from Magnitudes?
14. 22:25Identifying Singletons
15. 23:09Decoding Graph
16. 23:55Our Contribution: Fast and Efficient Algorithms
17. 24:18"Good" Bipartite Graph + Structured Measurements

" related talks

• 29mCompressive SensingIman Mossavat · PyData Eindhoven 2021
• 28mCombinatorial Problems in Support Recovery for 1-bit Compressed SensingArya Mazumdar · Application-Driven Coding Theory 2024
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 45mNoisy Estimation of Simultaneously Structured ModelsMaryam Fazel · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 19mSupport Recovery in Universal One-bit Compressed SensingSoumyabrata Pal, Arya Mazumdar · ITCS 2022
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 39mProbabilistic Hashing Methods for Succinct Data Representations and ApplicationsPing Li · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)