FRG: Collaborative Research: Algorithms for sparse data representations

研究人员解决了使用丰富词典上的稀疏表示来压缩大型数据集的数学基础，并根据算法复杂性对这些问题进行了分类。研究人员还发现用于计算数据的高质量稀疏表示的高效算法超过复杂的、常用的词典，这些词典在输出的效率和正确性方面都被证明具有所要求的性能，并且特别适合于海量数据集应用。这项研究在多个抽象层面上进行。它考虑了保证或排除这类算法的表示类的一般因素，它考虑了特定公共表示类的算法，并找到了适用于特定常见(和不同)应用的算法，例如偏微分方程组的解、图像处理和数据库查询优化。在过去的十年中，数据收集机制的急剧增加，以及依赖于科学和几何建模的应用对更精细的数据分析的需求不断增加。每天，在医学成像、监视和科学获取中都会产生数百万个大数据集。此外，互联网已经成为一个容量巨大的通信媒介，产生了海量的交通数据集。这些数据集的有用性取决于我们有效处理它们的能力，无论是用于存储、传输、视觉显示、快速在线图形查询、关联，还是与来自其他医疗机构的数据进行配准。数据处理的当前技术水平远远不能提供新兴应用中所需的高效和忠实的表示。除了少数例外，以前的工作没有提供算法的效率或输出质量，尽管通常是通过实验验证的，但已经得到了严格和彻底的分析。研究人员进行基本的数学和算法研究，以显著提高我们处理和管理大型数据集的能力。这项研究在提供这一领域非常需要的严格算法结果方面取得了重大的数学进步。这项研究还通过高效的算法，在可分析的数据集的大小和可以执行的数据处理任务的类型方面做出了重大改进。最后，研究人员为海量数据处理应用程序创建了一个软件库。

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.