Exact support recovery for linear inverse problems with sparsity constraints

There are a couple of methods with sparsity enhancing properties for regularization of inverse problems. This paper deals with the Tikhonov regularization with an ℓ¹ 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 ℓ¹-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)

Published 27 April 2011