Dr. Eric Price, 'Instance-Optimal Compressed Sensing via Conditional Resampling', TADS Lunch-n-Learn

Thursday, April 29, 2021 - 12:00pm to 1:00pm
Event Type: 

Dr. Eric Price

Presenter: Dr. Eric Price

Title: Instance-Optimal Compressed Sensing via Conditional Resampling

Abstract: Given a distribution P of images, how many random linear measurements are required for approximate recovery? Classical compressed sensing gives an upper bound for approximately sparse P, but actual distributions may have more or different structure than sparsity.  We instead give an instance-optimal bound: when P is (approximately) known, then _conditional resampling_, where we output a sample of P(x | y), is within constant factors of the best possible recovery algorithm.

When applied to state-of-the-art deep generative models, we find that conditional resampling produces less washed-out, more realistic
results than prior methods. It also has nice fairness properties, including proportional representation: the representation of any group in the output matches the input distribution.


Bio: Eric Price is an associate professor in the Department of Computer Science at UT Austin, where he studies how algorithms can produce more accurate results with less data. He received a Ph.D. in computer science from MIT in 2013. Eric's research was featured in Technology Review's TR10 list of 10 breakthrough technologies of 2012, his thesis received a George M. Sprowls award for best doctoral thesis in computer science at MIT, and he has received an NSF CAREER award. Two themes of his research are adaptivity, where initial data can guide future data collection, and signal structure, where a structural assumption can yield provable improvements in space or sample complexity.

After the presentation, there will be a short time for discussion and questions.