Frame builder: Greedy construction principles for near-optimal signal sparsification, transmission and recovery

University Of Houston, Houston TX

Investigators

Abstract

Bodmann DMS-1412524 The last decades have seen an explosive growth in the amount of digitized analog data being generated by high-resolution sensing devices and transmitted by communications infrastructure. High-resolution data is acquired for example in medical imaging in the form of MRI or CT scans or confocal microscopy, and in defense-related imaging as hyperspectral satellite images. The development of compressed sensing in applied mathematics has shown us that, surprisingly, randomly organized measurements provide a means to reduce the amount of data acquired by the sensor at the cost of invoking a nonlinear post-processing stage. The randomization strategies from compressed sensing are also relevant for generating codes and check sums that permit the recovery from sparse errors when transmitting a digitized analog signal. However, even at the level of state-of-the-art mathematical theory, random sensing and encoding precludes performance guarantees needed in critical situations. This project provides an alternative to random choice: Frames, which describe the structure of the measurements obtained with a sensor, are built in a step-by-step, incremental fashion. In order to realize provable performance guarantees, each step proceeds according to "greedy" optimization principles. A main application of this measurement design is image recovery from limited acquisition in region-of-interest computed tomography. The ability to perform accurate reconstruction of tissue density in a region of interest with limited scanning presents several potential advantages, including the reduction of radiation dose and the shortening of scanning time. More generally, the efficient parsing of signals according to this strategy has potential relevance for microarray data processing, motion segmentation, and many other data-intensive applications. The same greedy construction principles can be applied to the encoded transmission of digitized analog data, which is important for communication systems such as the internet. The solution to near-optimal error suppression for data loss would impact the quality of streaming media sent across the internet, or of wireless audio or video communications in unreliable environments. Parts of this project can be formulated at undergraduate or graduate-level research. The investigator trains at least two graduate students and one undergraduate student in the course of this project. The students are expected to gain valuable knowledge through the combination of theoretical work and the application to computed tomography. Compressed sensing has shown us how to reduce bandwidth by randomized sensing, which captures the essential part of a compressible signal directly, and by moving the burden of signal recovery from the sensor to a digital post-processing stage. The same techniques are useful for model selection such as subspace clustering and for correcting sparse errors such as partial data loss in transmissions. However, we still face challenging unresolved problems in signal acquisition and transmission. The gap between the relevant dimensions required to give near-certain success of a random construction is often far removed from practical situations. Moreover, there is no feasible known test that guarantees that a concrete outcome of a random construction is successful. This project addresses the need for provable performance guarantees of data acquisition and transmission in the following settings: (1) If a source for random signals concentrates near a union of subspaces, how can these subspaces be identified efficiently and reliably from noisy samples of the source? (2) If one expects communication failures when sending a digitized analog signal, resulting in a lost portion of the transmitted data, then how can the signal be encoded in order to suppress the impact of the data loss on the reconstructed analog signal in a near-optimal way? The project involves elements from convex optimization theory, functional and numerical analysis, and frame theory. A frame is an (over)complete family of vectors that provides stable expansions. Frame theory is important for sensing and digitized communications because in contrast to orthonormal bases, frames can incorporate linear dependencies between frame vectors, which allows for flexibility in their design and provides a fundamental method of error correction. Until recently, the state of the art of frame theoretic results relied on either randomized or group-representation constructions. This project focuses on an incremental, step-by-step design of near-optimal frames by greedy construction principles that are inspired by a technique developed by Daniel Spielman in works with Nikhil Srivastava and Adam Marcus. This technique has powerful applications, as shown in the recent simplified proof of the Bourgain-Tzafriri theorem and in the resolution of the Kadison-Singer problem. The expected outcomes of the project include the construction of frames by greedy methods that provide (1) sparse expansions for signals with known statistics and (2) error-correction capabilities for encoded transmissions that match the performance of randomized constructions. These construction methods are applied to region-of-interest computed tomography, an intentional data reduction strategy in which only X-rays are used that pass in the vicinity of an organ that is being imaged, thereby reducing the overall radiation dose. The successful implementation of greedy methods in frame design is also expected to have a significant impact on all tasks that involve analog signals being transmitted or interpreted in the presence of noise. The investigator trains at least two graduate students and one undergraduate student in the course of this project.