Adaptive Methods And Theory For Sparse Signal Recovery

The study of sparsity has recently been given tremendous attention within the signal processing community. Sparsity is the simple notion that a high dimensional signal or vector can be well represented by a relatively small number of coefficients; sparse signals arise in communications, coding, remote sensing, imaging, biology, medicine, and many more. Adaptivity, the ability to change behavior based on input from the environment, has long been recognized by engineers as a means to improve performance. The focus of this thesis is development of adaptive measurement techniques and theory for sparse signal recovery problems. Surprisingly, adaptive measurement systems can drastically improve performance by reducing the signal noise ratio (SNR) needed for successful inference of a sparse signal. The first portion of this thesis comprises contributions to the study of multiple-testing and sparse recovery problems from the perspective of sequential analysis. We propose a simple yet powerful adaptive procedure termed Sequential Thresholding, which can succeed with a relatively small number of adaptive measurements. We develop the fundamental performance limits of adaptive testing in this setting, and prove the asymptotic optimality of Sequential Thresholding. We then transition to the field of compressive sensing. In this setting we develop an adaptive, compressive, search procedure that is provably optimal in terms of dependence on SNR for a certain class of sparse signals. The fourth chapter of this thesis focuses on a problem termed the search across multiple populations. Here, sparsity manifests itself as the rare occurrence of some `atypical' statistical population. A general theory is developed, with tight upper and lower bounds on the number of samples required to find such an atypical population. Instantiating the general theory results in the tightest known bounds for some well-studied problems. Lastly, this thesis focuses on the problem of non-coherent signal detection in multipath fading channels. Here, the signaling duration and bandwidth of the transmit signal are adapted to exploit the statistical behavior of the wireless environment. Sparsity arises as bandwidth and signaling duration become large.