Total Variation Minimization in Compressed Sensing
Felix Krahmer, Christian Kruschel, and Michael Sandbichler

arXiv:1704.02105v2 [] 3 Nov 2017

November 6, 2017

Abstract
This chapter gives an overview over recovery guarantees for total variation minimization in
compressed sensing for different measurement scenarios. In addition to summarizing the results
in the area, we illustrate why an approach that is common for synthesis sparse signals fails
and different techniques are necessary. Lastly, we discuss a generalizations of recent results for
Gaussian measurements to the subgaussian case.

1

Introduction

The central aim of Compressed Sensing (CS) [CRT06, Don06] is the recovery of an unknown
vector from very few linear measurements. Put formally, we would like to recover x ∈ Rn from
y = Ax + e ∈ Rm with m  n, where e denotes additive noise.
For general x, recovery is certainly not possible, hence additional structural assumptions are
necessary in order to be able to guarantee recovery. A common assumption used in CS is that the
signal is sparse. Here for x we assume
kxk0 := |{k ∈ [n] : xk 6= 0}| ≤ s,
that is, there are only very few nonzero entries of x. And say that x is s-sparse for some given
sparsity level s  n. We call a vector compressible, if it can be approximated well by a sparse
vector. To quantify the quality of approximation, we let
σs (x)q := inf kz − xkq
kzk0 ≤s

denote the error of the best s-sparse approximation of x.
In most cases, the vector x is not sparse in the standard basis, but there is a basis Ψ, such that
x = Ψz and z is sparse. This is also known as synthesis sparsity of x. To find an (approximately)
synthesis sparse vector, we can instead solve the problem of recovering z from y = AΨz. A common
strategy in CS is to solve a basis pursuit program in order to recover the original vector. For a
fixed noise level ε, it is given by
minimize kzk1 such that kAz − yk2 ≤ ε.

(1)

While this and related approaches of convex regularization have been studied in the inverse
problems and statistics literature long before the field of compressed sensing developed, these works
typically assumed the measurement setup was given. The new paradigm arising in the context of
1

Figure 1: The original Fabio image (left) and the absolute values after application of a discrete
gradient operator(right).
compressed sensing was to attempt to use the remaining degrees of freedom of the measurement
system to reduce the ill-posedness of the system as much as possible. In many measurement systems,
the most powerful known strategies will be based on randomization, i.e., the free parameters are
chosen at random.
Given an appropriate amount of randomness (i.e., for various classes of random matrices A,
including some with structure imposed by underlying applications), one can show that the minimizer
x̂ of (1) recovers the original vector x with error


σs (x)1
√
kx − x̂k2 ≤ c
+ε ,
(2)
s
see, e.g., [BDDW08] for an elementary proof in the case of subgaussian matrices without structure,
and [KR14] for an overview, including many references, of corresponding results for random measurement systems with additional structure imposed by applications. Note that (2) entails that if
x is s-sparse and the measurements are noiseless, the recovery is exact.
For many applications, however, the signal model of sparsity in an orthonormal basis has proven
somewhat restrictive. Two main lines of generalization have been proposed. The first line of work,
initiated by [RSV08] is the study of sparsity in redundant representation systems, at first under
incoherence assumptions on the dictionary. More recently, also systems without such assumptions
have been analyzed [CENR10, KNW15]. The main idea of these works is that even when one
cannot recover the coefficients correctly due to conditioning problems, one may still hope for a
good approximation of the signal.
The second line of work focuses on signals that are sparse after the application of some transform,
one speaks of cosparsity or analysis sparsity [NDEG13], see, e.g., [KR15] for an analysis of the
Gaussian measurement setup in this framework. A special case of particular importance, especially
for imaging applications, is that of sparse gradients. Namely, as it turns out, natural images
often admit very sparse approximations in the gradient domain, see, e.g., Figure 1. Here the
discrete gradient at location i = (i1 , . . . , in ) is defined as the vector with its n entries given by
(∇z)i j = zi+ej − zi , j = 1, . . . , n, where ej is the j-th standard basis vector.
2

A first attempt to recover a gradient sparse signal is to formulate a compressed sensing problem in terms of the sparse gradient. When this is possible (for instance in the example of Fourier
measurements [CRT06]), applying (1) will correspond to minimizing k∇zk1 =: kzkT V , the total variation seminorm. Then (under some additional assumptions) compressed sensing recovery
guarantees of the form (2) can apply. This proof strategy, however, only allows for showing that
the gradient can be approximately recovered, not the signal. When no noise is present and the
gradient is exactly sparse (which is not very realistic), this allows for signal recovery via integrating
the gradient, but in case of noisy measurements, this procedure is highly unstable.
Nevertheless, the success motivates to minimize the total variation seminorm if one attempts
to recover the signal directly, not the gradient. In analogy with (1), this yields the following
minimization problem.
minimize kzkT V = k∇zk1 such that kAz − yk2 ≤ ε.
For A the identity (i.e., not reducing the dimension), this relates to the famous Rudin-OsherFatemi functional, a classical approach for signal and image denoising [?]. Due to its high relevance
for image processing, this special case of analysis sparsity has received a lot of attention recently
also in the compressed sensing framework where A is dimension reducing. The purpose of this
chapter is to give an overview of recovery results for total variation minimization in this context
of compressed sensing (Section 2) and to provide some geometric intuition by discussing the onedimensional case under Gaussian or subgaussian measurements (to our knowledge, a generalization
to the latter case does not appear yet in the literature) with a focus on the interaction between the
high-dimensional geometry and spectral properties of the gradient operator (Section 3).

2

An overview over TV recovery results

In this section, we will give an overview of the state of the art guarantees for the recovery of
gradient sparse signals via total variation minimization. We start by discussing in Section 2.1
sufficient conditions for the success of TV minimization.
Subsequently, we focus on recovery results for random measurements. Interestingly, the results
in one dimension differ severely from the ones in higher dimensions. Instead of obtaining a required
√
number of measurements roughly on the order of the sparsity level s, we need sn measurements
for recovery. We will see this already in Subsection 2.2, where we present the results of Cai and
Xu [CX15] for recovery from Gaussian measurements. In Section 3, we will use their results to
obtain refined results for noisy measurements as well as guarantees for subgaussian measurements,
combined with an argument of Tropp [Tro15]. In Subsection 2.3 we will present results by Ward
and Needell for dimensions larger or equal than two showing that recovery can be achieved from
Haar incoherent measurements.

2.1

Sufficient Recovery Conditions

Given linear measurements Ax = y for an arbitrary A ∈ Rm×n and a signal x with k∇xk0 ≤ s, a
natural way to recover x is by solving
minimize k∇zk1 such that Az = y.

3

(3)

