AF: Medium: Collaborative Research: Sparse Approximation: Theory and Extensions

在过去的十年里，理论计算机科学、应用数学和电子工程界广泛地研究了“求解”欠定线性系统问题的各种变体。让我们能够解决这些问题的一个常见的数学特征是稀疏性；粗略地说，只要未知向量不包含太多的非零分量（或有几个主导分量），我们就可以“解”未知向量的欠定系统。这些问题被称为稀疏逼近问题，在信号和图像处理、生物学、成像、断层扫描、机器学习等各个领域都有应用。提出的研究项目旨在发展一个全面的，严格的稀疏近似理论，广泛定义。研究计划包括两个互补的研究方向：(1)对稀疏逼近的组合、算法和复杂性理论基础（包括将其推广到泛函稀疏逼近，我们想要“解决”未知向量的某些函数，而不是向量本身）的稳健和更完整的观点；(2)结合其在理论计算机科学的其他领域的相互作用或直接应用，从复杂性理论到编码理论，以及电子工程；从信号处理到模数转换器。一个专注于竞争参数之间的最佳权衡和实现这种权衡的计算可行性的一般稀疏逼近理论不仅有助于探索稀疏逼近的理论极限和可能性，而且还将算法技术和理论基准带回其应用领域。稀疏逼近已经被证明在许多领域都有影响，包括成像和信号处理、互联网流量分析、生物学实验设计和药物设计。

In the past ten years the theoretical computer science, applied math and electrical engineering communities have extensively studied variants of the problem of ``solving" an under-determined linear system. One common mathematical feature that allows us to solve these problems is sparsity; roughly speaking, as long as the unknown vector does not contain too many non-zero components (or has a few dominating components), we can ``solve'' the under-determined system for the unknown vector. These problems are referred to as sparse approximation problems and have applications in diverse areas such as signal and image processing, biology, imaging, tomography, machine learning and others.The proposed research project aims to develop a comprehensive, rigorous theory of sparse approximation, broadly defined. The research proposal entails two complementary research directions: (1) a robust and more complete view of the combinatorial, algorithmic, and complexity-theoretic foundations of sparse approximations (including its generalization to functional sparse approximation where we want to ``solve" for some function of the unknown vector instead of the vector itself),(2) coupled with either its interactions or direct applications in other areas of theoretical computer science, from complexity theory to coding theory, and of electrical engineering, from signal processing to analog-to-digital converters.A general theory of sparse approximation that concentrates both on the optimal tradeoffs between competing parameters and the computational feasibility of attaining such tradeoffs will not only help explore the theoretical limits and possibilities of sparse approximations, but also feed algorithmic techniques and theoretical benchmarks back to its application areas. Sparse approximation already has been shown to have impact in a variety of fields, including imaging and signal processing, Internet traffic analysis, and design of experiments in biology and drug design.