Methods and Applications of Analysis

Volume 18 (2011)

Number 1

Exact support recovery for linear inverse problems with sparsity constraints

Pages: 105 – 110

DOI: http://dx.doi.org/10.4310/MAA.2011.v18.n1.a7

Author

Dennis Trede (Zentrum für Technomathematik, Universität Bremen, Germany)

Abstract

There are a couple of methods with sparsity enhancing properties for regularization of inverse problems. This paper deals with the Tikhonov regularization with an ℓ1 penalty and with the orthogonal matching pursuit. Conditions are derived, which ensure that the regularized solution has the exact support. These conditions are especially applicable in the case of ill-posed problems, where other conditions based on coherence or the restricted isometry property are usually not applicable. Surprisingly, the conditions coincide for both, for the ℓ1-penalized Tikhonov regularization and for the orthogonal matching pursuit.

Keywords

inverse problems, ill-posed problems, sparsity constraints, exact recovery, Tikhonov regularization, greedy algorithm, orthogonal matching pursuit

2010 Mathematics Subject Classification

Primary 47A52, 65J20. Secondary 94A12.

Full Text (PDF format)