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.