arXiv:1609.06357v3 [] 13 Apr 2017

Sparse Blind Deconvolution and Demixing Through ℓ1,2-Minimization.∗
Axel Flinth†
Institut für Mathematik
Technische Universität Berlin
April 14, 2017

Abstract
This paper concerns solving the sparse deconvolution and demixing problem using ℓ1,2 -minimization. We
show that under a certain structured random model, robust and stable recovery is possible. The results extend
results of Ling and Strohmer [Self Calibration and Biconvex Compressive Sensing, Inverse Problems, 2015],
and in particular theoretically explain certain experimental findings from that paper. Our results do not only
apply to the deconvolution and demixing problem, but to recovery of column-sparse matrices in general.
MSC2010: 52A41, 90C25.

Acknowledgement
The author acknowledges support from Deutsche Forschungsgemeinschaft (DFG) Grant KU 1446/18 - 1 and the
Berlin Mathematical School. He thanks Felix Krahmer and Dominik Stöger for pointing out weak spots in the
first version of the article, as well as providing references making it possible to repair them – and even enhance
the results slightly in the process. He also wishes to thank Gitta Kutyniok for fruitful discussions.

1

Introduction

Assume that we observe a vector v ∈ Cq 1 and are told that it is a sum of r convolutions of r pairs of vectors
wi , zi , i.e.
X
wi ∗ zi ,
v=
i∈[r]

where [r] is a short-hand notation for the set {1, 2, . . . , r}. This problem is known
as the blind deconvolution and
P
demixing problem (we need to ’demix’ each contribution wi ∗ zi from the sum i wi ∗ zi , as well as ’deconvolve’ the
unknown filters wi to recover the vectors zi ). In general, it is of course impossible to reconstruct the pairs (wi , zi )
without any structural assumptions on them. In this work, we will assume that there exist (known) subspaces Wi
∗ This article has been accepted for publication in Adv. Comput. Math. The final publication is available at Springer via
DOI 10.1007/s10444-017-9533-0
† Postal adress: Techische Universität Berlin, Sekretariat MA 5-4, Straße des 17 Juni 136, 10623 Berlin.
E-mail: flinth@math.tu-berlin.de
1 In a previous (preprint) version of this article, all (random) vectors appearing were assumed to be real. As was pointed out to the
author, this is not very fortunate due to the use of the Fourier transform. Concretely, the meaning of the vectors ai being Gaussian
distributed changes meaning into something more artificial than when they are kept complex. For this reason, a change to a complex
setting was made.

1

and Ui of Cq , i ∈ [r] such that wi ∈ Wi and zi ∈ Ui for each i ∈ [r]. This could in a communication application
correspond to filters wi and signals zi having certain bandwidth restrictions.
There is a standard way to transform the blind deconvolution problem into a matrix recovery problem (Ahmed,
Recht and Romberg 2014 [1]; Ling and Strohmer 2015 [11]). For certain sparsity assumptions on the vectors wi
and zi , this results in a recovery problem of a column sparse matrix tuple Z. Such problems will be the focus of
this paper.
Before discussing strategies for solving such problems, let us begin by describing the transformation procedure
in detail. Taking the Fourier transform of the above equation, we arrive at
X
ŵi ⊙ ẑi ,
v̂ =
i∈[r]

ci ,
where ⊙ denotes elementwise multiplication, i.e. (x ⊙ y)i = xi yi . Let us introduces the bases (Bℓi )ℓ∈[ki ] for W
bi , i ∈ [r] (note that we do not assume that all subspaces have the same dimension). Then
and (Aiℓ )ℓ∈[ni ] for U
there exists coefficients (fki )k∈[ki ] and (gji )j∈[ni ] , i ∈ [r], such that for all ℓ ∈ [q]
v̂ℓ =

X

i∈[r]

=

X




 

X

fκi Bκi  

κ∈[ki ]

ℓ

X

X

j∈[ni ]



gji Aij 

ℓ

Bκi (ℓ)fκi gji Aij (ℓ)

i∈[r] κ∈[ki ],j∈[ni ]

If we define r matrices Zi ∈ Cki ,ni through Zi = f i (g i )∗ , i.e. Zi (κ, j) = fκi gji , we see that we can write the latter
sum as
X
X X
biℓ , Zi aiℓ ,
Bκi (ℓ)(Zi Ai(·) (ℓ))κ =
i∈[r]

i∈[r] κ∈[ki ]

where we defined new vectors aiℓ ∈ Cni and biℓ ∈ Cki through
aiℓ (j) := Aij (ℓ),

biℓ (κ) := Bκi (ℓ).

we have rewritten our deconvolution problem to a problem of recovering a matrix tuple Z = (Zi ) ∈
L Hence,
ki ,ni
from the measurements
C
i∈[r]


v̂ = 

X

i∈[r]



biℓ , Zi aiℓ 

.

ℓ∈[q]

Let us denote the linear measurement map
M

i∈[r]

Cki ,ni → Cq ,



Z →

X

i∈[r]



biℓ , Zi aiℓ 

ℓ∈[q]

by A.
In this paper, we want to assume that the basis coefficients g i are sparse, a situation considered also in (Ling
and Strohmer 2015 [11]). We do not, however, pose any requirements on f i . The sparsity of the g i -coefficients
has the consequence that the matrices Zi = f i (g i )∗ are column-sparse, since only the columns corresponding to

2

indices in supp g i are not equal to zero. Since it is well-known that this structure is promoted by the ℓ1,2 - norm
(Eldar and Mishali 2009 [4]; Stojnic, Parvaresh and Hassibi 2009 [14])
kM k1,2 =

n
X
i=1

kM (i)k2 ,

where M (i) is the i:th column of M , this naturally calls for the following recovering procedure
X
kZi k1,2 subject to A(Z) = b.
min kZk1,2 :=

(P1,2 )

i∈[r]

Despite this approach arguably being canonical for recovering column-sparse matrices, there has not been any
theoretical analysis of the program P1,2 when the measurement map A is as above.
The article (Ling and Strohmer 2015 [11]) has provided (in the case that r = 1) a discussion on ℓ1 -minimization
for recovering Z
min kZk1 subject to A(Z) = b,

(P1 )

