We propose and analyze acceleration schemes for hard thresholding methods with applications to sparse approximation in linear inverse systems. Our acceleration schemes fuse combinatorial, sparse projection algorithms with convex optimization algebra to provide computationally efficient and robust sparse recovery methods. We compare and contrast the (dis) advantages of the proposed schemes with the state-of-the-art, not only within hard thresholding methods, but also within convex sparse recovery algorithms.