Dictionary-sparse recovery via thresholding-based algorithms (Q5964229)

Compressive sensing is nowadays a well known term designating an efficient procedure for recovering a signal from its samples. It is applied in a variety of domains such as photography, computed tomography and so on, allowing reconstructing a signal from its samples in a better way than it is predicted by the Shannon theory. It is obvious that such an approach can be fitted to a class of signals having some prescribed properties, namely that of having a small number of nonzero components (sparsity) and a special norm inequality (restricted isometry property, as E. Candes named it). The signal to be analyzed is represented via a special matrix, the so called dictionary or design matrix. It is clear that a great interest was directed to generate adequate algorithms to obtain the optimum solution. The present paper compares the so called thresholding algorithms, namely the iterative hard thresholding one and the hard thresholding pursuit one, and shows that they provide the same theoretical guarantee as \(\ell_1\)-recovery from imperfect compressive measurements for signals that can be represented as expansions in a fixed dictionary. The paper is a rigorous exposition of all the theorems and we think it represents a valuable contribution in the area of algorithms for compressive sensing.