For I ⊂ [n] we denote AI as the columns of A indexed by I, and for a consecutive notation we
denote IIT ∇ as the rows of ∇ indexed by I and I as the identity matrix. The following results can
also be easily applied to analysis `1 -minimization, where any arbitrary matrix D ∈ Rp×n replaces
∇ in (3), as well as to any real Hilbert space setting [Kru15].
In many applications it is important to verify whether there is exactly one solution of (3). Since
∇ is not injective here, we cannot easily use the well-known recovery results in compressed sensing
[FR13] for the matrix A∇† . However, a necessary conditon can be given since x can only satisfy
Ax = y and (∇x)I c = 0 if
ker(IITc ∇) ∩ ker(A) = {0}.
If ∇ is replaced by the identity, this is equivalent to AI being injective. Since this injectivity
condition is unavoidable, we assume for the rest of this section that it is satisfied.
The paper [NDEG13] provides sufficient and necessary conditons for uniform recovery via (3).
The conditions rely on the null space of the measurements and are hard to verify similar to the
classical compressed sensing setup [TP14]. The following result is a corollary of these conditions.
It no longer provides a necessary condition, but is more manageable.
Corollary 2.1. [NDEG13] For all x ∈ Rn with s := k∇xk0 , the solution of (3) with y = Ax is
unique and equal to x if for all I ⊂ [n] with |I| ≤ s it holds that
∀w ∈ ker(A)\{0} : k(∇w)I k1 < k(∇w)I c k1 .
To consider measurements for specific applications, where it is difficult to prove whether uniform
recovery is guaranteed, one can empirically examine whether specific elements x solve (3) uniquely.
For computed tomography measurements, a Monte Carlo Experiment is considered in [JKL15]
to approximate the fraction of all gradient s-sparse vectors to uniquely solve (3). The results
prompt that there is a sharp transition between the case that every vector with a certain gradient
sparsity is uniquely recoverable and the case that TV-minimization will find a different solution
than the desired vector. This behavior empirically agrees with the phase transition in the classical
compressed sensing setup with Gaussian measurements [Don04].
To efficiently check whether many specific vectors x can be uniquely recovered via (3), one
needs to establish characteristics of x which must be easily verifiable. Such a non-uniform recovery
condition is given in the following theorem.
Theorem 2.1. [JKL15] It holds that x ∈ Rn is a unique solution of (3) if and only if there exists
w ∈ Rm and v ∈ Rn−1 such that
∇T v = AT w, vI = sign(∇x)I , kvI c k∞ < 1.

(4)

The basic idea of the proof is to use the optimality condition for convex optimization problems
[Roc72]. Equivalent formulations of the latter theorem can be found in [ZMY16, KR15] where
the problem is considered from a geometric perspective. However, verifying the conditions in
Theorem 2.1 still requires solving a linear program where an optimal v for (4) needs to be found.
In classical compressed sensing, the Fuchs Condition [Fuc04] is known as a weaker result as it
suggests a particular w in (4) and avoids solving the consequential linear program. The following
result generalizes this result to general analysis `1 -minimization.

4

Corollary 2.2. If x ∈ Rn satisfies
k(IITc ∇(∇T II c IITc ∇ + AT A)−1 ∇sign(∇x))I k∞ < 1
then x is the unique solution of (3).

2.2

Recovery from Gaussian measurements

As discussed above, to date no deterministic constructions of compressed sensing matrices are
known that get anywhere near an optimal number of measurements. Also for the variation of
aiming to recover approximately gradient sparse measurements, the only near-optimal recovery
guarantees have been established for random measurement models. Both under (approximate)
sparsity and gradient sparsity assumptions, an important benchmark is that of a measurement
matrix with independent standard Gaussian entries. Even though such measurements are hard
to realize in practice, they can be interpreted as the scenario with maximal randomness, which
often has particularly good recovery properties. For this reason, the recovery properties of total
variation minimization have been analyzed in detail for such measurements. Interestingly, as shown
by the following theorem, recovery properties in the one-dimensional case are significantly worse
than for synthesis sparse signals and also for higher dimensional cases. That is why we focus on
this case in Section 3, providing a geometric viewpoint and generalizing the results to subgaussian
measurements.
Theorem 2.2. [CX15] Let the entries of A ∈ Rm×n be i.i.d. standard Gaussian random variables
and let x̂ be a solution of (3) with input data y = Ax0 . Then
√
1. There exist constants c1 , c2 , c3 , c4 > 0, such that for m ≥ c1 sn(log n + c2 )
P(∀x0 : k∇x0 k0 ≤ s : x̂ = x0 ) ≥ 1 − c3 e−c4

√

m

.

