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

在过去的十年里，理论计算机科学，应用数学和电气工程社区已经广泛研究了“解决”欠定线性系统问题的变体。 一个共同的数学特征，使我们能够解决这些问题是稀疏性;粗略地说，只要未知向量不包含太多的非零分量（或有几个主导分量），我们可以“解决”未知向量的欠定系统。 这些问题被称为稀疏近似问题，并在不同的领域，如信号和图像处理，生物学，成像，断层扫描，机器学习和other.The拟议的研究项目的应用程序旨在开发一个全面的，严格的稀疏近似理论，广义。 该研究计划涉及两个互补的研究方向：（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.