Sparse Recovery

With the increasing amount of information available, the cost of processing high-dimensional data becomes a critical issue. In order to reduce the model complexity, the concept of sparsity is widely used over last decades. Sparsity refers in this context to the requirement that most of the model parameters are equal or close to zero. As a relevant application, we mention the variable selection from econometrics, where zero entries correspond to irrelevant features. Another important application concerns the compressed sensing from signal processing, where just a few linear measurements are usually enough in order to decode sparse signals. In this chapter, the sparsity of a vector will be measured with respect to the zero norm. By using the latter, we state the problem of determining the sparsest vector subject to linear equality constraints. Its unique solvability in terms of spark of the constraint matrix is given. For gaining convexity, we substitute the zero norm by the Manhattan norm. The corresponding regularized optimization problem is known as basis pursuit. We show that the basis pursuit admits sparse solutions under the null space property of the underlying matrix. Further, a probabilistic technique of maximum a posteriori estimation is applied to derive the least absolute shrinkage and selection operator. This optimization problem is similar to the basis pursuit, but allows the application of efficient numerical schemes from convex optimization. We discuss the iterative shrinkage-thresholding algorithm for its solution.