Premium
Necessary and sufficient conditions for linear convergence of ℓ 1 ‐regularization
Author(s) -
Grasmair Markus,
Scherzer Otmar,
Haltmeier Markus
Publication year - 2011
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.20350
Subject(s) - tikhonov regularization , backus–gilbert method , regularization (linguistics) , mathematics , inverse problem , regularization perspectives on support vector machines , rate of convergence , a priori and a posteriori , mathematical optimization , mathematical analysis , computer science , key (lock) , artificial intelligence , philosophy , computer security , epistemology
Motivated by the theoretical and practical results in compressed sensing, efforts have been undertaken by the inverse problems community to derive analogous results, for instance linear convergence rates, for Tikhonov regularization with ℓ 1 ‐penalty term for the solution of ill‐posed equations. Conceptually, the main difference between these two fields is that regularization in general is an uncon strained optimization problem, while in compressed sensing a constrained one is used. Since the two methods have been developed in two different communities, the theoretical approaches to them appear to be rather different: In compressed sensing, the restricted isometry property seems to be central for proving linear convergence rates, whereas in regularization theory range or source conditions are imposed. The paper gives a common meaning to the seemingly different conditions and puts them into perspective with the conditions from the respective other community. A particularly important observation is that the range condition together with an injectivity condition is weaker than the restricted isometry property. Under the weaker conditions, linear convergence rates can be proven for compressed sensing and for Tikhonov regularization. Thus existing results from the literature can be improved based on a unified analysis. In particular, the range condition is shown to be the weakest possible condition that permits the derivation of linear convergence rates for Tikhonov regularization with a priori parameter choice. © 2010 Wiley Periodicals, Inc.