The problem of estimating a high-dimensional signal based on an incomplete set of noisy observations has broad applications. In remote sensing, network traffic measurement, and computational biology, the observation process makes it difficult or costly to obtain sample sizes larger than the ambient signal dimension. Signal recovery is in general intractable when the dimension of the signal is much larger than the number of observations. However, efficient recovery methods have been developed by imposing a sparsity constraint on the signal. There are different ways to impose sparsity, which has given rise to a diverse set of problems in sparse approximation, subset selection in regression, and graphical model selection.

This thesis makes several contributions. First, we examine the role of sparsity in the measurement matrix, representing the linear observation process through which we sample the signal. We develop a fast algorithm for approximation of compressible signals based on sparse random projections, where the signal is assumed to be well-approximated by a sparse vector in an orthonormal transform. We propose a novel distributed algorithm based on sparse random projections that enables refinable approximation in large-scale sensor networks. Furthermore, we analyze the information-theoretic limits of the sparse recovery problem, and study the effect of using dense versus sparse measurement matrices. Our analysis reveals that there is a fundamental limit on how sparse we can make the measurements before the number of observations required for recovery increases significantly. Finally, we develop a general framework for deriving information-theoretic lower bounds for sparse recovery. We use these methods to obtain sharp characterizations of the fundamental limits of sparse signal recovery and sparse graphical model selection.