Dictionary Sparse Recovery via Thresholding Based Algorithms
It is shown that the iterative hard thresholding and hard thresholding pursuit algorithms provide the same theoretical guarantees as \ell _1$$l1 minimization for the recovery from imperfect compressive measurements of signals that have almost sparse analysis expansions in a fixed dictionary. Unlike other signal space algorithms targeting the recovery of signals with sparse synthesis expansions, the ability to compute (near) best approximations by synthesis sparse signals is not necessary. The results are first established for tight frame dictionaries, before being extended to arbitrary dictionaries modulo an adjustment of the measurement process.