Practical Compressed Sensing

Traditional signal processing schemes sample signals at a high rate and immediately discard most of the information during the compression process. By exploiting the fact that most practical signals are sparse, compressed sensing offers an alternative framework for signal acquisition that directly senses the data in compressed form using few nonadaptive, linear measurements. Reconstruction algorithms, as well as the kind of measurements, that provide tractable and robust signal recovery are well understood. However, traditional compressed sensing approaches still provide little theory and algorithms for many practical problems. This work aims to fill that gap. Combining known greedy reconstruction algorithms and stochastic gradient descent methods, two algorithms are proposed for solving a generalized sparse reconstruction problem. These stochastic greedy algorithms possess favorable properties in large-scale applications and have provable convergence guarantees that often outperform their deterministic counterparts. In another direction, adaptive measurement strategies are examined, which select the next measurement based on previous observations. This is contrasted with traditional compressed sensing, where measurements are nonadaptive and fixed prior to signal acquisition. Adaptive sensing significantly improves signal recovery when arbitrary linear measurements can be constructed. However, in practice, the types of measurements that can be acquired are limited. The limitations and advantages of adaptive sensing are demonstrated when the measurements belong to a finite set of allowable measurement vectors, and a practical sampling scheme is proposed to select measurements that are adapted to the signal support. Finally, prior signal information is available in many applications and can be exploited during the signal reconstruction. The recovery conditions and associated recovery guarantees of weighted L1-minimization are provided when arbitrary prior information is available.