CAREER: Fundamental Algorithms for Data-Limited Problems

从医学成像到天文学，从科学假设检验到数据分析，计算机被用于计算比数据收集便宜的各种领域。 这样的情况要求算法不仅快速，而且数据效率高。这个项目考虑了在理论和实践中感兴趣的基本计算问题的次线性算法。它关注两个基本问题：需要多少样本或来自信号的噪声观测来准确地重建信号，以及需要多少来自对象的样本来估计对象的属性？PI将研究如何利用信号结构的知识来改进信号重构。 一个示例信号结构是具有稀疏傅立叶变换的特性;这在离散设置中已经得到了很好的研究，但在更现实的连续设置中仍然知之甚少。另一种信号结构是由深度卷积神经网络构建的生成模型给出的;近年来，这些模型已经产生了非常准确的图像模型。 该项目将使用这些模型从更少的测量中更准确地估计图像。 PI还将调查分布检验和图抽样中的问题，目标是将分布检验文献中的技术转化为统计假设检验框架。 PI将把研究融入教学，指导从高中到研究生院的学生。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.