From medical imaging to astronomy, scientific hypothesis testing to data analysis, computers are used in a wide variety of areas where computation is cheaper than data collection. Such situations call for algorithms that are not only fast, but also data efficient. This project considers sub-linear algorithms for fundamental computational problems of interest in both theory and practice. It focuses on two basic questions: how many samples, or noisy observations from a signal, does it take to accurately reconstruct the signal, and how many samples from an object does it take to estimate a property of the object?
The PI will investigate ways to leverage knowledge of signal structure into improved signal reconstruction. An example signal structure is the property of having a sparse Fourier transform; this has been well studied in the discrete setting, but is still poorly understood in the more realistic continuous setting. Another signal structure is that given by generative models built with deep convolutional neural networks; these have produced remarkably accurate models of images in recent years. This project will use such models to estimate images more accurately from fewer measurements. The PI will also investigate problems in distribution testing and graph sampling, with a goal of translating techniques from the distribution testing literature into the statistical hypothesis testing framework. The PI will incorporate research into teaching, and mentor students at levels ranging from high school to graduate school.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
