Sparse over complete 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 over complete dictionary, the sparsest representation can be found, at least approximately if not exactly, by either an orthogonal greedy algorithm or by lscr1-norm 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.