Author Archives: Marc Nicodeme

Study of sparse methods for tomography

As part of tomography with a limited number of angles, the resulting inverse problem is ill-conditioned. The algorithms “classic”, analytic and algebraic produce many artifacts. The optimization methods solve this problem by using a regularization. In my work, I guess the parsimonious or sparse images in a given representation. A sparse image is an image that has few non-zero components. To promote this parsimony, I will rectify the problem with a standard \ell^1 and solve one of the two equivalent problems below.

(1)   \begin{equation*} \underset{x\in \mathbb{R}^n}{\text{min}}\ \|x\|_1 \text{ s.t. } \|\mathbf{A}x-y\|_2\le \delta \end{equation*}

(2)   \begin{equation*} \underset{x\in \mathbb{R}^n}{\text{min}}\ \frac{1}{2}\|\mathbf{A}x-y\|_2 + \lambda \|x\|_1 \end{equation*}

My job is to assess the theoretical limits of these problems while being the closest to reality. Recent studies [3] have highlighted sufficient conditions ensuring the reconstruction of the image by minimizing \ell^1 and provide an error of this reconstruction [1]. These conditions require the existence of a particular vector called dual certificate . Depending on the application, it may be possible to calculate a candidate who will be a conditional dual certificate [2,4].

This work primarily cover the construction of such candidates. I propose in my work, a greedy approach to calculate a candidate who is a dual certificate for almost all images “rebuildable” and minimizing the theoretical reconstruction error.

[1] Charles Dossal and Remi Tesson. Consistency of l1 recovery from noisy deterministic measurements. Applied and Computational Harmonic Analysis, 2013.

[2] Jean-Jacques Fuchs. Recovery of exact sparse representations in the presence of bounded noise. Information Theory, IEEE Transactions on, 51(10) :3601–3608, 2005.

[3] Markus Grasmair, Otmar Scherzer, and Markus Haltmeier. Necessary and sufficient conditions for linear convergence of l1-regularization. Commun. Pure and Appl. Math., 64(2) :161–182, 2011.

[4] Samuel Vaiter, Gabriel Peyré, Charles Dossal, and Jalal Fadili. Robust sparse analysis regularization. 2011.