  We present a new recovery analysis for a standard compressed sensing
algorithm, Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2008),
which considers the fixed points of the algorithm. In the context of arbitrary
measurement matrices, we derive a sufficient condition for convergence of IHT
to a fixed point and a necessary condition for the existence of fixed points.
These conditions allow us to perform a sparse signal recovery analysis in the
deterministic noiseless case by implying that the original sparse signal is the
unique fixed point and limit point of IHT, and in the case of Gaussian
measurement matrices and noise by generating a bound on the approximation error
of the IHT limit as a multiple of the noise level. By generalizing the notion
of fixed points, we extend our analysis to the variable stepsize Normalised IHT
(N-IHT) (Blumensath and Davies, 2010). For both stepsize schemes, we obtain
lower bounds on asymptotic phase transitions in a proportional-dimensional
framework, quantifying the sparsity/undersampling trade-off for which recovery
is guaranteed. Exploiting the reasonable average-case assumption that the
underlying signal and measurement matrix are independent, comparison with
previous results within this framework shows a substantial quantitative
improvement.
