Sparse Recovery

Vladimir Shikhman () and David Müller ()
Additional contact information
Vladimir Shikhman: Chemnitz University of Technology
David Müller: Chemnitz University of Technology

Chapter 7 in Mathematical Foundations of Big Data Analytics, 2021, pp 131-148 from Springer

Abstract: Abstract 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.

Date: 2021
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-62521-7_7

Ordering information: This item can be ordered from
http://www.springer.com/9783662625217

DOI: 10.1007/978-3-662-62521-7_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().