We consider the problem of recovering sparse vectors using a small number of
fixed linear measurements. We propose a partial hard-thresholding operator
that
leads to a family of iterative algorithms. One extreme of the family yields
well
known hard thresholding algorithms while the other extreme leads to a new
algorithm that we call Orthogonal Matching Pursuit with Replacement (OMPR).
OMPR, like OMP, adds exactly one coordinate at each iteration but, unlike OMP,
OMPR also removes one coordinate. This simple change allows us to prove that
OMPR has the best known guarantees for sparse recovery in terms of RIP. Our
proof techniques are novel and flexible enough to also permit the tightest
known
analysis of popular iterative algorithms like CoSaMP and Subspace Pursuit.