### Andrew Thompson (University of Edinburgh)

#### A new analysis of a gradient projection method for compressed sensing

*Wednesday 28 March 2012 at 15.30, JCMB 6206*

##### Abstract

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.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*