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

AF：媒介：协作研究：稀疏逼近：理论与扩展

• 批准号: 1161151
• 负责人: Shanmugavelayu Muthukrishnan
• 金额: $ 29万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1161151&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Sparse

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.

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