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.