Convergence rates in ℓ¹-regularization when the basis is not smooth enough

Abstract

Sparsity promoting regularization is an important technique for signal reconstruction and several other ill-posed problems. Theoretical investigation typically bases on the assumption that the unknown solution has a sparse representation with respect to a fixed basis. We drop this sparsity assumption and provide error estimates for nonsparse solutions. After discussing a result in this direction published earlier by one of the authors and co-authors, we prove a similar error estimate under weaker assumptions. Two examples illustrate that this set of weaker assumptions indeed covers additional situations which appear in applications.

Keywords:

• linear ill-posed problems
• Tikhonov-type regularization
• ℓ¹-regularization
• nonsmooth basis
• sparsity constraints
• convergence rates
• variational inequalities

AMS Subject Classifications:

• 65J20
• 47A52
• 49N45

Acknowledgments

The authors thank Bernd Hofmann for many valuable comments on a draft of this article and for fruitful discussions on the subject.

Notes

J. Flemming was supported by the German Science Foundation (DFG) under grant FL 832/1-1. M. Hegland was partially supported by the Technische Universität München Institute of Advanced Study, funded by the German Excellence Initiative. Work on this article was partially conducted during a stay of M. Hegland at TU Chemnitz, supported by the German Science Foundation (DFG) under grant HO 1454/8-1.

Dedicated to Professor Bernd Hofmann on the occasion of his 60th birthday