ABSTRACT
This chapter provides an overview of different solution strategies to the compressed sensing problems, and presents the basic results about which properties the measurement matrix has to have in order for those strategies to succeed. It discusses the case of the matrix being chosen at random. Compressed sensing is changing the way engineers and researchers from other application areas are thinking about signal processing. The chapter also discusses applications of the theory of compressed sensing, and some generalizations of compressed sensing. In compressed sensing problems, the number of steps is typically equal to the sparsity level. The greedy algorithms have the advantage of being very fast and easy to implement. The key idea of greedy algorithms is to first identify some subset in support of the original signal and then refine it in a number of steps until a good estimate of the support is found.
