This paper provides theoretical guarantees for denoising per-formance of greedy-like methods. Those include Compres-sive Sampling Matching Pursuit (CoSaMP), Subspace Pur-suit (SP), and Iterative Hard Thresholding (IHT). Our resultsshow that the denoising obtained with these algorithms isa constant and a log-factor away from the oracle's perfor-mance, if the signal's representation is sufficiently sparse.Turning to practice, we show how to convert these algorithmsto work without knowing the target cardinality, and insteadconstrain the solution to an error-budget. Denoising tests onsynthetic data and image patches show the potential in thisstagewise technique as a replacement of the classical OMP.