Further Results on Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise

Sparse overcomplete representations have attracted much interest recently for their applications to signal processing. In a recent work, Donoho, Elad, and Temlyakov (2006) showed that, assuming sufficient sparsity of the ideal underlying signal and approximate orthogonality of the overcomplete dictionary, the sparsest representation can be found, at least approximately if not exactly, by either an orthogonal greedy algorithm or by l(1)-norrn minimization subject to a noise tolerance constraint. In this paper, we sharpen the approximation bounds under more relaxed conditions. We also derive analogous results for a stepwise projection algorithm.