RUI: Efficient Algorithms for Compressed Sensing and Matrix Completion

Grinnell College, Grinnell IA

Investigators

Abstract

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.