2. For any η ∈ (0, 1), there are constants c̃1 , c̃2 > 0 and a universal constant c2 > 0, such that
√
for s ≥ c̃0 and (s + 1) < n4 . If m ≤ c̃1 sn − c̃2 , there exist infinitely many x0 ∈ Rn with
k∇x0 k0 ≤ s, such that P(x̂ 6= x0 ) ≥ 1 − η.
This scaling is notably different from what is typically obtained for synthesis sparsity, where the
number of measurements scales linearly with s up to log factors. Such a scaling is only obtained
for higher dimensional signals, e.g., images. Indeed, in [CX15], it is shown that for dimensions at
least two the number of Gaussian measurements sufficient for recovery is
(
c2 s log3 n, if d = 2
m≥
cd s log n, if d ≥ 3,
where the constant cd depends on the dimension.
Furthermore, as we can see in Theorem 2.5 below, this is also the scaling one obtains for
√
dimensions larger than 1 and Haar incoherent measurements. Thus the scaling of sn is a unique
feature of the 1-dimensional case. Also note that the square-root factor in the upper bound makes
the result meaningless for a sparsity level on the order of the dimension. This has been addressed
in [KRZ15], showing that a dimension reduction is also possible if the sparsity level is a (small)
constant multiple of the dimension.
5

The proof of Theorem 2.2 uses Gordon’s escape through the mesh Theorem [Gor88]. We will
elaborate on this topic in Section 3.
In case we are given noisy measurements y = Ax0 +e with kek2 ≤ ε, we can instead of solving (3)
consider
minimize k∇zk1 such that kAz − yk2 ≤ ε.

(5)

If ∇x0 is not exactly, but approximately sparse, and our measurements are corrupted with
noise, the following result can be established.
Theorem 2.3. [CX15] Let the entries of A ∈ Rm×n be i.i.d. standard Gaussian random variables
and let x̂ be a solution of (5) with input data y satisfying kAx0 − yk2 ≤ ε. Then for any α ∈ (0, 1),
there are positive constants δ, c0 , c1 , c2 , c3 , such that for m = αn and s = δn


min|S|≤s k(∇x0 )S c k1
ε
√
P kx0 − x̂k2 ≤ c2
≥ 1 − c0 e−c1 n .
+ c3 √
n
n
This looks remarkably similar to the recovery guarantees obtained for compressed sensing, note
however that the number of measurements needs to be proportional to n, which is not desirable.
We will present a similar result with improved number of measurements in Section 3.5.
Theorem 2.4. (Corollary of Theorem 3.4) Let x0 ∈ Rn be such that k∇x0 k ≤ s for s > 0 and
√
A ∈ Rm×n with m ≥ C ns log(2n) be a standard Gaussian matrix. Furthermore, set y = Ax0 + e,
where kek ≤ ε denotes the (bounded) error of the measurement and for some absolute constants
c, c̃ > 0 the solution x̂ of (12) satisfies
!
√
2ε
−c̃ ns
p
P kx̂ − x0 k > √
≤
e
.
c 4 ns( log(2n) − 1)
Note, however that in contrast to theorem 2.3, this theorem does not cover the case of gradient
compressible vectors, but on the other hand Theorem 3.4 also incorporates the case of special
subgaussian measurement ensembles. Also, if we set s = δn, we reach a similar conclusion as in
Theorem 2.3.

2.3

Recovery from Haar-incoherent measurements

For dimensions d ≥ 2, Needell and Ward [NW13a, NW13b] derived recovery results for measurement
matrices having the restricted isometry property (RIP) when composed with the Haar wavelet
transform. Here we say that a matrix Φ has the RIP of order k and level δ if for every k-sparse
vector x it holds that
(1 − δ)kxk22 ≤ kΦxk22 ≤ (1 − δ)kxk22 .
The results of [NW13a, NW13b] build upon a connection between a signal’s wavelet representation and its total variation seminorm first noted by Cohen, Dahmen, Daubechies and DeVore [CDDD03].
Their theorems yield stable recovery via TV minimization for N d dimensional signals. For
d = 2, notably these recovery results concern images of size N × N .
Several definitions are necessary in order to be able to state the theorem. The d dimensional
d
d
d
discrete gradient is defined via ∇ : RC → CN ×d and maps x ∈ CN to its discrete derivative which,
6

for each α ∈ [N ]d is a vector (∇x)α ∈ Cd composed of the derivatives in all d directions. Up to
now, we have always used the anisotropic version of the TV seminorm, which can be seen as taking
the `1 norm of the discrete gradient. The
P isotropic TV seminorm is defined via a combination of `2
and `1 norms. It is given by kzkT V2 := α∈[N ]d k(∇z)α k2 . The result in [NW13a] is given in terms
of the isotropic TV seminorm but can also be formulated for the anisotropic version.
Furthermore, we will need to concatenate several measurement matrices in order to be able
to state the theorem. This will be done via the concatenation operator ⊕ : Lin(Cn , Ck1 ) ×
Lin(Cn , Ck2 ) → Lin(Cn , Ck1 +k2 ), which ’stacks’ two linear maps.
l−1
d−l
Finally, we need the notion of shifted operators. For an operator B : CN ×(N −1)×N
→ Cq ,
N
d
q
0
N
d
q
l
these are defined as the operators B0l : C → C and B : C → C concatenating a column of
zeros to the end or beginning of the l-th component, respectively.
d

Theorem 2.5 ([NW13a]). Let N = 2n and fix integers p and q. Let A : CN → Cp be a map
that has the restricted isometry property of order 2ds and level δ < 1 if it is composed with the
d−1
orthonormal Haar wavelet transform. Furthermore let B1 , . . . , Bd with Bj : C(N −1)N
→ Cq be
such that B = B1 ⊕ B2 ⊕ · · · ⊕ Bd has the restricted isometry property of order 5ds and level δ < 31 .
d
Consider the linear operator M = A ⊕ [B1 ]01 ⊕ [B1 ]01 ⊕ · · · ⊕ [Bd ]0d ⊕ [Bd ]0d . Then M : CN → Cm
d
with m = 2dq + p and for all x ∈ CN we have the following. Suppose we have noisy measurements
y = M(x) + e with kek2 ≤ ε, then the solution to
x̂ = argminz kzkT V2 such that kM(z) − yk2 ≤ ε
satisfies
1. k∇(x − x̂)k2 ≤ c1



k∇x−(∇x)S k1,2
√
s

+

√ 
dε ,



2. kx − x̂kT V2 ≤ c2 k∇x − (∇x)S k1,2 +
3. kx − x̂k2 ≤ c3 d log N



k∇x−(∇x)S k1,2
√
s

√

+


sdε ,

√ 
dε ,

for some absolute constants c1 , c2 , c3 .
From the last point of the previous theorem, we see that for noiseless measurements and gradient
sparse vectors x, perfect recovery can be achieved provided the RIP assumption holds. Subgaussian
measurement matrices, for example, will have the RIP, also when composed with the Haar wavelet
transform H (this is a direct consequence of rotation invariance). Moreover, as shown in [KW11],
randomizing the column signs of an RIP matrix will, with high probability, also yield a matrix that
has the RIP when composed with H. An important example is a subsampled Fourier matrix with
random column signs, which relates to spread spectrum MRI (cf. [PMG+ 12]).

2.4

Recovery from subsampled Fourier measurements

Fourier measurements are widely used in many applications. Especially in medical applications as
parallel-beam tomography and magnetic resonance imaging it is desirable to reduce the number of
samples to spare patients burden. In Section 2.1, this is a motivation for introducing algorithmic
checks for unique solutions of (3). In this section, we consider a probabilistic approach where
an incomplete measurement matrix A ∈ Cm×n chosen from the discrete Fourier transform on
7

CN is considered. Therefore we consider a subset Ω of the index set {−bn/2c + 1, ..., dn/2e},
where Ω consists of m integers chosen uniformly at random and, additionally, 0 ∈ Ω. Hence,
we want to recover a signal, sparse in the gradient domain, with a measurement matrix A =
(e2πikj/n )k∈Ω,j∈[n] . In [CRT06] the optimal sampling cardinality for s-sparse signals in the gradient
domain was given and enables to recover one-dimensional signals signals from O(k log(n)) Fourier
samples. It naturally extends to two dimensions.
Theorem 2.6. [CRT06] With probability exceeding 1 − η, a signal z, which is k-sparse in the
gradient domain is the unique solution of (3) if
m & k(log(n) + log(η −1 )).
As already discussed in the introduction, the proof of this result proceeds via recovering the
gradient and then using that the discrete gradient (with periodic boundary conditions) is injective.
Due to the poor conditioning of the gradient, however, this injectivity results do not directly
generalize to recovery guarantees for noisy measurements. For two (and more) dimensions, such
results can be obtained via the techniques discussed in the previous subsection.
These techniques, however, do not apply directly. Namely, the Fourier (measurement) basis is
not incoherent to the Haar wavelet basis; in fact, the constant vector is contained in both, which
makes them maximally coherent. As observed in [PVW11], this incoherence phenomenon only
occurs for low frequencies, the high frequency Fourier basis vectors exhibit small inner products to
the Haar wavelet basis. This can be taken into account using a variable density sampling scheme
with sampling density that is larger for low frequencies and smaller for high frequencies. For
such a sampling density, one can establish the restricted isometry for the corresponding randomly
subsampled discrete Fourier matrix combined with the Haar wavelet transform with appropriately
rescaled rows [KW14]. This yields the following recovery guarantee.
Theorem 2.7. [KW14] Fix integers N = 2p , m, and s such that s & log(N ) and
m & s log3 (s) log5 (N ).
2
Select m frequencies {(ω1j , ω2j )}m
j=1 ⊂ {−N/2 + 1, . . . , N/2} i.i.d. according to



 j j
1
P (ω1 , ω2 ) = (k1 , k2 ) = CN min C, 2
=: η(k1 , k2 ), −N/2 + 1 ≤ k1 , k2 ≤ N/2,
k1 + k22

(6)

(7)

where C is an absolute constant and CN is chosen such that η is a probability distribution.
Consider the weight vector ρ = (ρj )m
with ρj = (1/η(ω1j , ω2j ))1/2 , and assume that the noise
j=1 √
vector ξ = (ξj )m
j=1 satisfies kρ ◦ ξk2 ≤ ε m, for some  > 0. Then with probability exceeding
3

1 − N −C log (s) , the following holds for all images f ∈ CN ×N :
Given noisy partial Fourier measurements y = FΩ f + ξ, the estimation
f # = argming∈CN ×N kgkT V

√
such that kρ ◦ (FΩ g − y)k2 ≤ ε m,

(8)

where ◦ denotes the Hadamard product, approximates f up to the noise level and best s-term
approximation error of its gradient:
kf − f # k2 .

k∇f − (∇f )s k1
√
+ ε.
s
8

(9)

A similar optimality result is given in [Poo15], also for noisy data and inexact sparsity. In
contrast to the previous result, this result includes the one-dimensional case. The key to obtaining
such a result is showing that the stable gradient recover implies the stable signal recovery, i.e.,
kzk2 . γ + kzkT V with kAzk2 ≤ γ.

(10)

Again the sampling distribution is chosen as a combination of the uniform distribution and a
decaying distribution. The main idea is to use this sampling to establish (10) via the RIP. We skip
technicalities for achieving the optimality in the following theorem and refer to the original article
for more details.
√
Theorem 2.8. [Poo15] Let z ∈ Cn be fixed and x be a minimizer of (5) with ε = mδ for some
δ > 0, m & k log(n)(1+log(η −1 )), and an appropriate sampling distribution. Then with probability
exceeding 1 − η, it holds that




√
kP ∇zk1
kz − xk2
δ
kP ∇zk1
k∇z − ∇xk2 . δ k + C1 √
, √
. C2 √ + C1
,
k
n
s
k
where P is the orthogonal projection onto a k-dimensional subspace,
C1 = log(k) log1/2 (m), and C2 = log2 (k) log(n) log(m).
In the two-dimensional setting the result changes to




√
kP ∇zk1
kP ∇zk1
√
k∇z − ∇xk2 . δ k + C3
,
, kz − xk2 . C2 δ + C3
k
k
with remaining C2 and
C3 = log(k) log(n2 /k) log1/2 (n) log1/2 (m).
These results are optimal since the best error one can archive [NW13b] is kz − xk2 . kP ∇zk1 k −1/2 .
The optimality in the latter theorems is achieved by considering a combination of uniform
random samling and variable density sampling. Uniform sampling on its own can achieve robust
and stable recovery. However, the following theorem shows that the signal error is no longer optimal
but the bound on the gradient error is still optimal up to log factors. Here (10) is obtained by
using the Poincaré inequality.
√
Theorem 2.9. [Poo15] Let z ∈ Cn be fix and x be a minimizer of (5) with ε = mδ for some δ > 0
and m & k log(n)(1 + log(η −1 )) with random uniform sampling. Then with probability exceeding
1 − η, it holds that


√
√
kP ∇zk1
kz − xk2
k∇z − ∇xk2 . δ k + C √
, √
. (δ s + CkP ∇zk1 ),
n
k
where P is the orthogonal projection onto a k-dimensional subspace and C = log(k) log1/2 (m).

9

3

TV-recovery from subgaussian measurements in 1D

In this section, we will apply the geometric viewpoint discussed in [Ver15] to the problem, which will
eventually allow us to show the TV recovery results for noisy subgaussian measurements mentioned
in Section 2.2.
As in the original proof of the 1D recovery guarantees for Gaussian measurements [CX15], the
Gaussian mean width will play an important role in our considerations.
Definition 3.1. The (Gaussian) mean width of a bounded subset K of Rn is defined as
w(K) := E sup hg, xi,
x∈K−K

where g ∈ Rn is a vector of i.i.d. N (0, 1) random variables.
In [CX15], the mean width appears in the context of the Gordon’s escape through the mesh
approach [Gor88] (see Section 3.4 below), but as we will see, it will also be a crucial ingredient in
applying the Mendelson small ball method [KM15, Men14].
The mean width has some nice (and important) properties, it is for example invariant under
taking the convex hull, i.e.,
w(ch(K)) = w(K).
Furthermore, it is also invariant under translations of K, as (K − x0 ) − (K − x0 ) = K − K.
Due to the rotational invariance of Gaussian random variables, that is U g ∼ g, we also have that
w(U K) = w(K). Also, it satisfies the inequalities
w(K) = E sup hg, xi ≤ 2E sup hg, xi ≤ 2E sup |hg, xi|,
x∈K−K

x∈K

x∈K

which are equalities if K is symmetric about 0, because then K = −K and hence K − K = 2K.

3.1

M ∗ bounds and recovery

In order to highlight the importance of the Gaussian mean width in signal recovery, we present some
arguments from [Ver15]. Thus in this section we present a classical result, the M ∗ bound, which
connects the mean width to recovery problems, cf. [Ver15]. Namely, recall that due to rotational
invariance, the kernel of a Gaussian random matrix A ∈ Rm×n is a random subspace distributed
according to the uniform distribution (the Haar measure) on the Grassmannian
Gn,n−m := {V ≤ Rn : dim(V ) = n − m}.
Consequently, the set of all vectors that yield the same measurements directly correspond to
such a random subspace.
The average size of the intersection of this subspace with a set reflecting the minimization
objective now gives us an average bound on the worst case error.
Theorem 3.1 (M ∗ bound, Theorem 3.12 in [Ver15]). Let K be a bounded subset of Rn and E be
a random subspace of Rn of drawn from the Grassmanian Gn,n−m according to the Haar measure.
Then
w(K)
E diam(K ∩ E) ≤ C √ ,
(11)
m
10

where C is absolute constant.
Given the M ∗ -bound it is now straightforward to derive bounds on reconstructions from linear
observations. We first look at feasibility programs - which in turn can be used to obtain recovery
results for optimization problems. For that, let K ⊂ Rn be bounded and x ∈ K be the vector we
seek to reconstruct from measurements Ax = y with a Gaussian matrix A ∈ Rm×n .
Corollary 3.1. [MPTJ07] Choose x̂ ∈ Rn , such that
x̂ ∈ K and Ax̂ = y,
then one has, for an absolute constant C 0 ,
w(K)
E sup kx̂ − xk2 ≤ C 0 √ .
m
x∈K
This corollary directly follows by choosing C 0 = 2C, observing that x̂ − x ∈ K − K, and that
the side constraint enforces A(x̂ − x) = 0.
Via a standard construction in functional analysis, the so called Minkowski functional, one can
now cast an optimization problem as a feasiblity program so that Corollary 3.1 applies.
Definition 3.2. The Minkowski functional of a bounded, symmetric set K ⊂ Rn is given by
k · kK : Rn → R : x 7→ inf{t > 0 : x ∈ tK}.
So the Minkowski functional tells us, how much we have to ’inflate’ our given set K in order to
capture the vector x. Clearly, from the definition we have that if K is closed
K = {x : kxkK ≤ 1}.
If a convex set K is closed and symmetric, then k · kK defines a norm on Rn .
Recall that a set K is star shaped, if there exists a point x0 ∈ K, which satisfies that for all
x ∈ K we have {tx0 + (1 − t)x : t ∈ [0, 1]} ⊂ K. It is easy to see that convex sets are star shaped,
but for example unions of subspaces are not convex, but star shaped.
For bounded, star shaped K, the notion of k·kK now allows to establish a direct correspondence
between norm minimization problems and feasibility problems. With this observation, Corollary 3.1
translates to the following result.
Corollary 3.2. For K bounded, symmetric and star-shaped, let x ∈ K and y = Ax. Choose
x̂ ∈ Rn , such that it solves
min kzkK with Az = y,
then

w(K)
E sup kx̂ − xk2 ≤ C 0 √ .
m
x∈K

Here x̂ ∈ K is due to the fact that the minimum satisfies kx̂kK ≤ kxkK ≤ 1, as x ∈ K by
assumption.
This result directly relates recovery guarantees to the mean width, it thus remains to calculate
the mean width for the sets under consideration. In the following subsections, we will discuss
11

two cases. The first one directly corresponds to the desired signal model, namely gradient sparse
vectors. These considerations are mainly of theoretical interest, as the associated minimization
problem closely relates to support size minimization, which is known to be NP hard in general.
The second case considers the TV minimization problem introduced above, which then also yields
guarantees for the (larger) set of vectors with bounded total variation.
Note, however, that the M ∗ -bound only gives a bound for the expected error. We can relate
this result to a statement about tail probabilities using Markov’s inequality, namely
w(K)
P(sup kx − x̂k2 > t) ≤ t−1 E sup kx − x̂k2 ≤ C 0 √ .
t m
x∈K
x∈K
In the next section we compute the mean width for the set of gradient sparse vectors, that is
we now specify the set K in Corollary 3.1 to be the set of all vectors with energy bounded by one
that only have a small number of jumps.

3.2

The mean width of gradient sparse vectors in 1d

Here [PV13] served as an inspiration, as the computation is very similar for the set of sparse vectors.
Definition 3.3. The jump support of a vector x is given via
Jsupp(x) := {i ∈ [n − 1] : xi+1 − xi 6= 0}.
The jump support captures the positions, in which a vector x changes its values. With this, we
now define the set
K0s := {x ∈ Rn : kxk2 ≤ 1, |Jsupp(x)| ≤ s}.
The set K0s consists of all s-gradient sparse vectors, which have 2-norm smaller than one. We will
now calculate the mean width of K0s in order to apply Corrolary 3.1 or 3.2.
Note that we can decompose the set K0s into smaller sets KJ ∩B2n with KJ = {x : Jsupp(x) ⊂ J},
|J| = s and B2n = {x ∈ Rn : kxk2 ≤ 1}. As we can’t add any jumps within the set KJ , it is a
subspace of Rn . We can even quite easily find an orthonormal basis for it, if we define
(
1, if k ∈ [i, j]
1
(e[i,j] )k := √
.
j − i + 1 0, else
As we can align all elements of J = {j1 , j2 , . . . , js } with 1 ≤ j1 < j2 < . . . < js = n, we see that
{e[1,j1 ] , e[j1 +1,j2 ] , e[j2 +1,j
all elements
P3s] , . . . , e[js−1 +1,js ] } forms an ONB of KJ . Now, we can write
n
n
x ∈ KJ ∩ B2 as x = i=1 αi e[ji−1 +1,ji ] by setting j0 := 0. The property that x ∈ B2 now enforces
(ONB) that kαk2 ≤ 1. Now, note that K0s = −K0s , so we have
w(K0s ) = E
Using the decomposition K0s =

S

hg, xi = 2E sup hg, xi.

sup
x∈K0s −K0s

|J|=s (KJ

x∈K0s

∩ B2n ), we get

w(K0s ) = 2E sup

sup

|J|=s x∈KJ ∩B2n

12

hg, xi.

Now
hg, xi ≤ sup

sup
x∈KJ ∩B2n

α∈B2s

s
X

αi hg, e[ji−1 +1,ji ] i = sup

α∈B2s

i=1

s
X

αi

i=1

ji
X

gk
.
ji − ji−1
k=ji−1 +1
|
{z
}
√

=:GJ
i

Note that GJi is again a Gaussian random variable with mean 0 and variance 1. Furthermore,
the supremum over α is attained, if α is parallel to GJ , so we have supx∈KJ ∩B2n hg, xi = kGJ k2 .
Also note that GJ has i.i.d. entries, but for different J1 , J2 , the random vectors GJ1 and GJ2 may
be dependent. Our task is now to calculate E sup|J|=s kGJ k2 . As it has been shown for example
in [FR13], we have that
r
√
2√
s ≤ EkGJ k2 ≤ s
π
and from standard results for Gaussian concentration (cf. [PV13]), we get
√

2

s + t) ≤ P(kGJ k2 ≥ EkGJ k2 + t) ≤ e−t /2 .

By noting that |{J ⊂ [n] : |J| = s}| = ns , we see by a union bound that
 
 
√
√
n
n −t2 /2
J
J
P( sup kG k2 ≥ s + t) ≤
P(kG k2 ≥ s + t) ≤
e
.
s
s
|J|=s
P(kGJ k2 ≥

For the following calculation, set X := sup|J|=s kGJ k2 . By Jensen’s inequality and rewriting
the expectation, we have that
Z ∞
λEX
λX
e
≤ Ee =
P(eλX ≥ τ )dτ.
0

Now, the previous consideration showed, that
√

P(eλX ≥ |eλ( {zs+t)}) = P(X ≥

√

s + t) ≤

=:τ

 
 
n −t2 /2
n −(log(τ )/λ−√s)2 /2
e
=
e
,
s
s

Computing the resulting integrals yields
 
√
n −s/2 √
2
λEX
e
≤
e
λ 2πe( s+λ) /2 .
s
Using a standard bound for the binomial coefficients, namely
√

eλEX ≤ es log(en/s)−s/2+(

n
s



≤ es log(en/s) , we see

√
s+λ)2 /2+log(λ)+log( 2π)

,

or equivalently
√
√
λEX ≤ s log(en/s) − s/2 + ( s + λ)2 /2 + log(λ) + log( 2π)
By setting λ =

p

s log(en/s) and assuming (reasonably) large n, we thus get
p
EX ≤ 5 s log(en/s).
13

From this, we see that
p
w(K0s ) ≤ 10 s log(en/s).
It follows that the Gaussian mean width of the set of gradient sparse vectors is the same as the
mean width of sparse vectors due to the similar structure. If we want to obtain accuracy δ for our
reconstruction, according to Theorem 3.1, we need to take


s log(en/s)
m=O
δ2
measurements.
In Compressed Sensing, the squared mean width of the set of s-sparse vectors (its so called
statistical dimension) already determines the number of required measurements in order to recover
a sparse signal with basis pursuit. This is the case because the convex hull of the set of sparse vectors
can be embedded into the `1 -ball inflated by a constant factor. In the case of TV minimization, as
we will see in the following section, this embedding yields a (rather large) constant depending on
the dimension.

3.3

The extension to gradient compressible vectors needs a new approach

In the previous subsection, we considered exactly gradient sparse vectors. However searching all
such vectors x that satisfy Ax = y is certainly not a feasible task. Instead, we want to solve the
convex program
min kzkT V with Az = y,
with kzkT V = k∇zk1 the total variation seminorm. Now if we have that x ∈ K0s , we get that
√
√
kxkT V ≤ 2kαk1 ≤ 2 skαk2 = 2 s,
√
√
√
2 s
s ⊂ K 2 s := {x ∈ B n : kxk
s}.
As
K
with α as in section
3.2,
so
K
≤
2
TV
0
TV
T V is convex, we even
√
√2
2 s

2 s

have ch(K0s ) ⊂ KT V . We can think of the set KT V as ’gradient- compressible’
vectors.
√
4 s

In the proof of Theorem 3.3 in [CX15], the Gaussian√width of the set KT V has been calculated
p√
2 s
via a wavelet-based argument. One obtains that w(KT V ) ≤ C
ns log(2n) with C ≤ 20 being
an absolute constant. In this section we illustrate, that proof techniques different from the ones
used in the case of synthesis sparsity are indeed necessary in order to obtain useful results. In the
√
synthesis case, the 1-norm ball of radius s is contained in the set of s-sparse vectors inflated by a
constant factor. This in turn implies that the mean width of the compressible vectors is bounded
by a constant times the mean width of the s-sparse vectors.
√
2 s
We will attempt a similar computation, that is to √find a constant, such that the set KT V is
2 s

contained in the ’inflated’ set cn,s ch(K0s ). Then w(KT V ) ≤ cn,s w(K0s ). Although this technique
works well for sparse recovery, where cn,s = 2, it pityably fails in the case of TV recovery as we will
see below.
√
2 s
Let us start with x ∈ KT V . Now we can decompose J := Jsupp(x) = J1 ] J2 ] . . . Jp with
|Jk | ≤ s in an ascending manner, i.e., for all k ∈ Ji , l ∈ Ji+1 , we have that αk < αl . Note that the

