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.