  Compressive sensing is a technique to sample signals well below the Nyquist
rate using linear measurement operators. In this paper we present an algorithm
for signal reconstruction given such a set of measurements. This algorithm
generalises and extends previous iterative hard thresholding algorithms and we
give sufficient conditions for successful reconstruction of the original data
signal. In addition we show that by underestimating the sparsity of the data
signal we can increase the success rate of the algorithm.
  We also present a number of modifications to this algorithm: the
incorporation of a least squares step, polynomial acceleration and an adaptive
method for choosing the step-length. These modified algorithms converge to the
correct solution under similar conditions to the original un-modified
algorithm. Empirical evidence show that these modifications dramatically
increase both the success rate and the rate of convergence, and can outperform
other algorithms previously used for signal reconstruction in compressive
sensing.
