We present a novel analysis of a gradient projection algorithm, Iterative Hard Thresholding (IHT), for recovering sparse signals from undersampled measurements. By analysing the fixed points of IHT, we obtain a condition for general measurement matrices guaranteeing at most one fixed point, namely the original signal. We also give an improved requirement guaranteeing the algorithm's convergence to some fixed point. Thus, if both conditions are satisfied, we ensure recovery of the original signal. For the specific case of Gaussian measurement matrices and independent signals, comparison with existing worst-case results by means of the phase transition framework shows a substantial quantitative improvement.
In many applications, for example in image processing with wavelets, the original sparse signal may have additional structure which can be exploited in the recovery process. With this in mind, we extend our analysis to a variant of IHT adapted to the problem of recovering a signal whose wavelet coefficents have a rooted tree structure, which we call Iterative Tree Projection (ITP). By introducing a simplified phase transition framework, we obtain quantitative recovery results for ITP, also in the context of Gaussian matrices and independent signals.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
