Convergence rates and source conditions for Tikhonov regularization with sparsity constraints

By Dirk A. Lorenz. 2008

169 citations recorded by the source corpus.

Abstract This paper addresses the regularization by sparsity constraints by means of weighted ℓ p penalties for 0 ≤ p ≤ 2. For 1 ≤ p ≤ 2 special attention is payed to convergence rates in norm and to source conditions. As main results it is proven that one gets a convergence rate of in the 2-norm for 1 < p ≤ 2 and in the 1-norm for p = 1 as soon as the unknown solution is sparse. The case p = 1 needs a special technique where not only Bregman distances but also a so-called Bregman-Taylor distance has to be employed. For p < 1 only preliminary results are shown. These results indicate that, different from p ≥ 1, the regularizing properties depend on the interplay of the operator and the basis of sparsity. A counterexample for p = 0 shows that regularization need not to happen.

Subfields: Civil and Structural Engineering, Computational Mechanics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/80e94abf1923d0496c3e1db984d957609aa92717

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Civil and Structural Engineering

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Convergence and regularization results for optimal control problems with sparsity functional (2011, background): “Other source conditions as developed in [10,21] are not directly applicable, since they are tailored to the case (α, β) → (0, 0), while we are considering the convergence for α → 0 and fixed β.”
Linear Convergence of Iterative Soft-Thresholding (2007, unknown): “This property also plays a role in the performance analysis of Newton methods applied to minimization problems with sparsity constraints [21] and error estimates for ℓ 1 -regularization [24].”
Sparse regularization with lq penalty term (2008, unknown): “Similar results have been derived recently [20, 22].”
Necessary and sufficient conditions for linear convergence of ℓ1‐regularization (2011, methodology): “In the recent years, however, sparse regularization has been established as a powerful alternative to the standard methods [14, 1, 4, 23, 24, 28].”
Inverse problems in spaces of measures (2013, background): “This approach gives inverse problems in sequence spaces which have been extensively studied in terms of regularization and numerical algorithms [14, 27, 35, 3, 12, 7, 8, 6, 28, 22, 19, 33].”
An analysis of electrical impedance tomography with applications to Tikhonov regularization (2012, methodology): “This can be remedied by imposing extra conditions [24, 46].”
Regularization properties of the sequential discrepancy principle for Tikhonov regularization in Banach spaces (2014, unknown): “, [14, 22, 24, 28]).”