14

n
number
Pp Pp of such sets satisfies p ≤ s . Similarly as above, we now write x =
i∈Jk αi e[ji−1 +1,ji ] . From this, we see that
k=1

x=

p
X

kαJk k2

X
i∈Jk

k=1

|

P|J|

i=1 αi e[ji−1 +1,ji ]

=

αi
e
.
kαJk k2 [ji−1 +1,ji ]
{z
}
∈K0s

The necessary factor cn,s can be found by bounding the size of kαJk k2 , namely
max(kαJk k2 ) ≤

p
X
k=1

C−S

kαJk k2 ≤ kαk2
| {z }

√

r
p≤

n
.
s

≤1

√
p
2 s
From this, we see that KT V ⊂ ns ch(K0s ). To see that this embedding constant is optimal, we
construct a vector, for which it is needed.
To q
simplify the discussion, suppose that n and s are even and s|n. For even n, the vector
√
2 s

k

√

ε
)k has unity norm, lies in KT V for ε < 2 n s and has jump support on all of [n]!
x1 = ( 1−(−1)
n
For a vector x ∈ Rn and an index set I ⊂ [n], we define the restriction of x to I by
(
xj , if j ∈ I
(x|I )j :=
0, else.

pn
s
By splitting Jsupp(x1 ) into sets J1 , . . . , Jn/s and setting ak =
s x1 |Jk ∈ K0 , we see that x1 =
pn
Pn/s p s
s
k=1
n ak and in order for this to be elements of cn,s ch(K0 ), we have to set cn,s =
s . This
follows from
r
 r
n/s r
n/s
n/s
X
X
X
1
sp
n
n
x1 |Jk =
x1 =
ak =
ak ∈
ch(K0s )
np
p
s
s
k=1
k=1
k=1 |
{z }
√n s
∈

and no smaller inflation factor than

pn
s

s

K0

can suffice.

So from the previous discussion, we get
Lemma 3.1. We have the series of inclusions
ch(K0s )

⊂

√
2 s
KT V

r
⊂

n
ch(K0s ).
s

In view of the results obtainable for sparse vectors√ and the `1 -ball, this is very disappointing,
2 s
because Lemma 3.1 now implies that the width of KT V satisfies
r
 r
√
p
n
n
2 s
s
w(KT V ) ≤ w
ch(K0 ) =
w(K0s ) ≤ 10 n log(e(n − 1)/s),
s
s
which is highly suboptimal.
15

Luckily, the results in [CX15] suggest, that the factor n in the previous equation can be replaced
√
√
2 s
by sn. However, they have to resort to a direct calculation of the Gaussian width of KT V .
The intuition why the Gaussian mean width can be significantly smaller than the bound given in
Lemma 3.1 stems from the fact, that in order to obtain an inclusion we need to capure all ’outliers’
of the set - no matter how small their measure is.

3.4

Exact recovery

For exact recovery, the M ∗ -bound is not suitable anymore and, as suggested in [Ver15], we will use
’Gordon’s escape through the mesh’ in order to find conditions on exact recovery. Exact recovery
for TV minimization via this approach has first been considered in [CX15].
Suppose, we want to recover x ∈ K0s from Gaussian measurements Ax = y. Given, that we
want our estimator x̂ to lie in a set K, exact recovery is achieved, if K ∩ {z : Az = y} = {x}. This
is equivalent to requiring
(K − x) ∩ {z − x : Az = y} = {0}.
|
{z
}
=ker(A)

With the descent cone D(K, x) = {t(z − x) : t ≥ 0, z ∈ K}, we can rewrite this condition as
D(K, x) ∩ ker(A) = {0},
by introducing the set S(K, x) = D(K, x) ∩ B2n , we see that if
S(K, x) ∩ ker(A) = ∅,
we get exact recovery. The question, when a section of a subset of the sphere with a random
hyperplane is empty is answered by Gordon’s escape through a mesh.
Theorem 3.2 ([Gor88]). Let S ⊂ Sn−1 be fixed and E ∈ Gn,n−m be drawn at random according
√
to the Haar measure. Assume that ŵ(S) = E supu∈S hg, ui < m, then S ∩ E = ∅ with probability
exceeding
√


(m/ m + 1 − ŵ(S))2
1 − 2.5 exp −
.
18
So we get exact recovery with high probability from a program given in Theorem 3.1 or 3.2,
provided that m > ŵ(S(K, x0 ))2 .
Let’s see how this applies to TV minimization. Suppose, we are given x ∈ K0s and Gaussian
measurements Ax = y. Solving
min kzkT V with Az = y,
amounts to using the Minkowski functional of the set K = {z ∈ Rn : kzkT V ≤ kxkT V }, which is a
scaled TV-Ball.
In [CX15], the null space property for TV minimization given in Corollary 2.1 has been used in
order to obtain recovery guarantees.
They consider the set, where this condition is not met
S := {x0 ∈ B2n : ∃J ⊂ [n], |J| ≤ s, k(∇x0 )J k1 ≥ k(∇x0 )J c k1 },

16

and apply Gordon’s escape through the mesh to see that with high probability, its intersection with
the kernel of A is empty, thus proving exact recovery with high probability. Their estimate to the
mean width of the set S,
√ p
ŵ(S) ≤ c 4 ns log(2n)
√
with c < 19 is essentially optimal (up to logarithmic factors), as they also show that w(S) ≥ C 4 ns.
√
So uniform exact recovery can only be expected for m = O( sn log n) measurements.
Let us examine some connections to the previous discussion about the descent cone.
Lemma 3.2. We have that for K = {z ∈ Rn : kzkT V ≤ kxkT V } defined as above and x ∈ K0s , it
holds that S(K, x) ⊂ S.
Proof. Let y ∈ S(K, x). Then there exists a x 6= z ∈ K, such that y =
then, as z ∈ K, we have that kzkT V ≤ kxkT V , or
X
X
X
|(∇x)i | ≥
|(∇z)i | +
|(∇z)i |
i∈J

z−x
kz−xk2 .

Set J = Jsupp(x),

i6∈J

i∈J

Now, by the triangle inequality and this observation, we have
X
X
X
X
|(∇x)i − (∇z)i | ≥
|(∇x)i | − |(∇z)i | ≥
|(∇z)i | =
|(∇x)i − (∇z)i |.
i∈J

i6∈J

i∈J

i6∈J

The last equality follows from the fact that ∇x is zero outside of the gradient support of x. Mul1
gives the desired result
tiplying both sides with kz−xk
2
k(∇y)J k1 =

X
X
1
1
|(∇x)i − (∇z)i | ≥ ≥
|(∇x)i − (∇z)i | = k(∇y)J c k1 .
kz − xk2
kz − xk2
i6∈J

i∈J

The previous lemma shows that the recovery guarantees derived from the null space property
and via the descent cone are actually connected in a very simple way.
Clearly, now if we do not intersect the set S, we also do not intersect the set S(K, x), which yields
exact recovery for example with the same upper bounds on m as for S. Even more specifically, in the
calculation of ŵ(S) given in [CX15], an embedding into a slightly larger set S̃ = {x ∈ B2n : kxkT V ≤
√
√
4 s} is made. This embedding can also quite easily be done if we note that kxkT V ≤ 2 s, as we
showed above and kzkT V ≤ kxkT V .
Note that the same discussion also holds for higher dimensional signals, such that the improved
numbers of measurements as given in Section 2.2 can be applied.

3.5

Subgaussian measurements

Up to this point, all our measurement matrices have been assumed to consist of i.i.d. Gaussian
random variables. We will reduce this requirement in this section to be able to incorporate also
subgaussian measurement matrices into our framework.
Definition 3.4. A real valued random variable X is called subgaussian, if there exists a number
2
t > 0, such that EetX < ∞. A real valued random vector is called subgaussian, if all of its one
dimensional marginals are subgaussian.
17

An obvious example of subgaussian random variables are Gaussian random variables, as the expectation in Definition 3.4 exists for all t < 1. Also, all bounded random variables are subgaussian.
Here, we rely on results given by Tropp in [Tro15] using the results of Mendelson [KM15, Men14].
We will consider problems of the form
min kzkT V such that kAz − yk ≤ ε,

(12)

where A is supposed to be a matrix with independent subgaussian rows. Furthermore, we denote
the exact solution by x0 , i.e., Ax0 = y. We pose the following assumptions on the distribution of
the rows of A.
(M1) EAi = 0,
(M2) There exists α > 0, such that for all u ∈ Sn−1 it holds that E|hAi , ui| ≥ α,
(M3) There is a σ > 0, such that for all u ∈ Sn−1 it holds that P(|hAi , ui| ≥ t) ≤ 2 exp(−t2 /(2σ 2 )),
(M4) The constant ρ :=

σ
α

is small.

Then the small ball methods yields the following recovery guarantee (we present the version of
[Tro15]).
Theorem 3.3. Let x0 ∈ Rn and A ∈ Rm×n be a subgaussian matrix satisfying (M1)-(M4) above.
Furthermore, set y = Ax0 + e, where kek ≤ ε denotes the (bounded) error of the measurement.
Then the solution x̂ of (12) satisfies
kx̂ − x0 k ≤

max{cαρ−2

√

2ε
m − Cσw(S(K, x0 )) − αt, 0}

2

with probability exceeding 1 − e−ct . D(K, x0 ) denotes the descent cone of the set K at x0 , as
defined in the previous section.
From this we see that, provided
m ≥ C̃ρ6 w2 (S(K, x0 )),
we obtain stable reconstruction of our original vector from (12). Note that the theorem is only
√
meaningful for t = O( m), as otherwise the denominator vanishes.
In the previous section, we have shown the inclusion S(K, x0 ) ⊂ S for x0 ∈ Ks0 and hence we
have that
√ p
w(S(K, x0 ) ≤ w(S) ≤ c 4 ns log(2n).
√
So we see that for m ≥ C̃ρ6 ns log(2n), we obtain the bound
2ε
p
p
√
√ p
max{cαρ−2 C̃ρ3 4 ns log(2n) − Cσ 4 ns log(2n) − αt, 0}
2ε
p
=
p
√
4
max{σ(c C̃ − C) ns log(2n) − αt, 0}

kx̂ − x0 k ≤

with high probability. We conclude that, given the absolute constants c, C, we need to set
2
C̃ ≥ Cc2 in order to obtain a meaningful result. Combining all our previous discussions with
Theorem 3.3, we get
18

400

0.5

0.5
0.45

0.45

350

0.4

0.4
300
0.35

10

0.35

2

250
0.3

0.25

m

m

0.3

200

0.25

0.2

0.2

150

0.15

0.15

100
0.1

0.1

10 1

50
0.05

0

0.05

0

0

200

400

600

800

1000

1200

1400

1600

1800

0

2000

10 2

N

10 3

N

Figure 2: Average error of recovery from Rademacher measurements in 1d with m measurements
and ambient dimension N for fixed cosparsity level s = 5. Left: linear axis scaling, Right: logarithmic axis scaling. The slope of the phase transition in the log-log plot is observed to be about
1
4.
√
Theorem 3.4. Let x0 ∈ Rn , m ≥ C̃ρ6 ns log(2n) and A ∈ Rm×n be a subgaussian matrix
satisfying (M1)-(M4). Furthermore, set y = Ax0 + e, where kek
denotes the (bounded) error of
√ ≤ε√
√
σ(c C̃−C) 4 ns log(2n)
the measurement, constants c, C, C̃ > 0 as above and t ≤
. Then the solution
α
x̂ of (12) satisfies
!
2ε
2
p
P kx̂ − x0 k >
≤ e−ct .
p
√
σ(c C̃ − C) 4 ns log(2n) − αt
p
√
We can for example set t = ρ(c C̃ − C) 4 ns (for n ≥ 2) to obtain the bound
!
√
2ε
−c̃ρ ns
p
≤
e
.
P kx̂ − x0 k >
p
√
σ(c C̃ − C) 4 ns( log(2n) − 1)
q
For example for i.i.d. standard Gaussian measurements, the constant ρ = π2 .
Note that in the case of noisefree measurements ε = 0, Theorem 3.4 gives an exact recovery
result for a wider class of measurement ensembles with high probability. Furthermore with a
detailed computation of w(S(K, x0 )) one may be able to improve the number of measurements
for nonuniform recovery. It also remains open, whether the lower bounds of Cai and Xu for the
case of Gaussian measurements can be generalized to the subgaussian case. In fact, our numerical
experiments summarized in Figure 2 suggest a better scaling in the ambient dimension, around
N 1/4 , in the average case. We consider it an interesting problem for future work to explore whether
this is due to a difference between Rademacher and Gaussian matrix entries, between uniform and
nonuniform recovery, or between the average and the worst case. Also, it is not clear whether
the scaling is in fact N 1/4 or if the observed slope is just a linearization of, say, a logarithmic
dependence.

19

4

Discussion and open problems

As the considerations in the previous sections illustrate, the mathematical properties of total variation minimization differ significantly from algorithms based on synthesis sparsity, especially in one
dimension. For this reason, there are a number of questions that have been answered for synthesis
sparsity, but which are still open for the framework of total variation minimization. For example,
the analysis provided in [RRT12, KMR14] for deterministically subsampled partial random circulant matrices, as they are used to model measurement setups appearing in remote sensing or coded
aperture imaging, could not be generalized to total variation minimization. The difficulty in this
setup is that the randomness is encoded by the convolution filter, so it is not clear what the analogy
of variable density sampling would be.
Another case of practical interest is that of sparse 0/1 measurement matrices. Recently it has
been suggested that such meausurements increase efficiency in photoacoustic tomography, while at
the same time, the signals to be recovered (after a suitable temporal transform) are approximately
gradient sparse. This suggests the use of total variation minimization for recovery, and indeed empirically, this approaches yields good recovery results [SKB+ 15]. Theoretical guarantees, however,
(as they are known for synthesis sparse signals via an expander graph construction [BGI+ 08]) are
not available to date for this setup.

Acknowledgements
FK and MS acknowledge support by the Hausdorff Institute for Mathematics (HIM), where part
of this work was completed in the context of the HIM trimester program Mathematics of Signal
Processing, FK and CK acknowledge support by the German Science Foundation in the context of
the Emmy Noether Junior Research Group Randomized Sensing and Quantization of Signals and
Images (KR 4512/1-1) and by the German Ministry of Research and Education in the context of
the joint research initiative ZeMat. MS has been supported by the Austrian Science Fund (FWF)
under Grant no. Y760 and the DFG SFB/TRR 109 ”Discretization in Geometry and Dynamics”.

References
[BDDW08] R. G. Baraniuk, M. Davenport, R. A. DeVore, and M. Wakin. A simple proof of the
Restricted Isometry Property for random matrices. Constr. Approx., 28(3):253–263,
2008.
[BGI+ 08]

R. Berinde, A. Gilbert, P. Indyk, H. Karloff, and M. Strauss. Combining geometry and
combinatorics: A unified approach to sparse signal recovery. In 46th Annual Allerton
Conference on Communication, Control, and Computing, 2008, pages 798–805. IEEE,
2008.

[CDDD03] A. Cohen, W. Dahmen, I. Daubechies, and R DeVore. Harmonic analysis of the space
bv. Rev. Mat. Iberoam., 19(1):235–263, 2003.
[CENR10] E. J. Candès, Y. C. Eldar, D. Needell, and P. Randall. Compressed sensing with
coherent and redundant dictionaries. Appl. Comput. Harmon. Anal., 31(1):59–73, 2010.

20

[CRT06]

E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal
reconstruction from highly incomplete frequency information. IEEE Trans. Inform.
Theory, 52(3):489–509, 2006.

[CX15]

J.-F. Cai and W. Xu. Guarantees of total variation minimization for signal recovery.
Information and Inference, 4(4):328–353, 2015.

[Don04]

D. Donoho. High-dimensional centrally-symmetric polytopes with neighborliness proportional to dimension. Technical report, Department of Statistics, Stanford University,
2004.

[Don06]

D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–1306,
2006.

[FR13]

S. Foucart and H. Rauhut.
Springer, 2013.

[Fuc04]

J. J. Fuchs. On sparse representations in arbitrary redundant bases. IEEE Trans.
Inform. Theory, 50(6), 2004.

[Gor88]

Y. Gordon. On Milman’s inequality and random subspaces which escape through a mesh
in Rn . Springer, 1988.

[JKL15]

J. Jørgensen, C. Kruschel, and D. Lorenz. Testable uniqueness conditions for empirical
assessment of undersampling levels in total variation-regularized x-ray ct. Inverse Probl.
Sci. En., 23(8):1283–1305, 2015.

[KM15]

V. Koltchinskii and S. Mendelson. Bounding the smallest singular value of a random
matrix without concentration. Int. Math. Res. Notices, 2015(23):12991–13008, 2015.

[KMR14]

F. Krahmer, S. Mendelson, and H. Rauhut. Suprema of chaos processes and the restricted isometry property. Comm. Pure Appl. Math., 67(11):1877–1904, 2014.

[KNW15]

F. Krahmer, D. Needell, and R Ward. Compressive sensing with redundant dictionaries
and structured measurements. SIAM J. Math. Anal., 47(6):4606–4629, 2015.

[KR14]

F. Krahmer and H. Rauhut. Structured random measurements in signal processing.
GAMM-Mitteilungen, 37(2):217–238, 2014.

[KR15]

M. Kabanava and H. Rauhut. Analysis `1 -recovery with frames and gaussian measurements. Acta Appl. Math., 140(1):173–195, 2015.

[Kru15]

C. Kruschel. Geometrical Interpretations and Algorithmic Verification of Exact Solutions in Compressed Sensing. PhD thesis, TU Braunschweig, 2015.

[KRZ15]

M. Kabanava, H. Rauhut, and H. Zhang. Robust analysis `1 -recovery from gaussian
measurements and total variation minimization. European J. Appl. Math., 26(06):917–
929, 2015.

[KW11]

F. Krahmer and R. Ward. New and improved johnson-lindenstrauss embeddings via
the restricted isometry property. SIAM J. Math. Anal., 43(3):1269–1281, 2011.

A mathematical introduction to compressive sensing.

21

[KW14]

F. Krahmer and R. Ward. Stable and robust sampling strategies for compressive imaging. IEEE Trans. Image Proc., 23(2):612–622, 2014.

[Men14]

S. Mendelson. Learning without concentration. In COLT, pages 25–39, 2014.

[MPTJ07] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann. Reconstruction and subgaussian
operators in asymptotic geometric analysis. Geom. Funct. Anal., 17(4):1248–1282,
2007.
[NDEG13] S. Nam, M. Davies, M. Elad, and R. Gribonval. The cosparse analysis model and
algorithms. Appl. Comp. Harmon. Anal., 34(1):30–56, 2013.
[NW13a]

D. Needell and R. Ward. Near-optimal compressed sensing guarantees for total variation minimization. IEEE Trans. Image Proc., 22(10):3941–3949, 2013.

[NW13b]

D. Needell and R. Ward. Stable image reconstruction using total variation minimization. SIAM J. Imag. Sci., 6(2):1035–1058, 2013.

[PMG+ 12] G. Puy, J. Marques, R. Gruetter, J.-P. Thiran, D. Van De Ville, P. Vandergheynst, and
Y. Wiaux. Spread spectrum magnetic resonance imaging. IEEE Trans. Med. Imaging,
31(3):586–598, 2012.
[Poo15]

C. Poon. On the role of total variation in compressed sensing. SIAM J. Imag. Sci,
8(1):682–720, 2015.

[PV13]

Y. Plan and R. Vershynin. Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach. IEEE Trans. Inform. Theory, 59(1):482–494,
2013.

[PVW11]

G. Puy, P. Vandergheynst, and Y. Wiaux. On variable density compressive sampling.
IEEE Signal Proc. Let., 18:595–598, 2011.

[Roc72]

R.T. Rockafellar. Convex Analysis. Princeton University Press, 1972.

[RRT12]

H. Rauhut, J. Romberg, and J.A. Tropp. Restricted isometries for partial random
circulant matrices. Appl. Comp. Harmon. Anal., 32(2):242–254, 2012.

[RSV08]

H. Rauhut, K. Schnass, and P. Vandergheynst. Compressed sensing and redundant
dictionaries. IEEE Trans. Inform. Theory, 54(5):2210–2219, 2008.

[SKB+ 15]

M. Sandbichler, F. Krahmer, T. Berer, P. Burgholzer, and M. Haltmeier. A novel
compressed sensing scheme for photoacoustic tomography. SIAM J. Appl. Math.,
75(6):2475–2494, 2015.

[TP14]

A. Tillmann and M. Pfetsch. The computational complexity of the restricted isometry
property, the nullspace property, and related concepts in compressed sensing. IEEE
Trans. Inform. Theory, 60(2):1248–1259, 2014.

[Tro15]

J. Tropp. Convex recovery of a structured signal from independent random linear
measurements. In Sampling Theory, a Renaissance, pages 67–101. Springer, 2015.

22

[Ver15]

R. Vershynin. Estimation in high dimensions: a geometric perspective. In Sampling
theory, a renaissance, pages 3–66. Springer, 2015.

[ZMY16]

H. Zhang, Y. Ming, and W. Yin. One condition for solution uniqueness and robustness
of both `1 -synthesis and `1 -analysis minimizations. Adv. Comput. Math., 42(6):1381–
1399, 2016.

23

