close this window
Linear Convergence Rates of l1-Regularization
first name:
In this talk we study the stable solution of ill-posed equations

Ax = y

where A : XY is a linear operator between Hilbert spaces X and Y . If this equation
is ill-posed, then the solution does not depend continuously on the data
y. In order to stably solve the equation, stabilization methods have to be applied. The most widely used stabilization technique is Tikhonov regularization

Τy(x) := ||Ax-y||2 + αR(x) → min.

Here R is a penalty functional and α > 0 is the regularization parameter.

In the recent years - motivated by the success of compresses sensing - the
use of l1 penalty

R(x) = ||x||l1 := λ ∈ Λ|<φλ,x>| 

became very popular.(Here (φλ)λ ∈ Λ is some basis of X.) In this talk we study Tikhonov regularization with l1 penalty term. In particular, we show that the range condition (ran(A*) ∩ R(x+) ≠ ∅) together with a certain injectivity condition allows linear error estimates (convergence rates) between the solution
x+ and minimizers of Τα,y. Moreover, we show that the range condition is even necessary for this linear convergence rate. This is talk is based on joint work with M. Grasmair and O. Scherzer.

  • M. Grasmair, M. Haltmeier, and O. Scherzer. Necessary and sufficient conditions
    for linear convergence of l1-regularization. Reports of FSP S105 - \"Photoacoustic Imaging\" 18, University of Innsbruck, Austria, 2009.