RUI: Large-scale Algorithm Analysis and GPU Implementations for Compressed Sensing and Matrix Completion

该项目考虑了两个及时的研究主题的融合：压缩感知和矩阵完成算法，以及使用图形处理单元（GPU）实现它们。压缩感知是信号处理中相对较新的范例，其中采集信号和压缩测量的行为被组合成单个操作。所获取的压缩测量的数量与信号的信息内容成比例，而不是像传统的那样等于信号的环境维度。 虽然测量的数量显著减少，导致方程的不确定系统，但是可以保证低复杂度的贪婪算法来重建对所测量的信号的准确近似，只要潜在的信号是稀疏的，即，仅具有几个重要分量。矩阵补全类似地利用了目标矩阵的简单性，目标矩阵只有几个独立的列;换句话说，从有限数量的测量中恢复低秩矩阵。典型应用包括压缩雷达、地球物理数据分析、医学成像和计算机视觉。然而，来自这些应用的数据集通常至少超出当前可用的模拟水平一个数量级。 通过使用GPU的计算能力，该项目提供了一个平台，可以克服计算障碍，并对超出当前经验测试机制三个数量级的问题进行必要的大规模测试。传统上，信号测量是通过获取信号中的每个分量，然后使用适当的计算算法压缩信号。 例如，数码相机捕获具有大量像素的图像，然后使用诸如JPEG的压缩方案来减小数字图像的大小以用于存储或传播。 在许多情况下，与测量相关的成本和挑战是相当大的。 在压缩感知和矩阵完备中，测量过程被改变以减少测量的数量，但是信号重构过程必然更加困难。 压缩感知和矩阵补全将测量过程的工作量转移到专用于信号重构的计算资源。 医学成像中的典型示例是磁共振成像（MRI），其中获得诊断水平MRI所需的时间导致患者不必要的不适，甚至导致儿科镇静。 压缩感知MRI已经证明了在一小部分时间内产生诊断口径图像的能力。 增加的计算负担需要快速、有效的算法，并且已经针对压缩感知引入或更新了许多这样的算法。 观察到的这些算法的性能是大大上级他们的悲观的理论保证，但这些算法的测试一直受到限制，他们施加的计算负担。在这个项目中，PI和合作者开发软件，能够通过开发新技术，并利用新架构与图形处理单元提供的计算性能增益，从压缩测量提供近实时信号重建。由此产生的软件确认旨在为从业者提供最适合应用的算法选择指南。 PI机构的本科生有机会参与PI的研究，并在利用新的科学计算架构时面临挑战，但要实现收益。

This project considers the fusion of two timely research topics: algorithms for compressed sensing and matrix completion, and their implementation using graphical processing units (GPUs). Compressed sensing is a relatively new paradigm in signal processing where the acts of acquiring a signal and compressing the measurements are combined into a single operation. The number of compressed measurements acquired is proportional to the information content of the signal rather than, as is traditional, equal to the ambient dimension of the signal. Although the number of measurements is significantly reduced resulting in an undetermined system of equations, low-complexity greedy algorithms can be guaranteed to reconstruct an accurate approximation to the measured signal provided that the underlying signal was sparse, i.e. had only a few important components. Matrix completion similarly exploits the simplicity of the target matrix having only a few independent columns; in other words, one recovers a low rank matrix from a limited number of measurements. Typical applications include compressive radar, geophysical data analysis, medical imaging, and computer vision. The data sets from these applications are typically, however, at least an order of magnitude beyond the currently available simulation levels. By employing the computational power of GPUs this project provides a platform for overcoming computational barriers and the necessary large-scale testing on problems up to three orders of magnitude beyond current empirical testing regimes.Traditionally, a signal is measured by acquiring every component in the signal and then compressing the signal with an appropriate computational algorithm. For example, digital cameras capture an image with a huge number of pixels and then a compression scheme such as JPEG is used to reduce the size of the digital image for storage or dissemination. In many cases, the costs and challenges associated with taking measurements are considerable. In compressed sensing and matrix completion, the measurement process is altered in order to reduce the number of measurements but the signal reconstruction process is necessarily more difficult. Compressed sensing and matrix completion transfer the workload from the measurement process to computational resources dedicated to the signal reconstruction. A typical example in medical imaging is magnetic resonance imaging (MRI) where the time required to obtain a diagnostic level MRI causes unnecessary discomfort for patients and even pediatric sedation. Compressed sensing MRI has demonstrated the ability to produce diagnostic caliber images in a fraction of the time. The increased computational burden requires fast, efficient algorithms and many such algorithms have been introduced or updated for compressed sensing. The observed performance of these algorithms is substantially superior to their pessimistic theoretical guarantees, but testing of these algorithms has been constrained by their imposed computational burden. In this project, the PI and collaborators develop software capable of providing near real-time signal reconstruction from compressed measurements through development of new techniques, and by exploiting the computational performance gains offered by new architectures with graphical processing units. The resulting software validation is aimed to provide practioners with guidance on algorithm choice most appropriate to the application. Undergraduate students at the PI's institution have the opportunity to participate in the PI's research and are exposed to the challenges presented, but gains to be achieved, when exploiting new scientific computing architectures.