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

点击翻译按钮获取中文摘要

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.