RUI: Efficient Algorithms for Compressed Sensing and Matrix Completion

传统的测量信号的方法是获取信号中的每个分量，然后用适当的计算算法对信号进行压缩。例如，数码相机捕获具有大量像素的图像，然后使用JPEG等压缩方案来减小数字图像的大小，以便存储或传播。在许多应用中，与获取测量值相关的成本和挑战是相当大的。在压缩感知和矩阵补全中，为了大幅减少测量次数，测量过程被改变，但信号重建过程必然更加困难。压缩感知和矩阵补全将测量过程的工作量转移到专用于信号重建的计算资源上。典型的应用包括压缩雷达、地球物理数据分析、医学成像和计算机视觉。该项目将采用整体方法进行压缩传感和矩阵完成的数据采集和算法开发，其中理论保证通常依赖于计算昂贵的子程序，并适用于计算繁重的测量过程。通过稀疏的测量算子、迭代贪心算法中宽松的子程序要求以及这些算法在计算加速硬件上的实现，可以提高效率。压缩感知将信号采集和压缩的行为结合成一个单一的操作。计算效率高的算法然后通过利用信号具有相对较少的重要组成部分的潜在简单性来产生稀疏信号的精确近似值。矩阵补全同样利用了目标矩阵只有几个独立列的简单性；换句话说，从有限数量的测量中恢复一个低秩矩阵。虽然用于压缩感知和矩阵补全的贪婪算法在理论上保证了精确恢复底层低维信号所需的测量次数，但这些保证需要的测量量远远超过实际应用。此外，许多算法采用理论上有用但计算代价昂贵的子程序。观察到的计算效率更高的测量操作员的性能，鼓励在实践中采用缺乏最坏情况的技术，统一的获取和重建保证。该项目旨在平衡理论保证和快速高效算法的竞争欲望。该项目将追求理论上可行的算法，这些算法在实践中也很有用，并在合理的计算工作量（包括功率、时间和负担得起的硬件）下提供线性逆问题的解决方案。同时，建立计算效率高但缺乏精确保证的测量算子和恢复算法的经验性能特征，有助于指导从业者和理论家今后的研究。为了为这些计算密集型算法提供接近实时的解决方案，该项目还将通过设计和传播利用高性能计算图形处理单元上可用的大规模并行计算的算法实现来进一步加速计算。

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 applications, the costs and challenges associated with acquiring measurements are considerable. In compressed sensing and matrix completion, the measurement process is altered in order to drastically 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. Typical applications include compressive radar, geophysical data analysis, medical imaging, and computer vision. This project will take a holistic approach to data acquisition and algorithm development for compressed sensing and matrix completion where theoretical guarantees often rely on computationally expensive subroutines and apply to computationally burdensome measurement processes. Increased efficiency can be achieved through sparse measurement operators, relaxed subroutine requirements in iterative greedy algorithms, and the implementation of these algorithms on computation accelerating hardware.Compressed sensing combines the acts of signal acquisition and compression into a single operation. Computationally efficient algorithms then produce accurate approximations to sparse signals by exploiting the underlying simplicity that the signal has relatively 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. While leading greedy algorithms for compressed sensing and matrix completion have theoretical guarantees defining the number of measurements required for accurately recovering the underlying low dimensional signal, these guarantees require many more measurements than practical for applications. Furthermore, many of the algorithms employ theoretically useful but computationally expensive subroutines. Observed performance of more computationally efficient measurement operators encourages the adoption of techniques in practice that lack worst case, uniform guarantees for acquisition and reconstruction. This project seeks to balance the competing desires for theoretical guarantees and fast, efficient algorithms. The project will pursue theoretically viable algorithms which are also practically useful and provide solutions to linear inverse problems in reasonable amounts of computational effort including power, time, and affordable hardware. At the same time, establishing empirical performance characteristics for computationally efficient measurement operators and recovery algorithms which lack precise guarantees will help guide practitioners and theorists in future research. To provide near real time solutions to these computationally intensive algorithms, the project will also further accelerate computation by designing and disseminating algorithm implementations which exploit the massively parallel computations available on high performance computing graphics processing units.