A Tutorial Introduction Compressed Sensing

In this half-day tutorial, the author will present an introduction to the field of compressed sensing. Compressed sensing refers to the recovery of high-dimensional but low-complexity objects from a small number of linear measurements. The most popular applications of compressed sensing are (i) the recovery of high-dimensional but sparse vectors, when the locations of the nonzero components are unknown, and (ii) the recovery of high-dimensional but low rank matrices. This half-day tutorial will cover some of the most recent results in both problems. Until recently, both problems were addressed through the method of random projections. However, recent research has focused on deterministic methods for determining the measurement operators, especially the use of binary measurement matrices. The recent approaches often require fewer measurements and also orders of magnitude faster. In this tutorial the theoretical methods will be presented, and their application will be illustrated through Matlab codes which will be freely available from the author.