Sparse Regularization
Regularization with sparsity constraints is an impressingly effective method for the solution of linear operator equations on Hilbert spaces, where the solution is assumed to have a sparse representation with respect to a given Hilbert space basis. Classical (linear) regularization methods apply a quadratic regularization term, which leads to a large number of insignificant coefficients in the expansion of the solution. In order to put more emphasis on the significant terms, one increases the penalization of small coefficients by applying a regularization term with subquadratic growth near zero. In case the growth is at least linear, one can show that the minimizer of the Tikhonov functional, that is, the regularized solution, is indeed sparse in the sense that at most finitely many coefficients are non-zero.
From the theoretical point of view, one of the most interesting properties of sparse regularization is the virtual absence of bounds on convergence rates. While the convergence rates for quadratic regularization are known to never exceed the order of $\delta^{2/3}$ (apart from trivial cases), one can show that regularization terms with linear or sublinear growth near zero can lead to rates of order $\delta$. In other words, the error of the approximate solution is of the same order as the data error.
 |
 |
 |
Contributors:
Markus Grasmair, Markus Haltmeier, Otmar Scherzer
References:
- [1] M. Grasmair; Non-convex sparse regularisation. J. Math. Anal. Appl., 365, 19–28, 2010.
- [2] M. Grasmair; Well-posedness and convergence rates for sparse regularization with sublinear $l^q$ penalty term. Inverse Probl. Imaging, 3(3):383-387, 2009.
- [3] M. Grasmair, M. Haltmeier, and O. Scherzer; Sparse regularization with $l^q$ penalty term. Inverse Probl., 24(5):055020 (13pp), 2008.
- [4] M. Grasmair, M. Haltmeier, and O. Scherzer; Necessary and sufficient conditions for linear convergence of $\ell^1$-regularization. Reports of FSP S105 - 'Photoacoustic Imaging' 18, University of Innsbruck, Austria, August 2009. Submitted.
- [5] M. Grasmair, M. Haltmeier, and O. Scherzer; The residual method for regularizing ill-posed problems. Reports of FSP S105 - 'Photoacoustic Imaging' 14, University of Innsbruck, Austria, May 2009. Submitted.