  This paper considers the use of total variation regularization in the
recovery of approximately gradient sparse signals from their noisy discrete
Fourier samples in the context of compressed sensing. It has been observed over
the last decade that a reconstruction which is robust to noise and stable to
inexact sparsity can be achieved when we observe a highly incomplete subset of
the Fourier samples for which the samples have been drawn in a random manner.
Furthermore, in order to minimize the cardinality of the set of Fourier
samples, the sampling set needs to be drawn in a non-uniform manner and the use
of randomness is far more complex than the notion of uniform random sampling
often considered in the theoretical results of compressed sensing. The purpose
of this paper is to derive recovery guarantees in the case where the sampling
set is drawn in a non-uniform random manner. We will show how the sampling set
is dependent on the sparsity structure of the underlying signal.
