ABSTRACT
In this chapter, we discuss applications of `1-based relaxation to problems of signal recovery and approximation. Our focus is the role played by sparsity in signal representation and approximation, and the use of `1-methods for exploiting this sparsity for solving problems like signal denoising, compression, and approximation. We begin by illustrating that many classes of “natural” signals are sparse when represented in suitable bases, such as those afforded by wavelets and other multiscale transforms. We illustrate how such sparsity can be exploited for compression and denoising in orthogonal bases. Next we discuss the problem of signal approximation in overcomplete bases, and the role of `1-relaxation in finding near-optimal approximations. Finally, we discuss the method of compressed sensing for recovering sparse signals. It is a combination of two ideas: taking measurements of signals via random projections, and solving a lasso-type problem for reconstruction.
