Necessary and Sufficient Conditions for Linear Convergence of l1-Regularization

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 l(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 unconstrained 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 ban 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. (C) 2010 Wiley Periodicals, Inc.