ABSTRACT

Practical signals are usually structured, and the most useful signal structure is sparsity. Thus, a fundamental hypothesis in compressed sensing is that the unknown signal to recover is sparse or can be sparsely compressible. A vector is said to be sparse if it has a small number of non-zero entries, and a vector is said to be sparsely compressible if it can be approximated by a sparse vector. Under

the sparsity hypothesis, compressed sensing problems and many other problems can be formulated as the so-called sparse optimization problem which seeks the sparsest solution of an underdetermined linear system or, in more general, the sparsest point in a convex set.