## Quantitative analysis of algorithms for compressed signal recovery

##### Abstract

Compressed Sensing (CS) is an emerging paradigm in which signals are recovered from undersampled
nonadaptive linear measurements taken at a rate proportional to the signal's true
information content as opposed to its ambient dimension. The resulting problem consists in finding a sparse solution to an underdetermined system of linear equations. It has now been
established, both theoretically and empirically, that certain optimization algorithms are able
to solve such problems. Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2007),
which is the focus of this thesis, is an established CS recovery algorithm which is known to
be effective in practice, both in terms of recovery performance and computational efficiency.
However, theoretical analysis of IHT to date suffers from two drawbacks: state-of-the-art worst-case
recovery conditions have not yet been quantified in terms of the sparsity/undersampling
trade-off, and also there is a need for average-case analysis in order to understand the behaviour
of the algorithm in practice.
In this thesis, we present a new recovery analysis of IHT, which considers the fixed points of
the algorithm. In the context of arbitrary matrices, we derive a condition guaranteeing convergence
of IHT to a fixed point, and a condition guaranteeing that all fixed points are 'close' to
the underlying signal. If both conditions are satisfied, signal recovery is therefore guaranteed.
Next, we analyse these conditions in the case of Gaussian measurement matrices, exploiting
the realistic average-case assumption that the underlying signal and measurement matrix are
independent. We obtain asymptotic phase transitions in a proportional-dimensional framework,
quantifying the sparsity/undersampling trade-off for which recovery is guaranteed. By generalizing
the notion of xed points, we extend our analysis to the variable stepsize Normalised IHT
(NIHT) (Blumensath and Davies, 2010). For both stepsize schemes, comparison with previous
results within this framework shows a substantial quantitative improvement.
We also extend our analysis to a related algorithm which exploits the assumption that the
underlying signal exhibits tree-structured sparsity in a wavelet basis (Baraniuk et al., 2010).
We obtain recovery conditions for Gaussian matrices in a simplified proportional-dimensional
asymptotic, deriving bounds on the oversampling rate relative to the sparsity for which recovery
is guaranteed. Our results, which are the first in the phase transition framework for tree-based
CS, show a further significant improvement over results for the standard sparsity model. We
also propose a dynamic programming algorithm which is guaranteed to compute an exact tree
projection in low-order polynomial time.