Compressive Computation: Novel Algorithms for Computation with Compressively Sensed Data

Kaslovsky Daniel N, Boulder CO

Investigators

Abstract

This project will provide the scientific community with new tools for analyzing large and complex data sets though the design and implementation of new algorithms using compressive sensing. While typically complex and high-dimensional, modern data sets often have a concise underlying structure. Compressive sensing is a new data-acquisition paradigm that allows sparse data to be randomly undersampled without sacrificing reconstruction accuracy. Compressive sensing relies on theoretical results that allow for an overwhelming majority of the information content in sparse data to be captured from a relatively small number of random measurements. Recent advances in the core cyberinfrastructure areas of computation and data analysis have demonstrated that efficient matrix computations may also be realized through randomized techniques. Based on the same theoretical underpinnings, the success of both compressive sampling and randomized numerical linear algebra suggest a new framework by which random sampling can be integrated into data acquisition and processing for new, highly efficient, computational algorithms. As randomized matrix operations are amenable to parallelization, such algorithms may achieve further efficiency from modern multi-processor architectures. The main research objective of this work is the design of both structured sensing matrices and new randomized computational algorithms for processing compressively sensed data. A careful theoretical study will result in understanding how mathematical operations on compressed samples may be used to manipulate the data from which the samples were acquired. With this understanding, algorithms will be designed for integrating the compressive sensing acquisition process with randomized numerical matrix computations. Massive amounts of data are produced by a wide range of scientific disciplines (e.g., genomics, astrophysics, internet and network analysis) as well as by commerce and industry (e.g., inventory databases, consumer behavior tracking). New algorithms for efficient processing of such data may therefore realize both economic and scientific impact. As compressing sensing is particularly applicable to imaging, the medical community stands to benefit from the results of this research through reduced image acquisition times and faster diagnoses from novel computation. The theoretical advances that will result from this proposal are applicable to other mathematical areas such as numerical analysis and computational harmonic analysis. The algorithms from this work will be implemented in high-quality code made publicly available to the general scientific community.