We study \(l_0\) -synthesis/analysis methods and the thresholding-based algorithms for the dictionary-sparse recovery from a few linear measurements perturbed with Gaussian noise. Assuming that the measurement system satisfies a common restricted isometry property adapted to a dictionary condition ( \({\textbf{D}}\) -RIP), we first prove optimally stable recovery results for the least squares minimization, either with a coefficient-sparsity constraint or with an analysis-sparsity constraint. We then propose heavy-ball iterative hard thresholding algorithms adapted to a dictionary ( \({\textbf{D}}\) -HBIHT). We show that under \({\textbf{D}}\) -RIP condition, after a finite number of iterations, \({\textbf{D}}\) -HBIHT and \({\textbf{D}}\) -HTP (hard thresholding pursuit adapted to a dictionary) yield a solution that achieves nearly optimal error bounds. We finally extend the \({\textbf{D}}\) -HBIHT and its analysis to compressed data separation, which shows that one can approximately reconstruct the signal’s two distinct sub-components from its compressed linear measurements via HBIHT adapted to two dictionaries, provided that the measurement system satisfies a RIP condition adapted to a composed dictionary and the two different dictionaries satisfy a mutual coherence between them.
