(See past events)
Master's Thesis Defense
Christian Verghese, SLU
A Survey of Deterministic and Probabilistic Methods in Compressive Sensing.
Compressive sensing is an area of mathematics concerning the recovery of sparse signals from a small number of linear measurements. This recovery problem naturally involves an underdetermined system of linear equations. The main goal in solving this system is to design a collection of measurements that distinguishes any pair of sparse vectors and permits efficient recovery. One significant finding in compressive sensing is that the number of measurements required for successful recovery depends on the sparsity of the signal considered. A well-known condition featured in the literature is the restricted isometry property, which is a sufficient condition for sparse recovery. There is no explicit method for constructing arbitrarily large measurement matrices with the restricted isometry property; however, families of random matrices have been shown to satisfy this property with high probability.
This thesis is expository in nature and surveys these breakthroughs in compressive sensing. The first part analyzes two sufficient conditions on the measurement matrix for successful reconstruction of a sparse signal. In particular, it is shown that a measurement matrix with sufficiently low restricted isometry property satisfies the robust null space property, which guarantees sparse vector recovery. The second part of the thesis explores the construction of suitable measurement matrices by employing probabilistic methods. The focus here is to illustrate that suitable random matrices with a relatively small number of measurements lead to sparse recovery with high probability.