𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Necessary and sufficient conditions for linear convergence of ℓ1-regularization

✍ Scribed by Markus Grasmair; Otmar Scherzer; Markus Haltmeier


Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
196 KB
Volume
64
Category
Article
ISSN
0010-3640

No coin nor oath required. For personal study only.

✦ Synopsis


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 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 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.


📜 SIMILAR VOLUMES


A necessary and sufficient condition for
✍ Lin, Chiang; Shyu, Tay-Woei 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

In this paper w e prove the following result. Let ml 2 m2 2 ... 2 ml be nonnegative integers. A necessary and sufficient condition for the complete graph K,, to be decomposed into stars S,,, , S

Necessary and sufficient conditions for
✍ Robert N. Shorten; Kumpati S. Narendra 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB 👁 2 views

## Abstract In this paper, necessary and sufficient conditions are derived for the existence of a common quadra‐tic Lyapunov function for a finite number of stable second order linear time‐invariant systems. Copyright © 2002 John Wiley & Sons, Ltd.

A necessary and sufficient condition for
✍ Zhou Huai-Lu 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K,,-free graph is k-hamiltonian if and only if it is (k + 2)-connected ( k L 1). We use [ 11 for basic terminology and notation, and consider simple graphs only. Let G be a graph. By V(G) and E(G) we denote,