where the ℓ1 -norm of a matrix is simply defined as the sum over the absolute values its entries. In particular, they
recover the well-known asymptotic result that m & sk log(nk) measurements suffices for P1 to be successful at
recovering an sk-sparse matrix in Ck,n . At the end of the paper, they perform numerical experiments which show
that ℓ1,2 -minimization actually performs better than ℓ1 -minimization at recovering column-sparse matrices. They
claim that they have theoretical guarantees also for the P1,2 -problem, but have as of today not yet published any.
In this work, we will, to some extent, provide that missing theoretical explaination, by generalizing the results
of (Ling and Strohmer 2015, [11]). We even improve them a bit by additionally including an argument for stability
of the problem, in the sense that approximately column-sparse matrices will be approximately recovered by P1,2 .
Also, our results are a bit more robust to noise. In addition to this, we consider the general case of r > 1, i.e., we
include the demixing part of the problem.
Although the main route of many of the arguments are the same as in the mentioned paper, several adjustments
has had to be made for the argument to work also for the ℓ1,2 -case. Many proofs become more difficult from a
technical point of view. Also, a dual certificate type of condition for stability and robustness of ℓ1 -minimization
from (Foucart and Rauhut 2013 [5]) has had to be generalized to ℓ1,2 -minimization.
The remainder of this introduction is devoted to discussing related work. The rest of the paper will then be
organized as follows: in Section 2, we present the measurement model we use, our main result, as well as an
outline of the proof of it. The details of the proofs are postponed to Section 3.

1.1

Related work

ℓ1,2 -minimization has been theoretically analysed before, i.e. in the resources (Eldar and Mishali 2009 [4]; Stojnic,
Parvaresh and Hassibi 2009 [14]) mentioned above. In (Asi, Mantzel and Romberg 2009 [2]), it is mentioned as
a way of solving the blind deconvolution problem, explicitly with applications in communication in mind.
ℓ1,2 -minimization is by no means the only possible way to recover the matrix tuple Z. In fact, one can
alternatively use the fact each matrix Zi = f i (g i )∗ is low-rank as a prior. This naturally calls for nuclear normminimization (Fazel, Recht and Parrilo 2010 [12]). The nuclear norm of a matrix tuple is canonically defined as
the sum of the nuclear norms kZi k∗ of each matrix Zi . The nuclear norm of a matrix Zi is thereby given by the
sum of the singular values of Zi . Hence,
X X
X
σj (Zi ).
kZi k∗ =
kZk∗ =
i∈[r] j∈[ni ]

i∈[r]

3

The paper (Ling and Strohmer 2015 [10]) treats recovery of low-rank matrix tuples using nuclear norm-minimization:
they are able to prove that under several technical conditions resembling the ones we will consider in this paq
2
per, log(q)
3 & r max(k, n) log(r + 1) is enough to secure that the nuclear norm minimization procedure recovers the correct matrix tuple. In (Jung, Krahmer and Stöger 2016 [13]), it was even shown, by different
q
authors, that the quadratic dependence on r can be removed (to be precise, their result requires log(q)
2 &

 p
2
r(k log (k) + n) log r n log(nq) + log(q) ).
However, as was pointed out in (Ling and Strohmer 2015 [11]), numerical experiments show that both ℓ1 and ℓ1,2 -minimization perform significantly better than nuclear norm minimization when it comes to recovering
matrices with the structure described above. This is not hard to argue heuristically: Assuming r = 1, the above
approach tries to recover a Ck,n -matrix of rank 1, which needs an order of n + k measurements. On the other
hand P1,2 (or P1 ) tries to recover an s-column sparse (or sk-sparse) Ck,n matrix , which only needs sk log (nk).
For really small sparsities and moderate k, sk can be smaller than n + k. Therefore, the authors of the mentioned
paper concentrate their efforts, as will we, on analysing the ℓ1 -minimization (and ℓ1,2 -minimization, respectively).
As observant readers already may have pointed out, the ”true dimension” of the problem of recovering a matrix
f g ∗ with f ∈ Rk and g ∈ Rn s-sparse is neither s·k nor n+k, but instead s+k (a mathematically precise statement
of this claim is provided in (Kech and Krahmer 2016 [7])). As of today, to the best knowledge of the author, there
are no convex minimization procedures which succeed which such few measurements. In this context, ( Bresler,
Lee and Wu 2013 [9]) should be mentioned. In that paper, the authors describe a alternating minimization
procedure which under some additional conditions on the vectors f and g succeed with high probability already
when q is of the order of s + k.

2

Main Result

In this section, the main result together with an outline of the proof will be presented. In order to do that, we
first need to describe our measurement model as well as the assumptions we make.
Let us begin by describing the properties of the basis vectors biℓ and aiℓ . The biℓ are assumed to be fixed and
known (this corresponds to the spaces Wi to be fixed and known). Also, we assume that each tuple (biℓ )ℓ∈[q] forms
a Parseval Frame of Cki , i.e
X
biℓ (biℓ )∗ = id .
ℓ∈[q]

In order for our proof to work, we will have to assume that the frames are somewhat well-conditioned. Concretely,
we will assume that there exists positive numbers µ− and µ+ so that kqi kbiℓ k22 ∈ [µ2− , µ2+ ] for all i and ℓ.
The vectors aiℓ are assumed to be known, but not fixed. Rather, we assume them to be independent Gaussian
vectors in their respective spaces. The spaces Ui from above are hence uniformly randomly chosen, and the
bases of them as well. A statement of the form ”the solution of P1,2 is equal to the ground truth signal with
high probability” will hence mean that the method works for a very high fraction of possible subspaces Ui and
sparsifying transforms in those respective spaces.
L
The signal model is as follows: we consider matrix tuples Z = (Zi )i∈[r] ∈ i∈[r] Cki ,ni , where each matrix Zi
is assumed to be column-supported on some set Si , i.e. only the columns Zi (j) for j ∈ Si are nonzero.
N Si has
cardinality si . Alternatively, we will sometimes speak of matrix tuples being supported on sets S = i∈[r] Si ,
with the exact same meaning. Note that the si are not assumed to be equal, and in particular, some of them
can even be equal to zero (which corresponds to Zi = 0). To simplify the notation somewhat, we will use the
following short-hands:
X
X
ni ,
si , n =
s=
i∈[r]

i∈[r]

k ∗ = max ki ,

k∗ = min ki

i∈[r]

i∈[r]

4

N
PM denotes the orthogonal projection on to the space of matrix tuples supported on M ⊆
i∈[r] [ni ]. When
convenient, we will also use the notation XS := PS X .
It will at several places in the article come in handy to decompose the map A. We define Ai : Cki ,ni → Cq
through
i

Ai (Z) = A((0, . . . , 0, Z , 0, . . . , 0)),
and also Aij : Cki → Cq through
Aij ν = Ai (νe∗j ).
In our main result, we will assume the following asymptotics of the number of measurements q:


P
 ∗
µ4+ k∗ i∈[r] si ki
2 ∗
nk
q & µ+ k s log 1 +
·
log
.
2
ǫ
µ k∗
−

