Ph.D Thesis

Ph.D StudentGiryes Raja
SubjectSparsity Models for Signals: Theory and Applications
DepartmentDepartment of Computer Science
Supervisor PROF. Michael Elad
Full Thesis textFull thesis text - English Version


Many signal and image processing applications have benefited remarkably from the theory of sparse representations.

In its classical form this theory models signal as having a sparse representation under a given dictionary -- this is referred to as the "Synthesis Model". In this work we focus on greedy methods for the problem of recovering a signal from a set of deteriorated linear measurements. We consider four different sparsity frameworks that extend the aforementioned synthesis model: (i) The cosparse analysis model; (ii) the signal space paradigm; (iii) the transform domain strategy; and (iv) the sparse Poisson noise model.

Our algorithms of interest in the first part of the work are the greedy-like schemes: CoSaMP, subspace pursuit (SP), iterative hard thresholding (IHT) and hard thresholding pursuit (HTP). It has been shown for the synthesis model that these have similar recovery guarantees like relaxation based techniques in the case that the noise is additive and adversarial. In this work we extend these results in several important ways:

(a) For the case that the noise is random white Gaussian we show that CoSaMP, SP and IHT achieve near-oracle performance, closing a gap between greedy algorithms and relaxation based techniques.

(b) We propose analysis variants for the greedy-like techniques. Assuming the availability of a near optimal projection scheme for the cosparse model, we provide performance guarantees for these algorithms.

(c) We consider the recovery performance in the synthesis framework when the signal, rather than the representation, is the objective. We develop new uniqueness and stability conditions along new algorithms that focus on the signal rather than the representation.

(d) One drawback of the results for the analysis greedy-like algorithms is that they do not hold for frames as the analysis dictionary, while the existing guarantees for relaxation based methods do cover frames. We propose a variant of IHT that operates in the analysis transform domain and provide guarantees that close this gap.

In the last part of our work we look at the Poisson denoising problem. We propose to harness sparse-representation modeling of image patches for this denoising task, handling severe SNR scenarios. We employ an exponential sparsity model, as recently proposed by Salmon et al., relying directly on the true noise statistics. Our scheme uses a greedy pursuit, with boot-strapping based stopping criterion, and dictionary learning within the denoising process, leading to state-of-the-art-results.