Compressive Computation: Novel Algorithms for Computation with Compressively Sensed Data

该项目将通过设计和实施使用压缩传感的新算法，为科学界提供分析大型和复杂数据集的新工具。虽然通常情况下是复杂和高维的，但现代数据集通常具有简洁的底层结构。压缩感知是一种新的数据获取模式，它允许对稀疏数据进行随机欠采样，而不会牺牲重建精度。压缩感知依赖于理论结果，该结果允许从相对较少的随机测量中捕获稀疏数据中的绝大多数信息内容。计算和数据分析等核心网络基础设施领域的最新进展表明，也可以通过随机化技术实现有效的矩阵计算。基于相同的理论基础，压缩抽样和随机化数值线性代数的成功提出了一种新的框架，通过该框架，随机抽样可以集成到数据采集和处理中，以实现新的、高效的计算算法。由于随机化的矩阵运算易于并行化，这样的算法可能会从现代多处理器体系结构中获得更高的效率。这项工作的主要研究目标是设计结构化传感矩阵和处理压缩传感数据的新的随机化计算算法。仔细的理论研究将导致理解如何使用对压缩样本的数学运算来处理从中获取样本的数据。有了这样的理解，算法将被设计用于将压缩感知获取过程与随机数字矩阵计算相结合。大量数据由广泛的科学学科(例如，基因组学、天体物理学、互联网和网络分析)以及商业和工业(例如，库存数据库、消费者行为跟踪)产生。因此，有效处理这类数据的新算法可能会产生经济和科学影响。由于压缩感知特别适用于成像，医学界将从这项研究的结果中受益，因为它减少了图像采集时间，并从新的计算中更快地进行诊断。这一建议将带来的理论进步也适用于其他数学领域，如数值分析和计算调和分析。这项工作的算法将以高质量的代码实现，向普通科学界公开提供。

This project will provide the scientific community with new tools for analyzing large and complex data sets though the design and implementation of new algorithms using compressive sensing. While typically complex and high-dimensional, modern data sets often have a concise underlying structure. Compressive sensing is a new data-acquisition paradigm that allows sparse data to be randomly undersampled without sacrificing reconstruction accuracy. Compressive sensing relies on theoretical results that allow for an overwhelming majority of the information content in sparse data to be captured from a relatively small number of random measurements. Recent advances in the core cyberinfrastructure areas of computation and data analysis have demonstrated that efficient matrix computations may also be realized through randomized techniques. Based on the same theoretical underpinnings, the success of both compressive sampling and randomized numerical linear algebra suggest a new framework by which random sampling can be integrated into data acquisition and processing for new, highly efficient, computational algorithms. As randomized matrix operations are amenable to parallelization, such algorithms may achieve further efficiency from modern multi-processor architectures. The main research objective of this work is the design of both structured sensing matrices and new randomized computational algorithms for processing compressively sensed data. A careful theoretical study will result in understanding how mathematical operations on compressed samples may be used to manipulate the data from which the samples were acquired. With this understanding, algorithms will be designed for integrating the compressive sensing acquisition process with randomized numerical matrix computations.Massive amounts of data are produced by a wide range of scientific disciplines (e.g., genomics, astrophysics, internet and network analysis) as well as by commerce and industry (e.g., inventory databases, consumer behavior tracking). New algorithms for efficient processing of such data may therefore realize both economic and scientific impact. As compressing sensing is particularly applicable to imaging, the medical community stands to benefit from the results of this research through reduced image acquisition times and faster diagnoses from novel computation. The theoretical advances that will result from this proposal are applicable to other mathematical areas such as numerical analysis and computational harmonic analysis. The algorithms from this work will be implemented in high-quality code made publicly available to the general scientific community.