FRG: Collaborative Research: Algorithms for sparse data representations

FRG：协作研究：稀疏数据表示算法

• 批准号: 0354464
• 负责人: Ingrid Daubechies
• 金额: $ 17万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0354464&HistoricalAwards=false
• 关键词: FRG; Collaborative; Research; Algorithms; sparse

The investigators address the mathematical underpinnings of compressing large data sets using sparse representations over rich dictionaries and develop a foundation for classifying these problems in terms of their algorithmic complexity. The investigators also find efficient algorithms for computing high-quality sparse representations of data over sophisticated, commonly used dictionaries that provably perform as claimed with respect to both efficiency and correctness of output and are particularly well-suited for massive data set applications. The research proceeds at multiple levels of abstraction. It considers general factors of a representation class that guarantee or preclude such algorithms, it considers algorithms for specific common representation classes, and it finds algorithms for representation classes adapted to specific common (and diverse) applications, such as solutions of partial differential equations, image processing, and database query optimization.Over the past ten years there has been a dramatic increase in data gathering mechanisms, as well as an ever-increasing demand for finer data analysis in applications that rely on scientific and geometric modeling. Each day, literally millions of large data sets are generated in medical imaging, surveillance, and scientific acquisition. In addition, the internet has become a communication medium with vast capacity, generating massive traffic data sets. The usefulness of these data sets rests on our ability to process them efficiently, whether it be for storage, transmission, visual display, fast on-line graphical query, correlation, or registration against data from other modalities. The current state of the art in data processing is far from providing the efficient and faithful representations required in emerging applications. With few exceptions, previous work has not provided algorithms whose efficiency or output quality, though typically validated experimentally, has been analyzed rigorously and thoroughly. The investigators carry out fundamental mathematical and algorithmic research to significantly increase our capacity to process and manage large data sets. The research makes significant mathematical progress in providing rigorous algorithmic results that are of great need in this field. The research also makes significant improvements through highly efficient algorithms in the sizes of data sets that are analyzable and in the types of data processing tasks that can be carried out. Finally, the investigators create a library of software for massive data processing applications.

研究人员解决了在丰富的字典上使用稀疏表示压缩大型数据集的数学基础，并开发了根据算法复杂性对这些问题进行分类的基础。研究人员还发现了有效的算法，用于在复杂的、常用的字典上计算高质量的稀疏数据表示，这些字典可以证明在输出的效率和正确性方面都如所声称的那样执行，并且特别适合于大规模数据集应用程序。研究在多个抽象层次上进行。它考虑了保证或排除这种算法的表示类的一般因素，它考虑了特定通用表示类的算法，并找到了适合于特定通用（和不同）应用程序的表示类的算法，例如偏微分方程的解、图像处理和数据库查询优化。在过去的十年中，数据收集机制有了急剧的增长，同时依赖于科学和几何建模的应用程序对更精细的数据分析的需求也在不断增长。每天，数以百万计的大型数据集在医学成像、监测和科学采集中产生。此外，互联网已经成为一种容量巨大的通信媒介，产生了大量的流量数据集。这些数据集的有用性取决于我们有效处理它们的能力，无论是存储、传输、视觉显示、快速在线图形查询、关联，还是与其他模式的数据进行注册。目前的数据处理技术还远远不能提供新兴应用程序所需的高效和忠实的表示。除了少数例外，以前的工作没有提供其效率或输出质量的算法，尽管通常经过实验验证，但已经经过严格和彻底的分析。研究人员进行基础数学和算法研究，以显着提高我们处理和管理大型数据集的能力。该研究取得了重大的数学进展，提供了该领域急需的严谨的算法结果。该研究还通过高效的算法在可分析数据集的大小和可执行的数据处理任务类型方面取得了重大进展。最后，研究人员创建了一个用于海量数据处理应用程序的软件库。