ǫ > 0 is an upper bound on the failure probability. This amount of measurements
is, up to logarithmic term,
P
more or less what could be expected: we are trying to recover a signal from a i∈[r] si ki -dimensional structure
P
embedded in a i∈[r] ni ki -dimensional space. Intuitively (compare for instance (Candes and Tao 2005 [3])), this
calls for
X
X


ni ki
si ki log
q&
i∈[r]

i∈[r]

compressive measurements. Note that if the ki are not varying to much with i, we have
P
∗
i∈[r] ni ki ≈ k n. In particular, we have equality for r = 1.

P

i∈[r] si ki

≈ k ∗ s and

To simplify reading the paper, let us summarize all of our assumptions in a list.

(a) a-statistics. The vectors aiℓ ∈ Cni are independent Gaussians.
(b) Parseval Frames. For each i we have
X

biℓ (biℓ )∗ = id .

ℓ∈[q]

(c) b-norms under control: There exists µ− , µ+ > 0 with
q
i 2
ki kbℓ k2

∈ [µ2− , µ2+ ]

for each i and ℓ.
(d) q-asymptotics We have
q&

µ2+ k ∗ s log


1+

µ4+ k∗

P

i∈[r]

µ2− k∗

si ki



· log



nk∗
ǫ



.

The main result of this paper reads as follows.
Theorem 2.1. Under the assumptions (a) to (d), every matrix tuple Z0 with Zi0 si -column sparse is the unique
solution of P1,2 with a probability larger than 1 − ǫ.
In fact, (a) to (d) will even imply stable and robust recovery in the sense that for any matrix tuple Z0 and
y = A(Z0 ) + ν with kνk2 ≤ σ, with a probability larger than 1 − 3ǫ, any solution Z ∗ of the program
min kZk1,2 subject to kA(Z) − yk2 ≤ σ
obeys
√
kZ ∗ − Z0 kF ≤ C1 kPS c Z0 k1,2 + (C2 + C3 s)σ,
where C1 , C2 and C2 are universal constants.
5

Remark 2.2. The assumptions we have made are the same as in (Ling and Strohmer 2015 [11]), except for the
(d)-assumption. The mentioned paper only deals with the case r = 1, but in that case, their equivalent of the
(d)-assumption reads
q
& µ2+ ks log(nk).
log2 (q)
If we put ǫ = q 1−α in our assumption (d) (as is made in the mentioned article) and assume that
∗

(d)∗
µ2+
µ2−

is close to

one (note that k = k∗ in the case r = 1), we arrive at
q & µ2+ ks log(1 + µ2+ sk) log(nkq α−1 ).

(d)r=1

Compared to (d∗ ), we gain a log(q)-term but lose a log(sk)-term. Since log(q) & log(1 + µ2 sk) for q & sk, we
see that (d)∗ in fact implies (dr=1 ). Hence, the (d)r=1 -assumption slightly weaker than (d)∗ . The reason for this
improvement is of proof-technical nature: We apply a strong version of the Matrix Bernstein inequality, and it is
probably possible to obtain this rate also for ℓ1 -minimization.
Looking a bit closer, we however find a way in which ℓ1,2 -minimization inevitably outperforms ℓ1 -minimization:
Under assumptions (a) to (c), together with (d)∗ , the authors of the mentioned article prove that the regularized
ℓ1 -minimization program, with a probability larger than q 1−α (the implicit constant is dependent on the parameter
α), obeys
√
kZ ∗ − Z0 kF ≤ (C1 + C2 ks)σ
for every
√ s-column
√ sparse Z0 . This error bound is worse than the one we prove for exactly column-sparse signals
(since ks ≥ s), and also does not account for small deviations from the sparsity assumption. Hence, our
analysis indicates that ℓ1,2 -minimization really works better than ℓ1 -minimization for recovering s-column sparse
matrices using the considered type of measurements.

2.1

Outline of the proof.

The proof of Theorem 2.1 will inevitably be technically quite involved. In the following, we will describe its basic
route. All details are given in the next section. We again point out that we closely follow the paper (Ling and
Strohmer 2015 [11]).
The start of the argument is the following lemma. It is a generalization of (Foucart and Rauhut 2013 [5, Th.
4.33]), which is a corresponding statement about ℓ1 -minimization. It will make use of the regularized program
min kZk1,2 subject to kA(Z) − yk2 ≤ σ.

σ
(P1,2
)

To simplify the notation, let us introduce the short hand Xb for the matrix tuple formed by normalizing each
column of each submatrix of X . To be precise,
( X (j)
i
if Xi (j) 6= 0
bi (j) := kXi (j)k2
X
0
else.
N
L
ki ,ni
and let S ⊆
Lemma 2.3. Let Z0 ∈
i∈[r] [ni ] be arbitrary. Consider a linear map A from
i∈[r] C
L
q
ki ,ni
to
C
and
noisy
measurements
y
=
A(Z
)
+
n with knk2 ≤ σ.
C
0
i∈[r]
Suppose that
kPS A∗ APS − PS kF →F ≤ δ

max kPS A∗ Aij k2→F ≤ β

(i,j)∈S c

for some δ ∈ [0, 1) and β ≥ 0. Also suppose that there exists a matrix tuple Y = A∗ υ (an approximate dual
certificate) with
√
kPS (Y − Zb0 )k ≤ η, kYS c k∞,2 ≤ θ and kυk2 ≤ τ s.
6

If ρ = θ +

ηβ
1−δ

σ
< 1, any solution Z ∗ of P1,2
obeys

√
kZ ∗ − Z0 kF ≤ C1 kPS c Z0 k1,2 + (C2 + C3 s)σ.

The constants are given by
C1 =

2β
2
+
1 − ρ (1 − ρ)(1 − δ)

where we defined µ =

√

C2 =

2µη
2βµη
+
+ 2µ
1 − ρ (1 − ρ)(1 − δ)

C3 =

2τ
2βτ
+
,
1 − ρ (1 − ρ)(1 − δ)

1+δ
1−δ .

The road ahead is now clear: what we need to do is to prove that with the assumptions we have made, the
parameters δ and β will probably be small. We will also have to construct an approximate dual certificate Y with
η, θ and τ as small as possible. Most of these proofs in the following will follow this general structure:
1. Write the stochastic matrix at hand as a sum of random, centered matrices.
2. Estimate the parameters Orlicz-Norms (see Section 3) and variances of the matrices involved.
3. Apply results about norm concentration of sums of independent matrices (see Theorem 3.3 and Corollary
3.4).
Bounding δ and β is particularly natural using the above strategy. The following results hold.
Lemma 2.4. Under the assumptions (a) to (d), we have
kPS A∗ APS − PS kF →F ≤

1
4

(1)

with a probability larger than 1 − ǫ.
Lemma 2.5. Suppose that (1) and assumption (d) is true. Then
max c kPS A∗ Aij k2→F ≤

(i,j)∈S

5
4

with a probability greater than 1 − ǫ.
It now only remains to construct the dual certificate Y. Although Lemma 2.3 only calls for an approximate
dual certificate, we will construct an exact one, just as in the paper (Ling and Strohmer 2015 [11]). This does
not only yield good results, but has the main technical advantage that it avoids using the so-called golfing scheme
(Gross 2011 [6]), which would need further assumptions on our frames (biℓ ). It should be noted that this comes
at the cost of us not being able to consider more structured (aiℓ )-constructions. For more details on this issue,
see (Ling and Strohmer 2015 [10, 11].)
So, the certificate we will use is defined as follows:
υ = AS (A∗S AS )−1 Zb0 ,

Y = A∗ υ,

(2)

where we introduced the short-hand AS = APS The following lemma shows that it with very high probability
will have the properties we need.
Lemma 2.6. Under assumptions (a)-(d) and additionally that (1) is true, υ and Y defined in (2) obeys
YS = PS Zb0 ,

kYS c k∞,2 ≤

with a probability larger than 1 − ǫ.

7

1
2

kυk ≤

√ √
2 5
s
3

With the above results at hand, the main result is easily deduced.
Proof of Theorem 2.1. We want to apply Lemma 2.3. Lemma 2.4 together with assumptions (a) to (d) secure
that with a failure probability smaller than ǫ, (1) holds, i.e. that δ ≤ 14 . (1) also makes Lemma 2.5 appliciable,
which proves that β ≤ 54 with a probability of failure smaller than ǫ. It also makes the Lemma 2.6 about the dual
√
certificate appliciable, which implies that η = 0, τ ≤ 2 3 5 and θ ≤ 12 with a probability of failure smaller than ǫ.
ηβ
≤ 12 < 1 with a probability larger than 1 − 3ǫ, which is what was to be proven. The
All in all, ρ = θ + 1−δ
corresponding bounds on C1 , C2 and C3 are
C1 =

3

32
3 ,

C2 =

√4 ,
5

C3 =

√
96 5
9 .

Proofs

In this section, we present all of the technical details omitted above.

3.1

Lemma 2.3

Let us begin by performing a (relatively straight-forward) calculation of the subdifferential of k · k1,2 .
L
Lemma 3.1. Let Z0 ∈ i∈[r] Cki ,ni be supported on the set S. Then the subdifferential of k · k1,2 at Z0 , i.e. the
L
set of ξ ∈ i∈[r] Cki ,ni with the property
∀H ∈

M

i∈[r]

Cki ,ni : kZ + Hk1,2 ≥ kZk1,2 + Re(hH, ξi),

is given by the direct sum of the individual sub-differentials ∂Zi (k · k1,2 ), i = 1, . . . , r, where ∂Zi (k · k1,2 ) is given
by
n
o
(j)
V ∈ Cki ,ni |V (j) = kZZii(j)k
.
(3)
,
j
∈
S
,
kV
(j)k
≤
1,
j
∈
/
S
i
2
i
2

Proof. By testing with H’s with only one Hi 6= 0, we see that ∂Z0 k · k1,2 has the claimed direct sum structure.
To calculate ∂Zi (k · k1,2 ), we need to characterize the matrices V with
X
X
X
kZi (j) + H(j)k2 ≥
Re(hV (j), H(j)i)
(4)
kZi (j)k2 + Re(hV (j), H(j)i) +
j∈[ni ]

j∈Si

j ∈S
/ i

for all H ∈ Cki ,ni . First, it is easy to see that a matrix tuple in (3) has this property. To see that ∂Zi k · k1,2
is contained in the set (3), begin by testing (4) with arbitrary matrices H supported on single columns with
indices in Sic . The resulting inequality implies that the corresponding columns have norm at most 1. Similarly
for j ∈ Si , by testing with the matrix with j:th column ±Zi (j) and 0 else, we see that Re(hZi (j), V (j)i) = 1, i.e.
(j)
+ uj with Re(uj , Zi (j)) = 0. To see that uj = 0, test with the matrix having j:th column τ uj for
V (j) = kZZii(j)k
2
τ > 0 and zero else. Since kv + wk22 = kvk22 + kwk22 + 2Re(hv, wi), this implies
p
q
kZi (j)k22 + τ 2 kuj k22 − kZi (j)k2
2
2
2
2
2
kZi (j)k2 + τ kuj k2 ≥ kZi (j)k2 + τ kuj k2 ⇒ kuj k2 ≤
, τ > 0.
τ

By letting τ → 0, we obtain kuj k2 = 0.

We can now prove Lemma 2.3, using the same ideas as in the proof of its ℓ1 -counterpart (Foucart and Rauhut
2013 [5, Th. 4.33]).
8

Proof. Let us denote H = Z ∗ − Z0 . Then we have due to the triangle inequality and Lemma 3.1
D
E
kZ ∗ k1,2 = kZ0 + Hk1,2 ≥ kPS Z0 + Hk1,2 − kPS c Z0 k ≥ kPS Z0 k + Re PS Zb0 , HS
+ hξS c , HS i − kPS c Z0 k

σ
for every ξ with kξk∞,2 ≤ 1. Now since Z0 obeys the constraint of P1,2
, there must be kZ0 k1,2 ≥ kZ ∗ k1,2 . Using
this, the above inequality, and choosing ξ appropriately, we obtain
D
E
D
E
kHS c k1,2 ≤ kZ0 k1,2 − kPS Z0 k1,2 + kPS c Z0 k1,2 + PS Zb0 , HS ≤ 2kPS c Z0 k1,2 + P Zb0 , HS .
(5)

Due to the first property of Y, we have
E
E
D
D
PS Zb0 , HS ≤ PS (Zb0 − Y), HS + |hYS , HS i| ≤ ηkHS kF + |hY, Hi| + |hYS c , HS c i| .

(6)

Due to kPS A∗ APS − PS kF →F ≤ δ, we furthermore have

1
1
1
kPS A∗ APS HkF ≤
kPS A∗ AHkF +
kPS A∗ APS c HkF .
1−δ
1−δ
1−δ
Now we estimate both of these two terms separately, starting with the second one. We have, due to
X
A(i,j) (Hi (j)),
A(HS c ) =
kHS kF ≤

(7)

(i,j)∈S c

that
kPS A∗ A(HS c )kF ≤

X

(i,j)∈S c

kPS A∗ A(i,j) (Hi (j))kF ≤ β

X

(i,j)∈S c

kHi (j)k2 ≤ βkHS c k1,2 ,

(8)

where we in the second to last step used that kPS A∗ Aij k2→F ≤ β for all (i, j) ∈ S c . Now for the first term in (7).
Since kPS A∗ k22→F = kPS A∗ APS kF →F ≤ 1 + δ, we have
√
√
kPS A∗ A(H)kF ≤ 1 + δkA(H)k2 ≤ 2 1 + δσ,
(9)
σ
where the last estimate follows from the constraint of P1,2
:

kA(H)k2 ≤ kA(Z0 ) − yk2 + ky − A(Z ∗ )k2 ≤ 2σ.

Combining (7) with (8) and (9),we obtain

1  √
2 1 + δσ + βkHS c k1,2
1−δ
√
We may furthermore deduce from the fact that Y = A∗ υ and kυk2 ≤ 2τ s
√
|hY, Hi| = |hυ, A(H)i| ≤ kυk2 kA(H)k2 ≤ 2τ sσ
kHS kF ≤

(10)

(11)

Finally, due to the second assumption on Y, |hYS c , HS c i| ≤ kYS c k∞,2 kHS c k1,2 ≤ θkHS c k1,2 . Putting this estimate
together with (10) and (11) into (6) yields
D
E
√
2η √
ηβ
1 + δσ +
PS Zb0 , HS ≤
kHS c k1,2 + 2τ σ s + θkHS c k1,2
1−δ
1−δ
Which, put into (5) and identifying the expressions defined in the statement of the theorem, reads
√
kHS c k1,2 ≤ 2kPS c Z0 k1,2 + 2ηµσ + 2τ σ s + ρkHS c k1,2 .
Which together with (10) implies



β
kHS c k1,2
kHkF ≤ kHS kF + kHS c kF ≤ 2µσ + 1 +
1−δ


√ 
β
1
≤ 2µσ + 1 +
·
· 2kPS c Z0 k1,2 + 2ηµσ + 2τ σ s ,
1−δ
1−ρ

which is exactly what we aimed to prove.

9

3.2

A Technical Tool from Random Matrix Theory.

Just as in the paper (Ling and Strohmer [11]), the main technical tool is a version of the Matrix Berstein inequality.
We use the one from (Koltchinskii 2013 [8]). It makes use of the 1-Orlicz-Norm of a random matrix:
kΨkψ1 = inf E (exp(kΨ/uk2→2)) ≤ 2.
u≥0

It is possible to prove (Vershynin 2012 [16, Lem 5.5]) that the Orlicz norm is equivalent to
1
−p

kΨkψ1 := sup p−1 E (kΨkp2→2 )

.

p≥1

This makes it clear that it is reasonable to define the ψq -norm of a random variable X for q ≥ 1 through
kXkψq ≃ sup p

1
−q

1
−p

E (|X|p )

.

p≥1

We then have k|X|q kψ1 ≤ qkXkqψq , since
q

k|X| kψ1 = sup p

−1

1
−
E (|X|qp ) p

q


 1 1
1 1
1
1 q
−q q
−q q
qp − pq
p −p
= sup (pq) q E (|X| )
= sup p q E (|X| )
≤ qkXkqψq .
p≥1

p≥1

p≥q

It is also clear that if X and Y are independent, we have
kX · Y kψ1 = sup p−1 E (|X · Y |p )

1
−p

1

= sup p− 2 E (|X|p )

p≥1

1
−p

p≥1

1
−p

1

· sup p− 2 E (|Y |p )
p≥1

= kXkψ2 kY kψ2

(12)

For a vector g = (g(1), . . . g(d)) ∈ Cd with independent Gaussian entries, with variances s2i , we have (see
(Vershynin 2012 [16, Example 5.8.1, Lemma 5.9] ))
X
X
(13)
s2i .
kg(i)k2ψ2 .
kgk2ψ2 .
i∈[d]

i∈[d]

Remark 3.2. Note that in this paper, kgkψ2 is for a random vector g ∈ Cd , despite of the notional similarity,
not the subgaussian norm defined in (Vershynin 2012 [16]). Instead, we view it as a linear map Cd → R and use
the definition from above, i.e. kgkψq = kkgk2kψq .
With this terminology at hand, we may formulate the theorem. To keep things simple, we omit some details,
in particular regarding the values of the appearing constants. These can be found in the referenced source.
Theorem 3.3. (Simplified version of Koltchinskii 2013 [8, Theorem 4, Corollary 1])2 Consider a finite sequence (Ψℓ )ℓ∈[q] of independent, centered and self-adjoint random matrices with dimension M × M , with R :=
max1≤1≤q kΨℓ kψ1 < ∞. Let S denote the matrix
S=

q
X

Ψℓ

ℓ=1

and define


2 In

σ 2 := max k

X

ℓ∈[q]

E (Ψℓ Ψ∗ℓ ) k2→2 , k

X

ℓ∈[q]



E (Ψ∗ℓ Ψℓ ) k2→2  .

an earlier version of this article, a similar bound, which is only true for identically distributed matrices, was erroneously used.

10

Then we can bound
P (kSk2→2 ≥ t) ≤ PM,σ2 ,R,q (t),
where PM,σ2 ,R,q (t) hasthe following property: There exist constants C0 , C1 and C2 such that for every t satisfying

0 < tR log 1 +

C 2 R2 q
σ2

< C1 σ 2 , we have




For t with tR log 1 +

1
t2

PM,σ2 ,R,q (t) ≤ 2M exp −
C0 σ 2 + R log 1 +

C 2 R2 q
σ2



C 2 R2 q
σ2



 .
t

≥ σ 2 , we instead have


t
1

PM,σ2 ,R,q (t) ≤ 2M exp −
C0 R log 1 +

C 2 R2 q
σ2





As was pointed out in (Tropp 2012 [15]), a theorem like the previous one immediately implies a corresponding
statement for non-square (and also square but non-self-adjoint) matrices. Let us state and prove this assertion.
Corollary 3.4. Consider a sequence (Ψℓ )ℓ∈[q] of independent centered random matrices with dimension M × N .
Adopting the notation of the previous theorem, we then have
P (kSk2→2 ≥ t) ≤ PM+N,σ2 ,R,q (t).
Sketch of Proof. (The idea is from (Tropp 2012 [15])). For a matrix M ∈ CM,N , define the dialation S (M ) ∈
CM+N,M+N through


0
M
S (M ) =
.
M∗ 0
Then kS (M )k2→2 = kM k2→2 . Consequently, S (Ψℓ ) is a sequence of independent and centered self-adjoint
(M + N ) × (M + N )-matrices with the same R and σ 2 -parameters as (Ψℓ ). Hence, the statement follows
immediately from the previous theorem.
We will often use the above theorem to derive bounds on the number of measurements needed for the probability that kSk2→2 to be small for some random matrix S. When doing this, the following observation be very
convenient: Let t > 0. Suppose that we have secured a bound of the form
P (Event) ≤ QPM,σ2 ,R,q (t)
and that

σ 2 + Rt log 1 +

C 2 R2 q
σ2



. t2 log



QM
ǫ

−1

,


R log 1 +

C 2 R2 q
σ2



. t log



QM
ǫ

−1

(14)

By applying the bounds provided in Theorem 3.3 for large and small t separately, we can then conclude that
P (Event) < ǫ.

3.3

Bounding the Parameters β and δ.

With the two results presented in the last section in our toolbox, it is possible to bound the parameters β and δ
with high probability.

11

For a start, note that there is no fundamental difference between dealing with linear maps on the space of
matrix tuples equipped with the Frobenius norm and matrices defined on CK , for an appropriate K, equipped with
the ℓ2 -norm. We will from now on never comment on this subtlety and instead apply Theorem 3.3 and Corollary
3.4 without explicitely re-interpreting the linear maps on matrix spaces to linear maps on an high-dimensional
CK .
L
Let us now calculate A∗ . We have for Z ∈ i∈[r] Cki ,ni and p ∈ Cq
hA(Z), pi =

X X

biℓ , Zi aiℓ pℓ =

ℓ∈[q] i∈[r]

X

i∈[r]

Zi , pℓ biℓ (aiℓ )∗ = hZ, A∗ pi ,

and hence
(A∗ p)i =

X

pℓ biℓ (aiℓ )∗ .

ℓ∈[q]

Consequently,
(A∗ A(Z))i =

X X

ℓ∈[q] κ∈[r]

hbκℓ , Zκ aκℓ i biℓ (aiℓ )∗ =

X X

biℓ (bκℓ )∗ Zκ aκℓ (aiℓ )∗

ℓ∈[q] κ∈[r]

We can now provide the proofs, starting with Lemma 2.4.
Proof of Lemma 2.4. We have
(PS A∗ APS (Z))i =

X X

ℓ∈[q] κ∈[r]

hbκℓ , Zκ (aκℓ )Sκ i biℓ (aiℓ )∗Si =

X X

biℓ (bκℓ )∗ Zκ ακℓ (αiℓ )∗ ,

ℓ∈[q] κ∈[r]

where we for i, ℓ defined the variables αiℓ = (aiℓ )Si , which again are independent and Gaussians in their respective
spaces, since they
 are projections of independent Gaussians. Due to further basic properties of Gaussians, we
have E ακℓ (αiℓ )∗ = δκi idSi . Due to assumption (b), we furthermore have


X
,
biℓ (biℓ )∗ Zi 
Z=
ℓ∈[q]

i∈[r]

and hence

(PS A∗ APS − PS ) =
where we defined Ψℓ :

L

i∈[r]

Cki ,ni →

L

i∈[r] C

ki ,ni

Ψℓ (Z)i =

X

ℓ∈[q]

Ψℓ − E (Ψℓ ) ,

through

X

biℓ (bκℓ )∗ Zκ ακℓ (αiℓ )∗

κ∈[r]

The random variables Ψℓ − E (Ψℓ ), ℓ = 1, . . . , q, are independent and, of course, centered. In order to apply
Theorem 3.3, we need to estimate the ψ1 -norms of them. Towards this, let us begin by calculating kΨℓ (Z)kF for
a fixed Z. We have
kΨℓ (Z)k2F =
≤

X

i∈[r]

X

i∈[r]

X

κ∈[r]

hbκℓ , Zκ ακℓ i biℓ (αiℓ )∗


kbiℓ k22 kαiℓ k22 

X

k∈[r]

2
F

=

X

i∈[r]

kbiℓ (αiℓ )∗ k2F
2

kbκℓ k2 kZκ kF kακℓ k2  ≤
12

X

i∈[r]

X

k∈[r]

2

hbκℓ , Zκ ακℓ i

kbiℓ k22 kαiℓ k22

X

j∈[r]

kbjℓ k22 kαjℓ k22

X

κ∈[r]

kZκ k2F

We used Cauchy-Schwarz, kAvk2 ≤ kAkF kvk and kuv ∗ kF = kuk2 kvk2 . Hence, kΨℓ (Z)kF ≤
kZkF , and consequently
X
kbiℓ k22 kαiℓ k22 .
kΨℓ kF →F ≤

P

i 2
i 2
i∈[r] kbℓ k2 kαℓ k2

·

i∈[r]

This is an expression which obeys
kkΨℓkF →F kψ1 ≤ 2

X

i∈[r]

kbiℓ k22 kαiℓ k2ψ2 .

µ2+ X
ki si .
q
i∈[r]

We used kX 2 kψ1 ≤ 2kXk2ψ2 , (13), and assumption (c). Note that we can use the same (asymptotic) estimate for
the ψ1 -norm of Ψℓ − E (Ψℓ ), as was pointed out in (Vershynin 2012 [16]). We have hence managed to bound the
R-parameter in Theorem 3.3.
Let us move on to the σ 2 -parameter. Ψℓ , and therefore also Ψℓ − E (Ψℓ ), is self-adjoint, since
+
*
+
*
X
X
X X
κ i ∗
i
κ ∗
i κ ∗
κ
i ∗
= hZ, Ψℓ (Y)i .
bℓ (bℓ ) Yi αℓ (αℓ )
Zκ ,
bℓ (bℓ ) Zκ αℓ (αℓ ) , Yi =
hΨℓ (Z), Yi =
i∈[r]

i∈[r]

κ∈[r]

κ∈[r]

Therefore,


2
E ((Ψℓ − E (Ψℓ ))∗ (Ψℓ − E (Ψℓ ))) = E (Ψℓ − E (Ψℓ ))2 = E Ψ2ℓ − E (Ψℓ ) .

E (Ψℓ )2 is given by E (Ψℓ )2 (Z)i = kbiℓ k22 biℓ (biℓ )∗ Zi and
X X
X
biℓ kbjℓ k22 (bκℓ )∗ Zκ ακℓ kαjℓ k22 (αiℓ )∗ .
biℓ (bjℓ )∗ Ψℓ (Z)j αjℓ (αiℓ )∗ =
Ψ2ℓ (Z)i =
j∈[r] κ∈[r]

j∈[r]

Lemma 3.5 (which is yet to be proven) reads

(si + 2) idSi
 

j 2
κ
i ∗
E αℓ kαℓ k2 (αℓ ) = sj idSi


0

Consequently,

i=j=κ
i = κ 6= j
else.

X

E Ψ2ℓ (Z)i = (si + 2)kbiℓ k22 biℓ (biℓ )∗ Zi +
sj kbjℓ k22 biℓ (biℓ )∗ Zi .
j6=i

This implies



2

2

E Ψℓ − E (Ψℓ )



i



= (si + 1)kbiℓk22 +

X
j6=i





2
X
µ

sj kbjℓ k22  biℓ (biℓ )∗ ≍
sj kj  biℓ (biℓ )∗ .
q
j∈[r]

We used assumption (c) at the end. Here, µ is meant to be understood as µ+ in the upper bound and µ− in the
lower bound. Summing over ℓ ∈ [q] and utilizing assumption (b), we arrive at
X

ℓ∈[q]



µ2 X
2
E Ψ2ℓ − E (Ψℓ ) ≍
si ki
q
i∈[r]

13



µ2 P
µ2 P
2
I.e. R . q+
i∈[r] si ki and σ ≍ q
i∈[r] si ki . Towards applying Theorem 3.3, we note that these bounds
together with assumption (d) imply that



P
P

−1

X

2
1
C2 µ4+ i∈[r] si ki
µ2
i∈[r] si ki
log
si ki 1 + log 1 +
σ 2 + 21 R log 1 + C2σR2 q . q+
.
2
ǫ
µ−
4
i∈[r]


1
R
log
1+
4

We used that

P

i∈[r] si ki

2

C2 R q
σ2



.

µ2+
2q

X

i∈[r]

P
−1

1
i∈[r] si ki
log
si ki .
.
ǫ
16

≤ nk ∗ . We now Theorem 3.3 to conclude that
P kPS A∗ APS − PS kF →F >

(Note that PS A∗ APS − PS is defined on the

1
2



≤ P(P

i∈[r]

si ki ),σ2 ,R,q

1
2



.

o

n
L
ki ,ni
|
supp
Z
⊆
S
).
C
-dimensional
space
Z
∈
s
k
i
i
i∈[r]
i∈[r]

P

Since we have a bound of the form (14) for t = 41 , the discussion following Theorem 3.3 finishes the proof.
It remains to prove the left out lemma.

Lemma 3.5. Let ακℓ be defined as above. We then have

(si + 2) idSi
 

E ακℓ kαjℓ k22 (αiℓ )∗ = sj idSi


0

i=j=κ
i = κ 6= j
else.

Proof. In the case that i 6= κ, we have, due to the independence







E ακℓ kαjℓ k22 (αiℓ )∗ = E ακℓ kαjℓ k22 E (αiℓ )∗ = E ακℓ kαjℓ k22 · 0 = 0.
In the case that i = κ, but j is distinct from i, we have, again due to independence





E ακℓ kαjℓ k22 (αiℓ )∗ = E kαjℓ k22 E αiℓ (αiℓ )∗ = sj idSi .

For the final case that all three indices are equal, we first note that αiℓ ∼ ρi θi , with ρi , θi independent, ρi ∼ kαiℓ k,
i.e. is χsi -distributed, and θi uniformly distributed over Ssi −1 . Hence


E αiℓ kαiℓ k22 (αiℓ )∗ = E ρ4i E (θi θi∗ ) = si (si + 2) s1i idSi = (si + 2) idSi ,

where the second to last equation follows from
X
X




E αiℓ (κ)2 E αiℓ (λ)2 = si · 3 + si (si − 1) = si (si + 2)
E αiℓ (κ)4 +
E ρ4i =
κ∈[si ]

κ6=λ∈[si ]

Now that we have the δ-parameter under control, the β-parameter is easy to handle.
q
p
Proof of Lemma 2.5. (1) implies that kPS A∗ k2→F = kPS A∗ APS kF →F ≤ 54 , which in turn implies that
kPS A∗ Aij k2→F ≤

14

√

i
5
2 kAj k2→2 .

It is furthermore clear that kAij k2→2 =

q
p
k(Aij )∗ Aij k2→2 = kP(i,j) A∗ AP(i,j) kF →F . The latter expression can

be dealt with just as the corresponding one in Lemma 1 - Theorem 3.3 implies for fixed (i, j)

P kP(i,j) A∗ AP(i,j) − P(i,j) kF →F > 41 ≤ P1,σ2 ,R,q ( 41 )




2
2
µ2
with R . q+ ki and σ 2 ≍ µq ki . In particular, we have max σ 2 + R log 1 + C2σR2 q , R log 1 +
1
16

∗
log( nkǫ )−1

under assumption (d), and we way

a union bound over all (less than nk ∗ ) pairs (i, j)
theorem.

3.4

C 2 R2 q
σ2



.

hence conclude that P1,σ2 ,R,q ( 14 ) ≤ nkǫ ∗ , which together with
q
proves that supi,j kAij k2→2 ≤ 1 + 41 , and therefore also the

The Dual Certificate

Now we prove that the dual certificate defined in (2) has the properties we need with high probability.
Proof of Lemma 2.6. Let us begin by noting that (1) implies that A∗S AS is invertible, with k(A∗S AS )−1 k ≤
q
Since also kAS kF →2 ≤ 54 , we have
kυk ≤

4
3

q

5 b
4 kZ0 kF

=

4
3.

√ √
2 5
s,
3

where the last equality is true since Zb0 is a tuple of matrices with column-sparsities s1 , . . . sr , and each of the
non-zero columns are normalized. It is furthermore clear that
YS = A∗S υ = A∗S AS (A∗S AS )−1 PS Zb0 = PS Zb0 .

Hence, it just remains to estimate the norms of the columns in Y corresponding to (i, j) ∈
/ S. Towards this, let
us define the matrix tuple
Yb = (A∗S AS )−1 Zb0 .

√
√
b F ≤ 4 √s. Also for any index
Then, due to the near-isometry property of A∗S AS and kZb0 kF = s, 54 s ≤ kYk
3
(i, j)
E
X
X XD
ϕℓ ,
bκℓ , Ybκ (aκℓ )Sκ biℓ aiℓ (j) ∼
Yi (j) =
ℓ∈[q]

ℓ∈[q] κ∈[r]

where we defined ki -dimensional random vectors ϕℓ through
E
XD
bκ , Ybκ ακ bi γℓ
ϕℓ =
ℓ

ℓ

ℓ

κ∈[r]

with γℓ ∈ C Gaussian, independent of all ακℓ ∈ CSκ . To estimate the ψ1 -norm of ϕℓ , we estimate with the
Cauchy-Schwarz inequality and assumption (c)


v
√
uX 2
X
µ+ kκ κ 2 b
u
µ
k
+
i
kbκℓ k2 kYbκ kF kακℓ k2  ≤ √ |γℓ |t
kϕℓ k2 ≤ |γℓ |kbiℓ k2 
kαℓ k2 kYkF .
q
q
κ∈[r]

κ∈[r]

(12) implies that the ψ1 -norm of this expression is smaller than
µ2+ √ ∗ b
k kYkF
q

sX

κ∈[r]

15

2

kακℓ k2 kκ

,
ψ2

qP
κ 2
where we used that univariate Gaussians have ψ2 -norm . 1. The term k
κ∈[r] kαℓ k2 kκ kψ2 is in fact the
ψ2 -norm of a vector g with independent Gaussian entries, where for every
qPi = 1, . . . , r, si of the entries have the
variance ki . (13) therefore implies that the expression is smaller than
i∈[r] si ki . We have secured the bound

of

R≤

µ2+ √ ∗ b
k kYkF
q

sX

si ki

i∈[r]

for the application of Corollary 3.4, and we move on to σ 2 .
First, we have


E (ϕ∗ℓ ϕℓ ) = E kbiℓ k22 γℓ2

X



(bκℓ )∗ Ybκ ακℓ (αjℓ )∗ Ybj∗ bjℓ  = kbiℓ k22

κ,j∈[r]





E µ2 k X D
E
XD
i
bκℓ (bκℓ )∗ , Ybκ Ybκ∗ ≍
bκℓ (bκℓ )∗ , Ybκ Ybκ∗
q

κ∈[r]

κ∈[r]

where we used that E αjℓ (ακℓ )∗ = δjκ idSκ . Taking the sum over ℓ ∈ [q], we obtain
+
*
X
µ2+ k ∗ X X κ κ ∗ b b ∗
µ2 k ∗ b 2
∗
E (ϕℓ ϕℓ ) .
bℓ (bℓ ) , Yκ Yκ = + kYk
F
q
q
ℓ∈[q]

κ∈[r]

ℓ∈[q]

where we in the last step used assumption (b). Similarly, one proves
is dealt with similarly: one obtains
k

X

ℓ∈[q]

E (ϕ∗ℓ ϕℓ ) k2→2

2

≤

X
ℓ∈q

kbiℓ (biℓ )∗ k2→2

2

P

ℓ∈[q]

E µ2 k ∗ X
XD
bκℓ (bκℓ )∗ , Ybκ Ybκ∗ . +
q

κ∈[r]

κ∈[r]

*

µ2 k ∗ b 2
= + kYk
F.
q

∗

µ2− k∗ b 2
q kYkF .

E (ϕ∗ℓ ϕℓ ) &

X
ℓ∈q

P

ℓ∈[q]

bκℓ (bκℓ )∗ , Ybκ Ybκ∗

E (ϕℓ ϕ∗ℓ )

+

µ k
b 2 . σ 2 . µ+ k kYk
b 2.
All in all, we have −q ∗ kYk
F
F
q
Towards applying Corollary 3.4, let us note that the bounds we have proven together with assumption (d)
secure that


sX


b 2 P
2
µ4+ k∗ kYk
µ2 k∗ b 2
µ2+ √ ∗ b
F
i∈[r] si ki
σ 2 + 21 R log 1 + C2σR2 q . +q kYk
+
k
k
Yk
s
k
log
1
+
F
i i
F
b2 k
q
µ2 k kY


µ2+ ∗
. q k s log 1 +

− ∗

i∈[r]

µ4+ k∗

P

i∈[r]
µ2− k∗

si ki



.

1
4

log



n(k∗ +1)
ǫ

−1

F

.


∗
b 2 ≍ s and P
We used the inequality between geometric and arithmetic mean ab ≤ 21 a2 + b2 , kYk
F
i∈[r] si ki ≤ sk .
We also have by the same argument


sX
P


µ4+ k∗ i∈[r] si ki
µ2+ √ ∗
C 2 R2 q
R log 1 + σ2
si ki log 1 +
. q k kYkF
µ2 k∗
−

i∈[r]

.

µ2+
∗
q sk


log 1 +

µ4+ k∗

P

i∈[r]

µ2− k∗

si ki



.

1
4

log



n(k∗ +1)
ǫ

Applying Corollary 3.4 together with a union bound yields


1
≤ 2n(k ∗ + 1)Pk∗ +1,σ2 ,R,q ( 12 ) . ǫ,
P max kYi (j)k2 ≥
2
(i,j)∈S
/
and the proof is finished.
16

−1

.

Funding: This Research was funded by the Deutsche Forschungsgemeinschaft (DFG) Grant KU 1446/18-1.
Conflicts of Interest: The author declares that he has no conflict of interest.

References
[1] A. Ahmed, B. Recht, and J. Romberg. Blind deconvolution using convex programming. IEEE Trans. Inf.
Theory, 60(3):1711–1732, 2014.
[2] M. S. Asi, W. Mantzel, and J. Romberg. Channel protection: Random coding meets sparse channels. In
IEEE Information Theory Workshop, Taormina, 2009, pages 348–352, 2009.
[3] E. Candès and T. Tao. Decoding by linear programming. IEEE Trans. Inf. Theory, 51:4203–4215, 2005.
[4] Y. Eldar and M. Mishali. Robust recovery of signals from a structured union of subspaces. IEEE Trans. Inf.
Theory, 55(11):5302–5316, Nov 2009.
[5] S. Foucart and H. Rauhut. A mathematical introduction to Compressed Sensing. Birkhäuser, 2013.
[6] D. Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory,
57(3):1548–1566, 2011.
[7] M. Kech and F. Krahmer. Optimal injectivity conditions for bilinear inverse problems with applications to
identifiability of deconvolution problems. arXiv preprint arXiv:1603.07316, 2016.
[8] V. Koltchinskii. A remark on low rank matrix recovery and noncommutative Bernstein type inequalities. In
From robability to statistics and back: High-dimensional models and processes – a festschrift in honor of Jon
A. Wellner, pages 213–226. Institute of Mathematical Statistics, 2013.
[9] K. Lee, Y. Wu, and Y. Bresler. Near optimal compressed sensing of sparse rank-one matrices via sparse
power factorization. arXiv preprint arXiv:1312.0525, 2013.
[10] S. Ling and T. Strohmer. Blind deconvolution meets blind demixing: Algorithms and performance bounds.
arXiv preprint arXiv:1512.07730, 2015.
[11] S. Ling and T. Strohmer. Self-calibration and biconvex compressive sensing. Inverse Problems, 31:115002,
2015.
[12] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via
nuclear norm minimization. SIAM review, 52(3):471–501, 2010.
[13] D. Stoeger, P. Jung, and F. Krahmer. Blind deconvolution and compressed sensing. In Cosera 2016, 2016.
[14] M. Stojnic, F. Parvaresh, and B. Hassibi. On the reconstruction of block-sparse signals with an optimal
number of measurements. IEEE Trans. Signal Process., 57(8):3075–3085, 2009.
[15] J. A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comp. Math., 12(4):389–434,
2012.
[16] R. Vershinyn. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing,
Theory and Applications, chapter 5. Cambridge University Press, 2012.

17

