1

Unified Theory for Recovery of Sparse Signals
in a General Transform Domain
Kiryung Lee, Yanjun Li Student Member, IEEE, Kyong Hwan Jin,

arXiv:1612.09565v2 [cs.IT] 2 Aug 2017

and Jong Chul Ye, Senior Member, IEEE

Abstract
Compressed sensing provided a data-acquisition paradigm for sparse signals. Remarkably, it has
been shown that practical algorithms provide robust recovery from noisy linear measurements acquired
at a near optimal sampling rate. In many real-world applications, a signal of interest is typically sparse
not in the canonical basis but in a certain transform domain, such as wavelets or the finite difference.
The theory of compressed sensing was extended to the analysis sparsity model but known extensions are
limited to specific choices of sensing matrix and sparsifying transform. In this paper, we propose a unified
theory for robust recovery of sparse signals in a general transform domain by convex programming. In
particular, our results apply to general acquisition and sparsity models and show how the number of
measurements for recovery depends on properties of measurement and sparsifying transforms. Moreover,
we also provide extensions of our results to the scenarios where the atoms in the transform has varying
incoherence parameters and the unknown signal exhibits a structured sparsity pattern. In particular, for the
partial Fourier recovery of sparse signals over a circulant transform, our main results suggest a uniformly
random sampling. Numerical results demonstrate that the variable density random sampling by our main
results provides superior recovery performance over known sampling strategies.
Index Terms
Compressed sensing, analysis sparsity model, sparsifying transform, total variation, incoherence,
variable density sampling.

I. I NTRODUCTION
The theory of compressed sensing (CS) [1], [2] provided a new data-acquisition paradigm for sparse
signals. Remarkably, it has been shown that practical algorithms are guaranteed to reconstruct the unknown
This work was supported in part by the National Science Foundation under grants IIS 14-47879 and Korea Science and Engineering Foundation under grants NRF-2013M3A9B2076548 and NRF-2016R1A2B3008104. K. Lee is with the School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332 USA (e-mail: kiryung@ece.gatech.edu).
Y. Li is with the Coordinated Science Laboratory and the Department of Electrical and Computer Engineering, University of
Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: yli145@illinois.edu). K.H. Jin is with the Biomedical Imaging
Group, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland (e-mail: kyong.jin@epfl.ch). J.C. Ye is with
the Department of Bio and Brain Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejon 305-701,
Korea (e-mail: jong.ye@kaist.ac.kr).

2

sparse signal from the linear measurements taken at a provably near optimal rate. Reconstruction algorithms with performance guarantees include modern optimization algorithms for `1 -norm-based convex
optimization formulations (e.g., [3], [4]) and iterative greedy algorithms (e.g., [5], [6], [7], [8]).
The canonical sparsity model in CS assumes that the unknown signal f P Cd is s-sparse in the standard
coordinate basis. In other words, }f }0 ď s, where } ¨ }0 counts the number of nonzero elements. The
acquisition process in CS is linear and represented by a sensing matrix A P Cmˆd so that the m linear
measurements in b P Cm is given by
b “ Af ` w,

where w P Cm denotes additive noise to the measurements and satisfies }w}2 ď . For certain random
sensing matrices, it was shown that an estimate fˆ given by
fˆ “ argmin }f˜}1

subject to

}b ´ Af˜}2 ď 

(1)

f˜PCd

satisfies }fˆ´f }2 ď c1  with high probability, provided that m ě Cs logα d for some α P N and numerical
constants C and c1 . In particular, in the noiseless case ( “ 0), the estimate fˆ coincides with the ground
truth signal f . For example, Candes and Tao [9] showed that the above guarantees hold for a Gaussian
sensing matrix A whose entries are i.i.d. following N p0, 1{mq via the restricted isometry property (RIP).
Recent results with a sharper sample complexity of m ě 2s logpd{sq were derived using the Gaussian
width of a tangent cone [10], [11].
In fact, the original idea of compressed sensing [12] was motivated by a need to accelerate various
imaging modalities. The sensing matrix A in these applications takes observations in a measurement
transform domain, i.e.

c
A“

n
SΩ Ψ,
m

(2)

where Ψ P Cnˆd is the matrix representation of the measurement transform and the sampling operator
SΩ : Cn Ñ Cm takes the m elements indexed by Ω “ tω1 , ω2 , . . . , ωm u. For example, when Ψ is a

discrete Fourier transform (DFT) matrix, A is a partial Fourier matrix. The aforementioned near optimal
performance guarantees were shown for a partial Fourier sensing matrix A obtained using a random
set Ω [2], [13], [14], [15] and generalized for the case where the rows of Ψ P Cnˆd correspond to an
incoherent tight frame for Cd [16].
However, in numerous imaging applications, a signal of interest is not sparse in the standard coordinate
basis. The theory of compressed sensing was accordingly extended to the so-called synthesis and analysis
sparsity models [17], [18], [19]. The synthesis sparsity model assumes that f P Cd is represented as a
linear combination of few atoms in a dictionary D P CdˆN . Equivalently, f is represented as f “ Du
with an s-sparse coefficient vector u P CN . Compressed sensing with the synthesis sparsity model can be
interpreted as conventional compressed sensing of u using a sensing matrix AD where u is s-sparse in the
standard basis. In particular when A is a Gaussian matrix and D is an orthogonal matrix, conventional

3

performance guarantees carry over to the synthesis sparsity model. On the other hand, the analysis
sparsity model, which is motivated from sparse representation in harmonic analysis [20], assumes that
the transform Φf P CN of f via Φ P CN ˆd is s-sparse. In fact, a signal of interest in practical applications
often follows the analysis sparsity model via various transforms including finite difference and wavelet
[20], contourlet [21], curvelet [22], and Gabor transforms. Thus, the analysis sparsity model has been
used as an effective regularizer for classical inverse problems in signal processing (e.g., denoising and
deconvolution) and compressed sensing imaging (e.g., [23]).
Unlike the previous results with the canonical sparsity model, the theory of compressed sensing with
the analysis model has been relatively less explored and known results are limited to specific cases.
Candes et al. [17] considered the recovery of f P Cd such that Φf is s-sparse for a transform Φ P CN ˆd
satisfying Φ˚ Φ “ Id , i.e. the columns of Φ˚ correspond to a tight frame for Cd . They showed that
fˆ “ argmin }Φf˜}1

subject to

}Af˜ ´ b}2 ď 

(3)

f˜PCd

has the error bound given by }fˆ ´ f }2 ď c1 , provided that the sensing matrix AΦ˚ satisfies the RIP.
In particular for a Gaussian sensing matrix A, their performance guarantee holds with high probability
for m “ Ops logpd{sqq for any Φ satisfying Φ˚ Φ “ Id . Indeed the performance guarantee by Candes
et al. [17] applies beyond the case of a Gaussian sensing matrix A. Krahmer and Ward [24] showed
that if A P Cmˆd and D P CdˆN satisfy the RIP and ε P Rd is a Rademacher sequence with random
˘1 entries, then AdiagpεqD satisfies the RIP, where diagpεq P Cdˆd denotes the diagonal matrix whose

diagonal entries are ε. However, applying a random sign before the acquisition might not be feasible in
certain applications. In another line of research, it was shown [18], [19] that greedy algorithms for the
analysis sparsity model provide performance guarantees if the sensing matrix A is a near isometry when
acting on all transform-sparse f such that Φf is sparse. Again for Φ satisfying Φ˚ Φ “ Id , this condition
on A is less demanding than the RIP of AΦ˚ since the latter implies the former. However, it has not
been studied how such a relaxation translates into less-demanding sample complexity.
A special analysis sparsity model associated with the finite difference transform Φ has been of particular
interest in signal processing and imaging applications. The corresponding convex surrogate }Φf }1 , known
as the total variation (TV), has been popularly used as an effective regularizer for solving inverse problems.
Needell and Ward [25] provided performance guarantees for TV minimization with a partial Fourier
sensing matrix A in terms of the RIP of AD with a Haar wavelet dictionary D. Their result was further
refined by Krahmer and Ward [26] with a clever idea of variable density sampling adopting the local
incoherence parameters. Remarkably, Krahmer and Ward [26] provided performance guarantees at the
sample complexity of m “ Ops log3 s log2 dq. However, these results on TV minimization rely on a
special embedding theorem that relates the Haar transform to the finite difference transform, which holds
only for signals of dimension two or higher. Therefore, the results by Needell and Ward [25] and by
Krahmer and Ward [26] do not apply to the 1D case and more importantly do not generalize to other
sparsifying transforms.

4

Recently, inspired by analogous results for the canonical sparsity model [10], [11], Kabanava et al.
[27] derived a performance guarantee of TV minimization with a Gaussian sensing matrix A at the
sample complexity of m ą d r1 ´ t1 ´ ps ` 1q{du2 {πs. Cai and Xu [28] showed a similar result with
?
m ě C sd log d. Compared to the previous result by Krahmer and Ward [26], the above results [27],
[28] apply to the 1D case but at a significantly suboptimal sample complexity. More importantly, the use
of a Gaussian sensing matrix might not be relevant to practical applications. Along a similar analysis
strategy, Kabanava and Rauhut [29] showed performance guarantees for (3) with a Gaussian sensing
matrix A P Rmˆd and a frame analysis operator Φ P RN ˆd roughly at the sample complexity of
m ě 2κs logp2N {sq, where κ denotes the ratio of upper and lower frame bounds, i.e. κ is the condition

number of the frame operator Φ˚ Φ. The sample complexity of this result for a tight frame is near optimal.
However, their analysis is restricted to a Gaussian sensing matrix A and does not generalize to other
sensing matrices.
A. Contributions
Our main contribution is to derive performance guarantees for compressed sensing of analysis-sparse
vectors by (3) for general classes of sensing matrix A given in the form of (2) with measurement transform
Ψ and (redundant) analysis transform Φ. Unlike the previous works, performance guarantees in this paper

apply without being restricted to a particular choice of Φ and Ψ1 . The number of measurements implying
these guarantees depends on certain properties of pΦ, Ψq and this result identifies a class of measurement
and sparsity models allowing recovery at a near optimal sampling rate. Moreover, when Ψ and Φ have a
few strongly correlated atoms, adopting the idea by Krahmer and Ward [26], we propose to acquire linear
measurements using random sampling with respect to a variable density designed with the correlations
between Ψ and Φ. This modified acquisition enables recovery at a lower sampling rate. We also extend
the results to group sparsity models. This extension applies to various popular regularized recovery
methods including the isotropic-total-variation minimization. In special cases where Ψ is Fourier and Φ
is a circulant matrix, our theory suggests a uniformly random sampling or its variation. For example, for
the total variation minimization, unlike the common belief in practice, a sampling strategy that combines
the acquisition of the lowest frequency and uniformly random sampling on the other frequencies provides
better reconstruction than known variable density random sampling strategies.
Our main idea is inspired by a previous work on structured matrix completion by Chen and Chi [30].
They showed that a structured low-rank matrix (e.g., a low-rank Hankel matrix) is successfully recovered
from partially observed entries by minimizing the nuclear norm. Indeed, their structured low-rank matrix
completion can be interpreted as follows. The unknown structured matrix M is given as the image T x of
the generator x via a linear map T . Then the completion of the structured matrix M with the low-rankness
prior is equivalent to the completion of the generator x with low-rankness in the transform domain via T .
Similarly, compressed sensing with the analysis sparsity model is equivalent to the recovery of x P Cn
1

A Gaussian sensing matrix is also obtained in the form of (2) by choosing Ψ as a Gaussian matrix.

5

with the prior that T x P CN is s-sparse where the transform T is given as T “ ΦΨ: . Therefore the
two problems are analogous to each other in the sense that their priors correspond to atomic sparsity
[10] in their respective transform domains. Moreover, in both the structured low-rank matrix model and
the transform-domain sparsity model, T is not necessarily surjective, which implies that T T ˚ may be
rank-deficient. This violates an important technical condition known as the isotropy property and many
crucial steps in the proofs of existing performance guarantees for CS break down. To overcome this
difficulty, we adopt the clever idea by Chen and Chi [30] through the aforementioned analogy and derive
near optimal performance guarantees for the recovery of sparse signals in a transform domain without
resorting to the isotropy property. However, besides this similarity, our results are significantly different
from the analogous results [30] in the following sense. Chen and Chi [30] assumed that T is restricted to
a set of special linear operators that generate structured matrices and their analysis indeed relies critically
on strong properties satisfied by such linear operators (e.g., T needs to satisfy T ˚ T “ In ). Contrarily,
we only assume a mild condition that T is injective and the resulting performance guarantees apply to
more general cases. For example, in compressed sensing with the analysis sparsity model, T “ ΦΨ: is
non-unitary if the measurement transform Ψ is non-unitary (e.g., the Radon transform) or the sparsifying
transform Φ is non-unitary (e.g., biorthogonal wavelet and data-adaptive transforms).
We illustrate our theory through extensive Monte Carlo simulations. The variable density sampling in
this paper provides an improved recovery performance over the previously suggested sampling strategies.
For example, when Φ and Ψ have atoms showing high correlation (e.g. Fourier and wavelet), our theory
suggests to sample more densely in the lower frequencies, which enables successful recovery from fewer
observations. Rather surprisingly, when Φ and Ψ respectively correspond to the finite difference and the
Fourier transforms, our theory suggests a special sampling density that always takes the lowest frequency
and chooses the other frequency components randomly using the uniform density. This is contrary to the
common belief in compressed sensing but the proposed sampling strategy turns out be more successful
than previous works not only in theory but also empirically. These numerical results strongly support out
new theory.
B. Organization
The rest of this paper is organized as follows. The main results are presented in Sections II and III,
where the proofs are deferred to Sections VI and VII. We extend the theory to the group sparsity models
in Section IV and study a special case of circulant transforms in Section V. After demonstrating empirical
observations in Section VIII, which supports our main results, we conclude the paper with some final
remarks in Section IX.
C. Notations
For a positive integer N , we will use a shorthand notation rN s for the set t1, . . . , N u. For a vector
z P CN , let zrks denote the k th element of z for k P rN s, i.e. z “ rzr1s, zr2s, . . . , zrN ssJ . The Hadamard

6

product of two vectors x, y P Cn is denoted by x d y . The circular convolution of two vectors x, y P Cn
is denoted by x f y . The Kronecker product of two matrices A and B is denoted by A b B . The operator
norm from `np to `N
q will be denoted by } ¨ }pÑq . For brevity, the spectral norm } ¨ }2Ñ2 will be written
without subscript as } ¨ }. For a matrix A, its Hermitian transpose and its Moore-Penrose pseudo inverse
are respectively written as A˚ and A: .
For J Ă rN s, the coordinate projection with respect to J , denoted by ΠJ , is defined as
$
&zrks k P J,
pΠJ zqrks :“
%0
otherwise.
The complex signum function, denoted by sgnp¨q : CN Ñ CN , is defined as
$
’
& zrks zrks ‰ 0,
psgnpzqqrks :“ |zrks|
’
%0
otherwise.

(4)

Let e1 , . . . , en denote the standard basis vectors for Cn . In other words, ek is the k th column of the
n-by-n identity matrix.

II. R ECOVERY OF S PARSE S IGNALS IN A G ENERAL T RANSFORM D OMAIN
Let T : Cn Ñ CN be a linear map that we call a “transform” in this paper. Let Ω “ tω1 , ω2 , . . . , ωm u
denote the multi-set of m sampling indices out of rns :“ t1, . . . , nu with possible repetition of elements.
Given Ω, the sampling operator SΩ : Cn Ñ Cm is defined so that the j th element of SΩ x P Cm is the
ωj th element of x P Cn for j “ 1, . . . , m. We are interested in recovering an unknown signal x P Cn from

its partial entries at Ω when the transform T x is known s-sparse a priori, i.e. }T x}0 ď s. Compressed
sensing with the analysis sparsity model is an instance of this problem formulation as shown in the
following. Recall that Ψ is of full column rank. Let T : Cn Ñ CN be defined by T “ ΦΨ: where
Ψ: denotes the Moore-Penrose pseudo inverse of Ψ. Let x P Cn denote the vector containing fully

sampled measurements, i.e. x “ Ψf . Since f “ Ψ: x, we have Φf “ ΦΨ: x “ T x. Thus the recovery
a
of f from b “ n{mSΩ Ψf with the prior that Φf is s-sparse is equivalent to the recovery of x from
a
b “ n{mSΩ x with the prior that T x is s-sparse.
In the noise-free scenario where partial entries of x are observed exactly, we propose to estimate x as
the minimizer to the following optimization problem:
minimize
}T g}1
n
gPC

subject to

SΩ g “ SΩ x.

(5)

We provide a sufficient condition for recovering x exactly by (5) in the following theorem.
Theorem II.1. Suppose T : Cn Ñ CN is injective. Let γ be defined by
γ :“ argmin }γ̃T ˚ T ´ In },
γ̃ą0

(6)

7

where Tr “ pT : q˚ . Let µ be given by
!
)
1{2
2
´1{2 r
2
µ “ max max n}γ T ek }8 , n}γ
T ek }8 .
kPrns

(7)

Let Ω “ tω1 , . . . , ωm u be a multi-set of random indices where ωk s are i.i.d. following the uniform
distribution on rns. Suppose T x is s-sparse. Then with probability 1´e´β ´3{n, x is the unique minimizer
to (5) provided
mě

`
˘‰
Cp1 ` βqµs “
log N ` log }T }1Ñ2 }T : }2Ñ8 .
˚
1 ´ }γT T ´ In }

Proof of Theorem II.1. See Section VI.
Remark II.2. All the results in this section including Theorem II.1 as well as other similar results [15],
[31], [30], all derived using the golfing scheme, provide an instance recovery guarantee that applies to a
single arbitrary instance of x, which is a weaker result than the uniform recovery guarantee that applies
to the set of all transform-sparse signals. In compressed sensing with the canonical sparsity model, an
instance guarantee is given from a fewer measurements than the uniform guarantee [15] by a poly-log
factor. For matrix completion problems, the RIP do not hold and known results [31], [30] only provide
an instance guarantee. We suspect that this is the case with the recovery problem in this paper.
Note that }T }1Ñ2 denotes the largest `2 -norm among all columns of T . Similarly, }T : }2Ñ8 “ }Tr}1Ñ2
denotes the largest `2 -norm among all columns of Tr. In a special case when T ˚ T “ In , we have T : “ T ˚ .
Thus }T }1Ñ2 “ }T : }2Ñ8 “ 1. In general, if }T }1Ñ2 }T : }2Ñ8 “ OpN α1 q for some α1 P N and
1
1 ´ }γT ˚ T ´ In }

“ Oplogα2 N q

for some α2 P N, then we get a performance guarantee at a near optimal scaling of sample complexity
of m “ Opµs logα N q, where α “ α1 ` α2 . These are mild conditions and easily satisfied by transforms
that arise in practical applications.
In the noisy scenario where partial entries of x are observed with additive noise, we propose to estimate
x by solving the following optimization problem:
minimize
}T g}1
n
gPC

subject to

}SΩ1 g ´ SΩ1 x7 }2 ď ,

(8)

˚ is the
where x7 denotes a noisy version of x, Ω1 denotes the set of all unique elements in Ω, and SΩ
1

adjoint of the sampling operator SΩ1 that fills missing entries at outside Ω1 with 0.
Theorem II.3. Suppose the hypotheses of Theorem II.1 hold. Let x̂ be the minimizer to (8) with x7
satisfying
}SΩ1 px ´ x7 q}2 ď .

Then
}x̂ ´ x}2 ď

? `
˘)
σmax pT q !
¨ 2 ` 28 N 3n}T }1Ñ2 }T : }2Ñ8 ` 1 ,
σmin pT q

(9)

8

Proof of Theorem II.3. See Section VII-A.
We can tighten the upper bound on the estimation error in Theorem II.3 when T ˚ T is well conditioned.
To this end, we will use the following theorem, which is obtained by modifying [32, Theorem 3.1].
Theorem II.4 (A modification of [32, Theorem 3.1]). Suppose T : Cn Ñ CN and Tr “ pT : q˚ satisfy (7)
with parameters µ and γ . Let Ω “ tω1 , . . . , ωm u be a multi-set of random indices where ωk s are i.i.d.
following the uniform distribution on rns. Then with probability 1 ´ ξ , we have
› ´n
¯ ›
›
›
˚
T SΩ
SΩ T : ´ T T : ΠJr› ď δ,
max ›ΠJr
m
r
|J|ďs

(10)

provided
C1 δ ´2 µs log2 s log N log m
,
1 ´ }γT ˚ T ´ In }

mě

(11)

and
m ě C2 δ ´2 µs logpξ ´1 q.

(12)

Proof of Theorem II.4. See Appendix F.
Using Theorem II.4, we provide another sufficient condition for stable recovery of sparse signals in a
transform domain, which has a smaller noise amplification factor.
Theorem II.5. Suppose T : Cn Ñ CN is injective. Suppose T and Tr “ pT : q˚ satisfy (7) with parameters
µ and γ . Let Ω “ tω1 , . . . , ωm u be a multi-set of random indices where ωk s are i.i.d. following the uniform

distribution on rns. Let x̂ be the minimizer to (8) with x7 satisfying (9). Then there exist numerical
constants C, c ą 0 for which the following holds. With probability 1 ´ N ´4 , we have
(ı
σmax pT q ” ?
n
}x̂ ´ x}2 ď
}T }1Ñ2 }T : }2Ñ8 p|Ω| ´ |Ω1 |q ` 1 ,
¨ 14 N `
σmin pT q
m
provided
mě

Cµs log4 N
.
1 ´ }γT ˚ T ´ In }

(13)

Furthermore, if T ˚ T “ In , then with probability 1 ´ N ´4 ,
σmax pT q ´ ?
n ¯
}x̂ ´ x}2 ď
¨ 14 N ` R ,
σmin pT q
m
where R is the count of the most repeated elements in Ω.
Proof of Theorem II.5. See Section VII-B.
Remark II.6. By the definition of Ω1 , we have |Ω|´|Ω1 | ď m´1. Suppose that }T }1Ñ2 }T : }2Ñ8 “ Op1q.
?
The resulting noise amplification factor by Theorem II.5 is Op N ` nq, which is already smaller than

9

?
Op N nq by Theorem II.3. In fact, the distribution of |Ω1 | is explicitly given by
(
m
` 1
˘
` n!
P |Ω | “ ` “ m
,
n pn ´ `q!
(
where m` denotes the Stirling number of the second kind defined by
" *
ˆ ˙
`
m
1 ÿ
`´j `
:“
p´1q
jm.
`! j“0
`
j

It would be possible to compute a more tight probabilistic upper bound on |Ω| ´ |Ω1 | with its distribution.
?
However, because of the other factor N , regardless of |Ω| ´ |Ω1 |, the noise amplification factor by
Theorem II.5 cannot be improved to Op1q as shown for compressed sensing with the canonical sparsity
model [15] or with a special analysis model [26]. We admit that this suboptimality in noise amplification
is a limitation of our analysis. It will be interesting to see whether one can obtain near optimal noise
amplification for a general transform T .
III. I NCOHERENCE -D EPENDENT VARIABLE D ENSITY S AMPLING
In the results of the previous section, the number of measurements is proportional to the incoherence
parameter µ in (7), which is the worst case `8 -norm among tT ek un and tTrek un . In certain scenarios,
k“1

k“1

these `8 -norms are unevenly distributed. For example, in compressed sensing with the analysis sparsity
model, T is given by T “ ΦΨ: with the sensing transform Ψ P Cnˆd and the sparsifying transform
Φ P CN ˆd . If Ψ and Φ correspond to the DFT and DWT (discrete wavelet transform), respectively, low-

frequency atoms have larger correlations. Thus there are a few T ek s that dominate the others with large
`8 -norms. Krahmer and Ward [26] proposed a clever idea of sampling measurements with respect to a
variable density adapted to the local incoherence parameters, which are t}T ek }8 un and t}Trek }8 un .2
k“1

k“1

Then the sample complexity depends on not the worst case incoherence parameter but the average of the
local incoherence parameters. In this section, adopting the idea by Krahmer and Ward [26], we extend
the results in Section II to the case where the local incoherence parameters are unevenly distributed. The
following theorem is analogous to Theorem II.1 and provides a sufficient condition for recovery of sparse
signals in a transform domain when measurements are sampled according to a variable density.
Theorem III.1. Suppose T : Cn Ñ CN is injective. Let µk and µ̃k be defined by
µk “ n}γ 1{2 T ek }28

and

µ̃k “ n}γ ´1{2 Trek }28

(14)

for all k P rns, where γ is defined in (6) from T and Tr “ pT : q˚ . Let Ω “ tω1 , . . . , ωm u be a multi-set of
random indices where ωk s are independent copies of a random variable ω with the following distribution:
?
µk µ̃k
Ppω “ kq “ řn a
,
µj µ̃j
j“1
2

@k P rns.

(15)

Krahmer and Ward [26] considered orthonormal Φ and Ψ respectively corresponding to the DFT and the Haar DWT. In this
case, T : “ T ˚ . Thus, Tr “ T .

10

Suppose T x is s-sparse. Then with probability 1 ´ e´β ´ 3{n, x is the unique minimizer to (5) provided
mě

`
˘‰
Cp1 ` βqµ̄s “
log N ` log }T }1Ñ2 }T : }2Ñ8 ,
˚
1 ´ }γT T ´ In }

where µ̄ is defined as

n
1 ÿa
µk µ̃k
µ̄ :“
n k“1

(16)

Compared to Theorem II.1, Theorem III.1 provides a performance guarantee at a smaller sample
complexity, where the worst-case incoherence parameter is replaced by the average incoherence parameter
µ̄. Note that µ̄ is always no greater than the worst-case incoherence parameter pmaxk µk q1{2 pmaxk µ̃k q1{2 .

In particular when there exist dominant µk s or µ̃k s compared to other incoherence parameters, the sample
complexity of Theorem III.1 is much smaller than that of Theorem II.1.
Proof of Theorem III.1. Define
?
?
ν :“ r µ1 , . . . , µn sJ

a
a
ν̃ :“ r µ̃1 , . . . , µ̃n sJ .

and

(17)

Without loss of generality, we may assume that µk s and µ̃k s are strictly positive. Then all entries of ν
and ν̃ are nonzero.
Ă as
Using ν and ν̃ , we construct a pair of weighted transforms W and W
W “

?

µ̄T rdiagpνqs´1

Ă “ ?µ̄Trrdiagpν̃qs´1 .
W

and

(18)

Ă satisfy
Then, W and W
c
max }γ
kPrns

1{2

W ek }8 ď

µ̄
n

c
and

max }γ

´1{2 Ă

kPrns

W ek }8 ď

µ̄
.
n

Furthermore, we have
¸
¸
˜
˜
m
m
ÿ
n
n ÿ
˚
Ă˚
Ă˚ “ E
E
W SΩ
SΩ W
W eωj e˚ωj W
m j“1
m j“1
˜
¸
m
n ÿ
´1
˚
´1 r ˚
“E
µ̄T rdiagpνqs eωj eωj rdiagpν̃qs pT q
m j“1
˜
¸
m
n ÿ
µ̄
a
“E
T eωj e˚ωj T :
m j“1 µωj µ̃ωj
“

(19)

(20)

m
1 ÿ r:
T T “ T T :.
m j“1

Since diagpν̃q is an invertible matrix, T and W span the same subspace and T T : is an orthogonal
projection onto the span of W . Furthermore,
Ă ek y “ 0,
xW ek1 , W

@k ‰ k 1 .

11

Let g “

?
µ̄rdiagpνqs´1 g 1 . Then T g “ W g 1 . Thus (5) is equivalent to
minimize
}W g 1 }1
1
n
g PC

subject to

SΩ g 1 “ µ̄´1{2 SΩ rdiagpνqsx.

(21)

Applying Theorem II.1 to (21) with incoherence parameter µ̄ completes the proof.
In the case when we are given sampled measurements corrupted with additive noise, Theorems II.3
and II.5 are modified according to the change of the distribution for choosing random sample indices.
Theorem III.2. Suppose the hypotheses of Theorem III.1 hold. Let x7 be a noisy version of x that satisfies
(9). Let x̂ be the minimizer to
minimize
}T g}1
n
gPC

subject to

}SΩ1 rρ d pg ´ x7 qs}2 ď ,

(22)

?
?
where ρ :“ µ̄´1{2 r µ1 , . . . , µn sJ . Then
„
ˆ
˙
?
maxkPrns µk
σmax pT q
µ̄
:
}x̂ ´ x}2 ď
¨ 2 ` 28 N
¨ 3n}T }1Ñ2 }T }2Ñ8 ` 1 .
¨
σmin pT q minkPrns µ̃k
minkPrns µ̃k

Like Theorem III.1, Theorem III.2 provides a performance guarantee at a lower sample complexity (in
order) when compared to Theorem II.3. On the other hand, the noise amplification factor of Theorem III.2
is larger than that of Theorem II.3 by a factor that depends on the distribution of the local incoherence
parameters tpµk , µ̃k qunk“1 .
Ă be defined in (18). Let ν and ν̃ be defined in (17). Define
Proof of Theorem III.2. Let W and W
Λ :“

?
µ̄rdiagpνqs´1

and

r “ ?µ̄rdiagpν̃qs´1 .
Λ

(23)

Then W “ T Λ and (8) is equivalent to
minimize
}W g 1 }1
1
n
g PC

subject to

}SΩ1 g 1 ´ SΩ1 Λ´1 x7 }2 ď .

(24)

Let x̆ denote the minimizer to (24). Then, the minimizer x̂ to (8) is represented as x̂ “ Λx̆, i.e.
x̆ “ Λ´1 x̂. By applying Theorem II.3 to (24), we obtain
}T x̂ ´ T x}2 “ }W x̆ ´ W Λ´1 x}2
¯)
!
? ´
r ´1 T : }2Ñ8 ` 1 }W }.
ď 2 ` 28 N 3n}T Λ}1Ñ2 }Λ

The proof completes by applying the following inequalities to (25):
:
r ´1 T : }2Ñ8 ď }Λ
r ´1 }}T : }2Ñ8 “ µ̄}T }2Ñ8
}Λ
minkPrns µ̃k

and
}T Λ}1Ñ2 ď }T }1Ñ2 }Λ} “

maxkPrns µk }T : }2Ñ8
.
µ̄

(25)

12

Theorem III.3. Suppose T : Cn Ñ CN is injective. Suppose that T and Tr “ pT : q˚ satisfy (14) with
parameters tµk unk“1 , tµ̃k unk“1 , and γ . Let µ̄ be defined in (16). Let Ω “ tω1 , . . . , ωm u be a multi-set of
random indices where ωk s are i.i.d. copies of a random variable ω with the distribution in (15). Let x̂
be the minimizer to (22) with x7 satisfying (9). Then there exist numerical constants C, c ą 0 for which
the following holds. With probability 1 ´ N ´4 , we have
"
„
*
?
n maxkPrns µk
µ̄
σmax pT q
:
1
¨
¨ 14 N `
¨ }T }1Ñ2 }T }2Ñ8 p|Ω| ´ |Ω |q ` 1 ,
}x̂ ´ x}2 ď
σmin pT q minkPrns µ̃k
m minkPrns µ̃k
provided
mě

C µ̄s log4 N
.
1 ´ }γT ˚ T ´ In }

Furthermore, if T ˚ T “ In , then with probability 1 ´ N ´4 ,
ˆ
˙
?
n maxkPrns µk
σmax pT q
µ̄
}x̂ ´ x}2 ď
¨
¨ 14 N `
¨
¨ R ,
σmin pT q minkPrns µ̃k
m minkPrns µ̃k
where R is the count of the most repeated elements in Ω.
Ă be defined in (18). Let ν and ν̃ be defined in (17). Let Λ and
Proof of Theorem III.2. Let W and W
r be defined in (23). In the proof of Theorem III.2, we have shown that (22) is equivalent to (24). In
Λ
Ă satisfy (19) and (20). Therefore, applying
the proof of Theorem III.1, we have shown that W and W

Theorem II.5 to (21) with incoherence parameter µ̄ completes the proof.
IV. E XTENSION TO G ROUP S PARSITY M ODELS
In Sections II and III, we considered the sparsity model in a transform domain. In applications, the
transform T x exhibits additional structures – group sparsity. For example, in compressed sensing of 2D
J J
signals, the sparsifying transform Φ “ rΦJ
1 , Φ2 s can be the concatenation of the horizontal and vertical

finite difference operators Φ1 and Φ2 . Anisotropic total variation encourages the sparsity of Φf [26]. On
the other hand, one can choose isotropic total variation, assuming that Φ1 f and Φ2 f are jointly sparse (see
the experiments section). For another example, in compressed sensing of color images or hyperspectral
images, the sparse codes acquired from applying the analysis operator to different channels are usually
assumed to be jointly sparse. To exploit such structures, we extend the results in the previous sections
to group sparsity models in a transform domain. More specifically, we assume that the transform T x of
unknown signal x via T : Cn Ñ CL is ps, tq strongly group sparse in the following sense.
Ť
Ş
Definition IV.1 ([33]). Let G “ tG1 , . . . , GN u be a partition of rLs, i.e. jPrN s Gj “ rLs and Gj Gj 1 “
H for j ‰ j 1 . A vector z P CL is ps, tq strongly group sparse with respect to G if there exists J Ă rN s

such that
supppzq Ă GJ ,

|GJ | ď t,

and

|J| ď s,

13

where GJ is defined by
GJ :“

ď

Gj .

jPJ

An atomic norm for this group sparsity model is given by
||| z |||G,1 :“

ÿ

}ΠGj z}2 .

jPrN s

The dual norm of ||| ¨ |||G,1 is defined by
||| z |||G,8 :“

sup

|xζ, zy|,

ζPCL :||| ζ |||G,1 ď1

which is equivalently rewritten as
||| z |||G,8 “ max }ΠGj z}2 .
jPrN s

A subgradient z̃ of ||| ¨ |||G,1 at z is given by
$
Π z
’
& Gj , ΠGj z ‰ 0,
ΠGj z̃ “ }ΠGj z}2
’
%0,
otherwise,

@j P rN s.

(26)

In a special case where Gj “ tju for all j P rN s, the strong group sparsity level reduces to the
conventional sparsity model. The analogy between the two models is summarized in Table I. All the
results in the previous section generalize to the strong group sparsity model according to this analogy. In
the below, we state the extended results as Theorems, the proofs of which are obtained in a straightforward
way by modifying the proofs of analogous theorems and lemmas for the usual sparsity model according
to Table I. Thus, we do not repeat the proofs in this section. (The only exception is Lemma VI.5 and
we provide an analogous Lemma VI.6 in Section VI-A.)
When T x is strongly group sparse, we propose to estimate T x by solving the following optimization
problem, which generalizes (5):
||| T g |||G,1
minimize
n
gPC

subject to

SΩ g “ SΩ x.

(27)

Then the following theorem, which is analogous to Theorem II.1, provides a performance guarantee for
(27).
Theorem IV.2. Let G “ tG1 , . . . , GN u be a partition of rLs. Suppose T : Cn Ñ CL is injective. Let µG
be given by
!
)
µG “ max max max n}γ 1{2 ΠGj T ek }22 , n}γ ´1{2 ΠGj Trek }22 ,
kPrns jPrN s

(28)

where γ is defined in (6) from T and Tr “ pT : q˚ . Let Ω “ tω1 , . . . , ωm u be a multi-set of random indices
where ωk s are i.i.d. following the uniform distribution on rns. Suppose T x is ps, tq strongly group sparse

14

TABLE I: Analogy between Sparsity Model and Group Sparsity Model
Sparsity Model
dimpRpT qq

N

support

supppzq “ tj : Πtju z ‰ 0u

group sparsity level
total sparsity level
atomic norm
dual norm
subgradient
of atomic norm
incoherence
parameter
local incoherence
parameters

}z}0 “ |supppzq|
}z}0 “ |supppzq|
ř
}z}1 “ N
j“1 |Πtju z|
} ¨ }8 “ maxjPrN s |Πtju z|

Group Sparsity Model
ř
L“ N
j“1 |Gj |
gsupppzq “ tj
Ť : ΠGj z ‰ 0u
supppzq “ jPgsupppzq Gj
||| z |||G,0 “ |gsupppzq|
}z}0 “ |supppzq|
ř
||| ¨ |||G,1 “ N
j“1 }ΠGj z}2
||| ¨ |||G,8 “ maxjPrN s }ΠGj z}2

(4)

(26)

µ

µG

tµk unk“1

tµG,k unk“1

with respect G . Then with probability 1 ´ e´β ´ 3{n, x is the unique minimizer to (27) provided
mě

`
˘‰
Cp1 ` βqµG s “
log N ` log }T }1Ñ2 }T : }2Ñ8 .
˚
1 ´ }γT T ´ In }

(29)

Suppose that µ and µG are the smallest constants satisfying corresponding incoherence conditions. If
t “ `s and |Gj | “ ` for all j P rN s, then
b
}ΠGj T ek }2 ď |Gj |}T ek }8 ,

@j P rN s, @k P rns.

Thus, we have µG ď `µ and a sufficient condition for (29) is given by
mě

`
˘‰
Cp1 ` βqµt “
:
log
N
`
log
}T
}
}T
}
.
1Ñ2
2Ñ8
1 ´ }γT ˚ T ´ In }

In other words, the sample complexity is proportional to the total sparsity level t and there is no gain
from the group structure. This inequality is tight if each ΠGj T ek have nonzero elements of the same
magnitude. Contrarily, if nonzero elements of each ΠGj T ek vary a lot in their magnitudes, µG is smaller
than `µ and there is gain from the group sparsity structure.
In the presence of noise to measurements, we generalize the optimization formulation for recovery in
(8) as follows:
||| T g |||G,1
minimize
n
gPC

subject to

}SΩ1 g ´ SΩ1 x7 }2 ď .

(30)

The following theorem, analogous to Theorem II.3, provides a performance guarantee for (30).
Theorem IV.3. Suppose the hypotheses of Theorem IV.2 hold. Let x̂ be the minimizer to (30) with x7
satisfying
}SΩ1 px ´ x7 q}2 ď .

15

Then
}x̂ ´ x}2 ď

? `
˘)
σmax pT q !
¨ 2 ` 28 N 3n}T }1Ñ2 }T : }2Ñ8 ` 1 .
σmin pT q

The results for recovery using a variable density sampling designed from local incoherence parameters
generalize in a similar way. We state the results in the following theorems.
Theorem IV.4. Let G “ tG1 , . . . , GN u be a partition of rLs. Suppose T : Cn Ñ CN is injective. Let µG,k
and µ̃G,k be given by
µG,k “ max n}γ 1{2 ΠGj T ek }22
jPrN s

and

µ̃G,k “ max n}γ ´1{2 ΠGj Trek }22 ,
jPrN s

(31)

where γ is defined in (6) from T and Tr “ pT : q˚ . Let Ω “ tω1 , . . . , ωm u be a multi-set of random indices
where ωk s are independent copies of a random variable ω with the following distribution:
a
µG,k µ̃G,k
Ppω “ kq “ řn a
, @k P rns.
µG,j µ̃G,j
j“1

(32)

Suppose T x is ps, tq strongly group sparse with respect G . Then with probability 1 ´ e´β ´ 3{n, x is the
unique minimizer to (5) provided
mě

`
˘‰
Cp1 ` βqµ̄G s “
log N ` log }T }1Ñ2 }T : }2Ñ8 ,
˚
1 ´ }γT T ´ In }

where µ̄ is defined as
µ̄G :“

n
1 ÿa
µG,k µ̃G,k .
n k“1

Theorem IV.5. Suppose the hypotheses of Theorem IV.4 hold. Let x̂ be the minimizer to (30) with x7
satisfying
}SΩ1 x ´ SΩ1 x7 }2 ď .

(33)

Then
„
ˆ
˙
?
maxkPrns µG,k
σmax pT q
µ̄G
:
}x̂ ´ x}2 ď
¨
¨ 2 ` 28 N
¨ 3n}T }1Ñ2 }T }2Ñ8 ` 1 .
σmin pT q minkPrns µ̃G,k
minkPrns µ̃G,k

V. C IRCULANT T RANSFORMS
Many sparsifying transforms fall into the category of circulant transforms, including the identity
transform. A block transform (e.g., block DCT), when applied to all overlapping patches of a signal
(sliding window with stride 1, including the wrap-around patches at the edges), is a union of circulant
transforms applied to the signal [34]. In this section, we consider only the case when the measurement
matrix Ψ P Cnˆn is the DFT matrix, and compute the variable density sampling distribution (15) for
sparsity with respect to a circulant transform, and distribution (32) for joint sparsity with respect to a
union of circulant transforms. We show that, if the circulant transforms are injective, the distributions
(15) and (32) correspond to the uniform distribution on rns. On the other hand, some circulant transforms

16

are not injective (e.g., the finite difference operator for 1D total variation or 2D isotropic total variation).
Even in this case, we show that the “variable” density sampling distributions are a variation of the uniform
distribution.
A. Injective Circulant Transforms
We say Φ P Cnˆn is a circulant transform (circulant matrix), if Φf “ φ f f is the circular convolution
of f with some vector φ P Cn , i.e. the matrix representation of
»
φr1s
φrns
φrn ´ 1s
—
— φr2s
φr1s
φrns
—
— φr3s
φr2s
φr1s
Φ“—
— .
.
..
— .
..
.
– .
φrns φrn ´ 1s φrn ´ 2s

Φ is given by
fi
¨ ¨ ¨ φr2s
ffi
¨ ¨ ¨ φr3sffi
ffi
¨ ¨ ¨ φr4sffi
ffi
.. ffi
..
ffi
.
. fl
¨ ¨ ¨ φr1s

(34)

The identity transform is a circulant transform with φ “ e1 .
By linearity and shift invariance of circular convolution, a circulant transform Φ can always be
diagonalized by the DFT matrix Ψ:
Φ “ Ψ˚ diagpλqΨ.

where λ “

(35)

?
nΨφ is the (unnormalized) DFT of φ. The same argument also applies to a 2D circulant

transform (circulant block circulant matrix) and the 2D DFT matrix. To avoid verbosity, we use circulant
transform Φ and DFT matrix Ψ to denote both 1D and 2D transforms.
Theorem V.1. For the DFT matrix Ψ P Cnˆn and an invertible circulant transform Φ P Cnˆn , the
sampling density distribution (15) is the uniform distribution on rns.
Proof of Theorem V.1. By the diagonalization in (35), we have
T “ ΦΨ: “ Ψ˚ diagpλq,
Tr “ pT : q˚ “ Ψ˚ diagpλ̃q,

where λ̃ is the complex conjugate of the element-wise inverse of λ, i.e. λ̃rks “ pλrks˚ q´1 . Then, the
following choice of parameters µk and µ̃k satisfy (14):
µk “ nγ}T ek }28 “ nγ|λrks|2 }Ψ˚ ek }28 “ γ|λrks|2 ,
µ̃k “ nγ ´1 }Trek }28 “ nγ ´1 |λ̃rks|2 }Ψ˚ ek }28 “ γ ´1 |λrks|´2 ,
?
where Ψ˚ ek is the k th column of the discrete Fourier basis and has infinity norm 1{ n. Therefore,
µk µ̃k “ 1 for all k P rns, and the distribution in (15) is Ppω “ kq “ 1{n, i.e. the uniform distribution

on rns.

17

Applying a sparsifying circulant transform to a signal is equivalent to passing the signal through a
sparsifying filter. One may also pass the signal through a bank of sparsifying filters. The filter bank is
equivalent to a union of circulant transforms, concatenated as
J
J J
Lˆn
Φ “ rΦJ
,
1 , Φ2 , . . . , Φ` s P C

(36)

where L “ `n. For example, the patch transform sparsity model [34] corresponds to this case. The 2D
isotropic total variation model (see Section V-B), as another example, has an additional joint sparsity
structure. For the latter example, let us consider a particular partition G “ tG1 , . . . , Gn u given by
Gk “ tpj ´ 1qn ` ku`j“1 ,

(37)

@k P rns.

For group sparsity on this union of circulant transforms, we have a result similar to Theorem V.1.
Theorem V.2. For the DFT matrix Ψ P Cnˆn , an injective transform Φ P CLˆn defined in (36), and the
partition defined in (37), the sampling density distribution (32) is the uniform distribution on rns.
Proof of Theorem V.2. Similar to (35), we have the following factorization for the concatenated transform:
Φ “ pI` b Ψ˚ qrdiagpλ1 q, diagpλ2 q, . . . , diagpλ` qsJ Ψ,

(38)

where λj is the (unnormalized) DFT of φj , the convolution kernel of the j th cirulant transform Φj . Hence
T and Tr are
T “ ΦΨ: “ pI` b Ψ˚ qrdiagpλ1 q, diagpλ2 q, . . . , diagpλ` qsJ ,
Tr “ pT : q˚ “ T pT ˚ T q´1 “ pI` b Ψ˚ qrdiagpλ̃1 q, diagpλ̃2 q, . . . , diagpλ̃` qsJ ,
˘
`ř
where λ̃j rks “ λj rks{ `j 1 “1 |λj 1 rks|2 . Then, µG,k and µ̃G,k in (31) are given respectively by
µG,k “ nγ max }ΠGk1 T ek }22
k1 Prns

“ nγ max }ΠGk1
k1 Prns

“ nγ max

k1 Prns

“

‰J
(
λ1 rks, λ2 rks, . . . , λ` rks b pΨ˚ ek q }22
“

˚
|eJ
k1 Ψ ek |}

`
‰J 2
`ÿ
˘
λ1 rks, λ2 rks, . . . , λ` rks }2 “ γ
|λj rks|2
j“1

and
µ̃G,k “ nγ ´1 max }ΠGk1 Trek }22
k1 Prns

“
‰J
(
λ̃1 rks, λ̃2 rks, . . . , λ̃` rks b pΨ˚ ek q }22

“ nγ ´1 max }ΠGk1
1

k Prns

“γ

´1

`
`ÿ
j“1

2

|λ̃j rks|

˘

“γ

´1

`
`ÿ
j“1

|λj rks|2

˘´1

.

18

Therefore, µG,k µ̃G,k “ 1 for all k P rns, and the distribution in (32) is Ppω “ kq “ 1{n, i.e. the uniform
distribution on rns.
B. Non-injective Circulant Transforms
In this section, we consider non-injective circulant transforms, such as the finite difference operator
for 1D total variation, or the union of vertical and horizontal finite difference operators for 2D isotropic
total variation. Since the spectral responses of these transforms are zero at certain frequencies, they
are invariant to changes in the corresponding frequency components. Therefore, unless these frequency
components are sampled in the measurement, they cannot be recovered from `1 -norm minimization (5)
or mixed norm minimization (27). Assuming without loss of generality that the null frequencies are the
first n0 columns in Ψ˚ (n0 ă mintn, mu), we adopt the following two-step sampling scheme:
1) Always sample indices ωk “ k for k P rn0 s.
2) Generate a multi-set of m ´ n0 indices tωn0 `1 , ωn0 `2 , . . . , ωm u, which are i.i.d. following a distribution on tn0 ` 1, n0 ` 2, . . . , nu.
We can compute the sampling density on tn0 ` 1, n0 ` 2, . . . , nu based on (14) and (15) (or (31) and
(32)) by removing the zero columns in T “ ΦΨ˚ (replacing T with T ren0 `1 , en0 `2 , . . . , en s). Next, we
state variations of Theorems V.1 and V.2 in these cases.
Corollary V.3. Suppose circulant transform Φ in (35) satisfies λrks “ 0 for k P rn0 s. Then the sampling
density in Step 2), for `1 -norm minimization (5) based on (15), is the uniform distribution on tn0 `
1, n0 ` 2, . . . , nu.

Corollary V.4. Suppose concatenated transform Φ in (38) satisfies λj rks “ 0 for all j P r`s and k P rn0 s.
Then the sampling density in Step 2), for mixed norm minimization (27) based on (32), is the uniform
distribution on tn0 ` 1, n0 ` 2, . . . , nu.
These results are direct consequences of Theorems V.1 and V.2, whose proofs translate with no changes
other than removing the zero columns in T (the columns indexed by rn0 s).
Next, we specialize these results to total variation minimization. We define the 1D finite difference
operator ΦTV,n by (34), where
$
’
1
’
’
&
φrks “

´1
’
’
’
%0

k“1
k“2
k P t3, 4, . . . , nu.

Then }f }TV “ }ΦTV,n f }1 is the 1D total variation of f . Clearly, the circulant transform ΦTV,n is not
injective, since its null space contains the direct current (DC) component – Ψ˚ e1 . By Corollary V.3, we
adopt the following sampling scheme for total variation minimization:
1) Always sample index ω1 “ 1.

19

2) Generate a multi-set of m ´ 1 indices tω2 , ω3 , . . . , ωm u, which are i.i.d. following the uniform
distribution on t2, 3, . . . , nu.
Total variation is more commonly used for 2D signals (e.g., images). For a 2D signal f of size n1 ˆn2 ,
the finite difference operator is a concatenation of the vertical and horizontal finite difference operators:
ff
«
In2 b ΦTV,n1
.
ΦTV,n1 ,n2 “
ΦTV,n2 b In1
The anisotropic and isotropic total variations of f are defined by
}f }TV,aniso “ }ΦTV,n1 ,n2 f }1 ,
}f }TV,iso “ ||| ΦTV,n1 ,n2 f |||G,1 ,

where the partion G “ tG1 , . . . , Gn u is defined by (37) for ` “ 2 and n “ n1 n2 . Let the measurement
operator Ψ be the 2D DFT on signals of size n1 ˆ n2 . Similar to the 1D case, the DC component Ψ˚ e1
belongs to the null space of ΦTV,n1 ,n2 . By Corollary V.4, we use the same two-step sampling scheme as
in the 1D case.
VI. P ROOF OF T HEOREM II.1
In this section, we prove Theorem II.1, which provides a sufficient condition for exact recovery of
sparse signals in a transform domain from noiseless observations. The proof of Theorem II.1 is based
on the golfing scheme [31], which was originally proposed for matrix completion [31] and later adopted
to compressed sensing [15] and to structured matrix completion [30].
The golfing scheme constructs an inexact dual certificate. The notion of a dual certificate was originally
proposed for compressed sensing (cf. [13]). To reconstruct an s-sparse f P Cd from b “ Af , it was
proposed to estimate f as the solution to
minimize }f˜}1
f˜PCd

subject to

b “ Af˜.

A dual certificate is a subgradient v P Cd of } ¨ }1 at f such that f is orthogonal to all null vectors of
the sensing matrix A. In matrix completion, the objective function is replaced from the `1 -norm to the
nuclear norm and the sensing matrix is replaced by a pointwise sampling operator. Gross [31] proposed
the clever golfing scheme that constructs an inexact dual certificate, which is close to the exact dual
certificate, and showed a low-rank matrix is exactly reconstructed from partial entries sampled at a near
optimal rate. Candes and Plan [15] adopted the golfing scheme back to compressed sensing and showed
that exact recovery is guaranteed from m “ Ops log dq incoherent measurements, which improves on the
previous performance guarantee with m “ Ops log4 dq.
Chen and Chi [30] adopted the golfing scheme to structured matrix completion. Let T : Cn Ñ Cn1 ˆn1
be a linear operator that maps a vector x P Cn to a structured matrix T x P Cn1 ˆn2 (e.g., a Hankel

20

matrix). Chen and Chi [30] proposed to estimate x by
minimize
}T g}˚
n
gPC

subject to

SΩ g “ SΩ x.

This can be interpreted as recovery of low-rank matrices in a special transform domain, where T maps
the standard basis vectors te1 , . . . , en u to unit-norm matrices with disjoint supports. Unlike compressed
sensing or matrix completion, in structured matrix completion, the dimension of the vector space where
the unknown signal is rearranged as a structured low-rank matrix is larger than the dimension of the
vector space where measurements are sampled. In other words, T is a tall matrix and is not surjective.
With this nontrivial difference, the conventional approaches [31], [15] do not apply directly to structured
matrix completion. Chen and Chi [30] cleverly modified the definition of an inexact dual certificate and
the golfing scheme accordingly and provided performance guarantee at a near optimal sample complexity.
We adopt their approach to recovery of sparse signals in a transform domain, where the nuclear norm is
replaced by the `1 -norm3 . Notably, we extend the theory to the case where T is not necessarily a unitary
transform (e.g., T ˚ T “ In ), which is the case in various practical applications.
We first present the following lemma that extends the notion of an inexact dual certificate for recovery
of sparse signals in a transform domain where the transform T is not necessarily unitary.
Lemma VI.1 (Uniqueness by an Inexact Dual Certificate). Suppose that T : Cn Ñ CN is injective. Let
J Ă rN s denote the support of T x, i.e. the elements of J correspond to the locations of the nonzero

elements in T x. Let Ω be a multi-set that consists of elements in rns with possible repetitions. Let Ω1
denote the set of all distinct elements in Ω. Suppose that
› 1
›n
›
›
˚
S Ω T : ΠJ ´ ΠJ T T : ΠJ › ď .
› ΠJ T SΩ
m
2

(39)

If there exists a vector v P CN satisfying
˚
: ˚
pT T : ´ T SΩ
1 SΩ1 T q v “ 0,

}ΠJ pv ´ sgnpT xqq}2 ď

1
,
7n}T }1Ñ2 }T : }2Ñ8

(40)

(41)

and
1
}pIN ´ ΠJ qv}8 ď ,
2

(42)

then x is the unique minimizer to (5).
Proof of Lemma VI.1. See Section VI-B.
The next lemma shows that such an inexact dual certificate exists with hight probability under the
hypothesis of Theorem II.1.
3

A subset of the authors [35] sharpened the original analysis of the completion of structured low-rank matrices by Chen and
Chi [30] particularly on the noise propagation in the recovery. In this paper, we generalize the improved version [35].

21

Lemma VI.2 (Existence of an Inexact Dual Certificate). Suppose the hypotheses of Theorem II.1 hold.
Then, with probability 1 ´ e´β ´ 1{n, there exists a vector v P CN satisfying (40) to (42).
Proof of Lemma VI.2. See Section VI-C.
Lemma VI.2 together with Lemma VI.1 implies Theorem II.1. Indeed, we only need to verify (39). By
Lemma VI.3, (39) holds with probability at least 1 ´ 2{n provided that m ě 32µs maxt1{p1 ´ }T ˚ T ´
In }q, 1{6u log n. This completes the proof of Theorem II.1.

In the next section, we will introduce fundamental estimates that will be used in the proofs of
Lemmas VI.1 and VI.2.
A. Lemmas on fundamental estimates
˚ S T : , which
The following lemmas provides estimates on various functions of the random matrix T SΩ
Ω

are analogous to the corresponding estimates for RIPless compressed sensing [15].
Similarly to RIPless compressed sensing, we also employ the notion of incoherence. In fact, our
incoherence assumption in (7) is analogous to a generalized version for anisotropic compressed sensing
[36], [32], [37].
One important distinction from compressed sensing is that the isotropy property is not satisfied. Indeed,
since the random indices in Ω are i.i.d. following the uniform distribution on rns, the random matrix
˚ S T : satisfies
T SΩ
Ω

n
˚
ET SΩ
SΩ T : “ T T : .
m

While T T : is an orthogonal projection (idempotent and self-adjoint), it is not necessarily an identity
operator. The rank-deficiency of T T : requires new analysis in Lemmas VI.1 and VI.2 compared to the
previous results for compressed sensing with the canonical sparsity model [15]. However, the fundamental
˚ S T : from their expectations and do not require the
estimates measure the deviations of functions of T SΩ
Ω

isotropy property (T ˚ T “ In ). We present the following lemmas for the fundamental estimates, whose
proofs are deferred to the appendix.
Lemma VI.3 (E1: Local Isometry on a Proper Subspace). Suppose T : Cn Ñ CN and Tr “ pT : q˚ satisfy
(7) with parameter µ. Let γ be defined in (6). Let J be a fixed subset of rN s satisfying |J| “ s. Let
Ω “ tω1 , . . . , ωm u where ωj s are i.i.d. following the uniform distribution on rns. Then for δ ą 0,
ˆ
˙
´› ´ n
¯ ›
¯
m
δ 2 {2
›
›
˚
:
:
P ›ΠJ
T S SΩ T ´ T T ΠJ › ě δ ď 2s exp ´
¨
.
m Ω
sµ 1{p1 ´ }γT ˚ T ´ In }q ` δ{3

Proof of Lemma VI.3. See Appendix B.
Lemma VI.4 (E2: Low Distortion). Suppose T : Cn Ñ CN and Tr “ pT : q˚ satisfy (7) with parameter
µ. Let γ be defined in (6). Let q P CN be a fixed vector. Let J be a fixed subset of rN s satisfying

22

|J| “ s. Let Ω “ tω1 , . . . , ωm u where ωj s are i.i.d. following the uniform distribution on rns. Then for

each t ď 1{2,
$
˜d
¸2 ,
›
& 1
.
´› ´ n
¯
¯
˚
mp1 ´ }γT T ´ In }q
›
›
˚
P › ΠJ
.
T SΩ
SΩ T : ´ T T : ΠJ q › ě t}ΠJ q}2 ď exp ´
t
´1
% 4
m
sµ
2

Proof of Lemma VI.4. See Appendix C.
Lemma VI.5 (E3: Off-Support Incoherence). Suppose T : Cn Ñ CN and Tr “ pT : q˚ satisfy (7) with
parameter µ. Let γ be defined in (6). Let q P CN be a fixed vector. Let J be a fixed subset of rN s
satisfying |J| “ s. Let Ω “ tω1 , . . . , ωm u where ωj s are i.i.d. following the uniform distribution on rns.
Then for each t ą 0,
›
¯
¯
´›
´n
›
›
˚
TrSΩ
SΩ T ˚ ´ TrT ˚ ΠJ q › ě t}ΠJ q}2
P ›ΠrN szJ
m
8
ˆ
˙
m
t2
?
ď 2N exp ´
¨
.
2µ 1{p1 ´ }γT ˚ T ´ In }q ` st{3

Proof of Lemma VI.5. See Appendix D.
Lemma VI.6 (E3’: Off-Group-Support Incoherence). Suppose T : Cn Ñ CL and Tr “ pT : q˚ satisfy
(28) with parameter µ. Let γ be defined in (6). Let q P CL be a fixed vector. Let G “ tG1 , . . . , GN u
Ť
be a partition of rLs. Let J be a fixed subset of rN s satisfying |J| “ s. Let GJ “ jPJ Gj . Let
Ω “ tω1 , . . . , ωm u where ωj s are i.i.d. following the uniform distribution on rns. Then for each t ą 0,
ˆ›
˙
›
´n
¯
›
›
˚
˚
˚
r
r
P ›ΠrLszGJ
T S SΩ T ´ T T ΠGJ q ›
ě t}ΠGJ q}2
m Ω
G,8
˙
ˆ
t2
m
?
¨
.
ď 2 max |Gj |N exp ´
2µ 1{p1 ´ }γT ˚ T ´ In }q ` st{3
jPrN s

Proof of Lemma VI.6. See Appendix E.
B. Proof of Lemma VI.1
Our proof essentially adapts the arguments of Chen and Chi [30, Appendix B] for the structured
low-rank matrix completion problem. There are two key differences in the two proofs. First, the `1 norm replaces the nuclear norm. Second, T is a general injective transform, which is not necessarily
unitary. These differences require nontrivial modifications of crucial steps in the proof. Furthermore, the
upper bound on the deviation of v from sgnpT xq in (41) is sharpened by optimizing parameters. This
improvement also applies to the previous work [30].
Let x̂ “ x ` h be the minimizer to (5). We show that T h “ 0 in two complementary cases. Then by
the injectivity of T , h “ 0, or equivalently, x̂ “ x.
Case 1: We first consider the case when h satisfies
}ΠJ T h}2 ď 3n}T }1Ñ2 }T : }2Ñ8 }ΠrN szJ T h}2 .

(43)

23

Since sgnpΠrN szJ T hq and sgnpT xq have disjoint supports, it follows that sgnpT xq ` sgnpΠrN szJ T hq
and sgnpT xq coincide on J . Furthermore, }sgnpT xq ` sgnpΠrN szJ T hq}8 ď 1. Therefore, sgnpT xq `
sgnpΠrN szJ T hq is a valid sub-gradient of the `1 -norm at T x. Then it follows that
}T x ` T h}1 ě }T x}1 ` xsgnpT xq ` sgnpΠrN szJ T hq, T hy

(44)

“ }T x}1 ` xv, T hy ` xsgnpΠrN szJ T hq, T hy ´ xv ´ sgnpT xq, T hy.

In fact, xv, T hy “ 0 as shown below. The inner product of T h and v is decomposed as
˚
:
˚
:
xv, T hy “ xv, pIN ´ T T : qT hqy ` xv, pT T : ´ T SΩ
1 SΩ1 T qT hy ` xv, T SΩ1 SΩ1 T T hy.

(45)

Indeed, all three terms in the right-hand side of (45) are 0. Since T T : is the orthogonal projection onto
the range space of T , the first term is 0. The second term is 0 by the assumption on v in (40). Since
x̂ is feasible for (5), SΩ x̂ “ SΩ x. Thus SΩ h “ SΩ px̂ ´ xq “ 0, i.e. e˚ω h “ 0 for all ω P Ω, which also

implies SΩ1 h “ 0. Then it follows that SΩ1 T : T h “ SΩ1 h “ 0. Thus the third term of the right-hand side
of (45) is 0.
Since the sgnp¨q operator commutes with ΠrN szJ and ΠrN szJ is idempotent, we get
xsgnpΠrN szJ T hq, T hy “ xΠrN szJ sgnpΠrN szJ T hq, T hy
“ xsgnpΠrN szJ T hq, ΠrN szJ T hy
“ }ΠrN szJ T h}1 .

Then (44) implies
}T x ` T h}1 ě }T x}1 ` }ΠrN szJ T h}1 ´ xv ´ sgnpT xq, T hy.

(46)

We derive an upper bound on the magnitude of the last term in the right-hand side of (46) given by
|xv ´ sgnpT xq, T hy| “ |xΠJ pv ´ sgnpT xqq, T hy ` xΠrN szJ pv ´ sgnpT xqq, T hy|
ď |xΠJ pv ´ sgnpT xqq, T hy| ` |xΠrN szJ v, T hy|

(47a)

ď }ΠJ pv ´ sgnpT xqq}2 }ΠJ T h}2 ` }ΠrN szJ v}8 }ΠrN szJ T h}1
1
1
}ΠJ T h}2 ` }ΠrN szJ T h}1 ,
ď
:
7n}T }1Ñ2 }T }2Ñ8
2

(47b)
(47c)

where (47a) holds by the triangle inequality and the fact that T x is supported on J ; (47b) by Hölder’s
inequality; (47c) by the assumptions on v in (41) and (42).
We continue by applying (47) to (46) and get
1
1
}ΠJ T h}2 ` }ΠrN szJ T h}1
:
7n}T }1Ñ2 }T }2Ñ8
2
3
1
ě }T x}1 ´ }ΠrN szJ T h}2 ` }ΠrN szJ T h}2
7
2
1
“ }T x}1 ` }ΠrN szJ T h}2 ,
14

}T x ` T h}1 ě }T x}1 ´

24

where the second step follows from (43).
Then, }T x̂}1 ě }T x}1 ě }T x̂}1 , which implies ΠrN szJ T h “ 0. By (43), we also have ΠJ T h “ 0.
Therefore, it follows that T h “ 0.
Case 2: Next, we consider the complementary case when h satisfies
}ΠJ T h}2 ą 3n}T }1Ñ2 }T : }2Ñ8 }ΠrN szJ T h}2 .

(48)

In the previous case, we have shown that SΩ h “ 0. Thus SΩ T : T h “ 0. Then together with pIN ´
T T : qT “ 0, we get
´n
m

which implies

¯
˚
T SΩ
SΩ T : ` IN ´ T T : T h “ 0,

A
´n
¯ E
˚
0 ě ΠJ T h,
T SΩ
SΩ T : ` IN ´ T T : T h
A
´m
¯
E
n
˚
“ ΠJ T h,
T SΩ
SΩ T : ` IN ´ T T : ΠJ T h
m
A
´n
¯
E
˚
` ΠJ T h,
T SΩ
SΩ T : ` IN ´ T T : ΠrN szJ T h .
m

The magnitude of the first term in the right-hand side of (49) is lower-bounded by
ˇA
´n
¯
Eˇ
ˇ
ˇ
˚
T SΩ
S Ω T : ` I N ´ T T : ΠJ T h ˇ
ˇ ΠJ T h,
m
ˇA
¯
Eˇ
´
n
ˇ
ˇ
˚
“ |xΠJ T h, ΠJ T hy| ´ ˇ ΠJ T h, T T : ´ T SΩ
SΩ T : ΠJ T h ˇ
m
›
›
n
›
›
˚
ě }ΠJ T h}22 ´ ›ΠJ T T : ΠJ ´ ΠJ T SΩ
SΩ T : ΠJ › }ΠJ T h}22
m
1
ě }ΠJ T h}22 ,
2

(49)

(50)

where the last step follows from the assumption in (39).
Next, we derive an upper bound on the second term in the right-hand side of (49). To this end, we first
computes the operator norm of T ek e˚ T : for k P rns. In fact, }T ek e˚ T : } “ }T ek }2 }Trek }2 , where Tr is the
k

adjoint of

T :.

k

Therefore, we only need to compute }T ek }2 and }Trek }2 . First, }T ek }2 is upper-bounded

by
max }T ek }2 “ }T }1Ñ2 .
kPrns

On the other hand, }Trek }2 is upper-bounded by
max }Trek }2 “ }Tr}1Ñ2 “ }T : }2Ñ8 ,
kPrns

where the last step holds since Tr is the adjoint operator of T : and `n8 is the dual space of `n1 . By the
above upper bounds on }T ek }2 and }Trek }2 , we get
}T ek e˚k T : } ď }T }1Ñ2 }T : }2Ñ8 .

25

n
˚
:
m T SΩ SΩ T

` IN ´ T T : is upper-bounded by
˜
¸
m
›
›n
ÿ
n
›
›
˚
SΩ T : ` IN ´ T T : › ď
}T eω1 e˚ω1 T : ` IN ´ T T : } `
}T eωj e˚ωj T : }2
› T SΩ
m
m
j“2
¸
˜
m
ÿ
n
˚
:
˚
:
:
ď
maxp}T eω1 eω1 T }, }IN ´ T T }q `
}T eωj eωj T }2
m
j“2

Then the operator norm of

(51)

ď n}T }1Ñ2 }T : }2Ñ8 ,

where the second step follows since pT eω1 e˚ω1 T : q˚ pIN ´ T T : q “ 0 and pIN ´ T T : qpT eω1 e˚ω1 T : q˚ “ 0.
The second term in the right-hand side of (49) is then upper-bounded by
ˇA
´n
¯
Eˇ
ˇ
ˇ
˚
:
:
T SΩ SΩ T ` IN ´ T T ΠrN szJ T h ˇ
ˇ ΠJ T h,
m
›
›n
›
›
˚
ď › T SΩ
SΩ T : ` IN ´ T T : › }ΠJ T h}2 }ΠrN szJ T h}2
m
ď n}T }1Ñ2 }T : }2Ñ8 }ΠJ T h}2 }ΠrN szJ T h}2 ,

(52)

where the last step follows from (51).
Applying (50) and (52) to (49) provides
ˇA
´n
¯
Eˇ
ˇ
ˇ
˚
0 ě ˇ ΠJ T h,
T SΩ
SΩ T : ` IN ´ T T : ΠJ T h ˇ
m
ˇA
´n
¯
Eˇ
ˇ
ˇ
˚
´ ˇ ΠJ T h,
T SΩ
SΩ T : ` IN ´ T T : ΠrN szJ T h ˇ
m
1
ě }ΠJ T h}22 ´ n}T }1Ñ2 }T : }2Ñ8 }ΠJ T h}2 }ΠrN szJ T h}2
2
1
1
ě }ΠJ T h}22 ´ }ΠJ T h}22
2
3
1
2
“ }ΠJ T h}2 ě 0,
6
where the second inequality follows from (48). Then it is implied that ΠJ T h “ 0. By (48), we also have
ΠrN szJ T h “ 0. Therefore, T h “ 0, which completes the proof.

C. Proof of Lemma VI.2
We construct a dual certificate v using a golfing scheme. Since the isotropy is not satisfied, the original
golfing scheme needs to be modified accordingly. We adopt the version for structured matrix completion
[30].
Recall that the elements of Ω “ tω1 , . . . , ωm u are i.i.d. following the uniform distribution on rns. We
partition the multi-set Ω into ` multi-sets so that Ω1 consists of the first m1 elements of Ω, Ω2 consists
ř
of the next m2 elements of Ω, and so on, where `i“1 mi “ m. Then, Ωi s are mutually independent and
each Ωi consists of i.i.d. random indices.
The version of the golfing scheme in this paper generates a dual certificate v P CN from intermediate

26

vectors qi P CN for i “ 0, . . . , ` ´ 1 by
˙
` ˆ
ÿ
n r ˚
˚
:
v“
T S SΩ T ` IN ´ T T qi´1 ,
mi Ωi i
i“1
where qi s are generated as follows: first, initialize q0 “ sgnpT xq; next, generate qi s recursively by
ˆ
˙
n r ˚
˚
˚
r
qi “ ΠJ T T ´
T S SΩ T
qi´1 , i “ 1, . . . , ` ´ 1.
mi Ωi i
Here, Tr denotes the adjoint of T : .
Note that
ˆ

˙
n r ˚
˚
˚
pT T ´
T S SΩ T ` IN ´ TrT
mi Ωi i
n
˚
: ˚r ˚
˚
˚
: ˚
r ˚
“
pT T : ´ T SΩ
` pT T : ´ T SΩ
1 SΩ1 T q T SΩ SΩi T
1 SΩ1 T q pIN ´ T T q
i
mi
n r ˚ r ˚
˚
˚
˚
r ˚
“
pT T ´ T SΩ1 SΩ1 T ˚ qTrSΩ
SΩi T ˚ ` pTrT ˚ ´ TrSΩ
1 SΩ1 T qpIN ´ T T q “ 0.
i
mi
:

˚
: ˚
T SΩ
1 SΩ1 T q

Thus it follows that v satisfies (40).
The rest of the proof is devoted to show that v satisfies (41) and (42), which follows similarly to the
proof of [15, Lemma 3.3]. For completeness, we verify that the arguments in [15] are valid in our setting
(with neither isotropy nor self-adjointness).
We show that qi satisfies the following two properties with high probability for each i P r`s: first,
}qi }2 ď ci }qi´1 }2

and, second,

›
›
˙
ˆ
›
›
˚
˚
˚
r
›ΠrN szJ n TrSΩ
qi´1 ››
SΩi T ` IN ´ T T
i
›
mi

(53)

ď ti }qi´1 }2 .

(54)

8

Let p1 piq (resp. p2 piq) denote the probability that the inequality in (53) (resp. (54)) does not hold.
Since qi´1 is independent of Ωi , by Lemma VI.4, p1 piq is upper-bounded by
ˆ
˙
1 a
p1 piq ď exp ´ pci mi p1 ´ }γT ˚ T ´ In }q{psµq ´ 1q2 .
4
Therefore, p1 piq ď α1 e´β if
mi ě

2 ` 8pβ ` log αq
µs
¨
.
2
1 ´ }γT ˚ T ´ In }
ci

(55)

On the other hand, note that qi´1 “ ΠJ qi´1 . Then it follows that
›
›
›
›
ˆ
˙
ˆ
˙
›
›
›
›
n r ˚
˚
˚
˚
˚
˚
r
r
›ΠrN szJ n TrSΩ
›
›
SΩi T ` IN ´ T T
qi´1 › “ ›ΠrN szJ
T SΩi SΩi T ` IN ´ T T
ΠJ qi´1 ››
i
›
mi
m
8
8
›
›
ˆ i
˙
›
›
n
˚
˚
˚
“ ››ΠrN szJ
TrS SΩ T ´ TrT
ΠJ qi´1 ›› .
mi Ωi i
8

27

Again, we use the fact that qi´1 is independent of Ωi . Then, by Lemma VI.5, p2 piq is upper-bounded by
ˆ
˙
3t2i mi
?
p2 piq ď 2N exp ´
.
6µ{p1 ´ }γT ˚ T ´ In }q ` 2µ sti
Therefore, p2 piq ď α1 e´β if
ˆ
˙
2
2
? pβ ` logp2αq ` log N qsµ.
mi ě 2
`
ti sp1 ´ }γT ˚ T ´ In }q 3ti s
We set the parameters similarly to the proof of [15, Lemma 3.3] as follows:


`
˘
log2 s
:
`“
` log2 n ` log2 }T }1Ñ2 }T }2Ñ8 ` 3,
2
$
&1{d2?log N e i “ 1, 2, 3,
ci “
%1{2
3 ď i ď `,
$
&1{d4?s e
i “ 1, 2, 3,
ti “
?
%log N {d4 s e 3 ď i ď `,
mi “ d10p1 ` log 6 ` βqµsc´2
i e,

(56)

(57)

@i.

By the construction of v , we have
`
ÿ

ˆ

˙
n r ˚
˚
˚
r
ΠJ v “
ΠJ
T S S Ω T ` IN ´ T T
qi´1
mi Ωi i
i“1
˙

ˆ
` „
ÿ
n
˚
˚
˚
qi´1
“
ΠJ qi´1 ´ ΠJ TrT ´
TrS SΩ T
mi Ωi i
i“1
`
ÿ

“

pqi´1 ´ qi q “ q0 ´ q`

i“1

“ sgnpT xq ´ q` “ ΠJ sgnpT xq ´ q` .

Therefore, (53) implies
}ΠJ pv ´ sgnpT xqq}2 “ }q` }2 ď

`
ź

?

ci }sgnpT xq}2 ď

i“1

s
.
2` log N

Next, by (53) and (54), we have
}ΠrN szJ v}8

›
ˆ
˙
` ›
ÿ
›
›
n r ˚
˚
˚
r
›
ď
qi´1 ››
›ΠrN szJ mi T SΩi SΩi T ` IN ´ T T
i“1
`
ÿ

ď

ti }qi´1 }2

(58)

i“1

˜
ď

?

s t1 `

`
ÿ
i“2

8

ti

i´1
ź
j“1

¸
cj

.

28

By setting parameters as in (57), the right-hand side in (58) is further
ˆ
˙
log N
1
1
`
1` ?
` ¨¨¨ ă
4
4 log N
2 log N

upper-bounded by
1
.
2

Then, we have shown that v satisfies (42).
It remains to show that (53) and (54) hold with the desired probability. From (55) and (56), it follows
that
1
pj piq ď e´β ,
6

@i P r`s, @j “ 1, 2.

In particular, we have
2 ÿ
3
ÿ

pj piq ď e´β .

j“1 i“1

This implies that the first three Ωi s satisfy (53) and (54) except with probability e´β .
On the other hand, we also have
1
p1 piq ` p2 piq ă ,
3

@i “ 4, . . . , `.

In other words, the probability that Ωi satisfies (53) and (54) is at least 2{3. The union bound doesn’t
show that Ωi satisfies (53) and (54) for all i ě 4 with the desired probability.
As in the proof of [15, Lemma 3.3], we adopt the oversampling and refinement strategy by Gross [31].
Recall that each random index set Ωi consists of i.i.d. random indices following the uniform distribution
on rns. Thus Ωi s are mutually independent. In particular, we set Ωi s are of the same cardinality in (57).
Therefore, Ωi s are i.i.d. random variables. We generate a few extra copies of Ωi for i “ ` ` 1, . . . , `1 ` 3
where `1 “ 3p` ´ 3q. Then, by Hoeffding’s inequality, there exist at least ` ´ 3 Ωi s for i ě 4 that
satisfy (53) and (54) with probability 1 ´ 1{n. (We refer more technical details for this step to [15,
Section III.B].) Therefore, there are ` good Ωi s satisfying (53) and (54) with probability 1 ´ e´β ´ 1{n,
and the dual certificate v is constructed from these good Ωi s. The total number of samples for this
construction requires
mě

40p1 ` log 6 ` βqµsp3 log N ` 3`q
,
1 ´ }γT ˚ T ´ In }

which can be simplified as
mě

`
˘‰
Cp1 ` βqµs “
:
log
N
`
log
}T
}
}T
}
1Ñ2
2Ñ8
1 ´ }γT ˚ T ´ In }

for a numerical constant C .
VII. P ROOFS FOR T HEOREMS II.3 AND II.5
In this section, we prove Theorems II.3 and II.5, which provide sufficient conditions for stable recovery
of sparse signals in a transform domain from noisy data.

29

A. Proof of Theorem II.3
Let h :“ x̂ ´ x. Since x̂ is the minimizer to (8), it follows that
}T x}1 ě }T x̂}1 “ }T x ` T h}1
˚
˚
ě }T x ` T pIn ´ SΩ
1 SΩ1 qh}1 ´ }T SΩ1 SΩ1 h}1 .

Since x and x̂ are feasible for (8), it follows that
`
˘
˚
7
˚
7
max }T SΩ
1 SΩ1 px̂ ´ x q}2 , }T SΩ1 SΩ1 px ´ x q}2
`
˘
ď }T } max }SΩ1 px̂ ´ x7 q}2 , }SΩ1 px ´ x7 q}2 ď }T }.

(59)

(60)

Therefore, by the triangle inequality, we have
˚
˚
˚
7
˚
7
}T SΩ
1 SΩ1 h}2 “ }T SΩ1 SΩ1 px̂ ´ xq}2 ď }T SΩ1 SΩ1 px̂ ´ x q}2 ` }T SΩ1 SΩ1 px ´ x q}2 ď 2}T }.

(61)

The rest of the proof will compute upper bounds on }T h}2 in two complementary cases similarly to
the proof of Lemma VI.1. Unlike the noiseless case (x7 “ x and  “ 0) in Lemma 54, the condition in
(61) does not necessarily imply SΩ h “ 0. In fact, the proof of Lemma VI.1 critically depends on the
˚ S 1 qh. Then it follows that
condition SΩ h “ 0. Essentially, we replace h by pIn ´ SΩ
1
Ω
˚
SΩ1 pIn ´ SΩ
1 SΩ1 qh “ 0.

(62)

˚ S 1 qh satisfies
Case 1: We first consider the case when pIn ´ SΩ
1
Ω
˚
:
˚
}ΠJ T pIn ´ SΩ
1 SΩ1 qh}2 ď 3n}T }1Ñ2 }T }2Ñ8 }ΠrN szJ T pIn ´ SΩ1 SΩ1 qh}2 ,

(63)

where J denotes the support of T x.
Under (63), similarly to the proof of Lemma VI.1, we have
˚
}T x ` T pIn ´ SΩ
1 SΩ1 qh}1 ě }T x}1 `

1
˚
}Π
T pIn ´ SΩ
1 SΩ1 qh}2 .
14 rN szJ

(64)

Combining (59) and (64) provides
?
?
˚
˚
˚
N }T SΩ
N }T }.
}ΠrN szJ T pIn ´ SΩ
1 SΩ1 qh}2 ď 14}T SΩ1 SΩ1 h}1 ď 14
1 SΩ1 h}2 ď 28

(65)

On the other hand, (63) implies
˚
˚
˚
}T pIn ´ SΩ
1 SΩ1 qh}2 ď }ΠrN szJ T pIn ´ SΩ1 SΩ1 qh}2 ` }ΠJ T pIn ´ SΩ1 SΩ1 qh}2
˚
ď p1 ` 3n}T }1Ñ2 }T : }2Ñ8 q}ΠrN szJ T pIn ´ SΩ
1 SΩ1 qh}2 .

Therefore, combining (61), (65) and (66) provides
!
? `
˘)
}T h}2 ď 2 ` 28 N 3n}T }1Ñ2 }T : }2Ñ8 ` 1 }T }.

(66)

(67)

30

˚ S 1 qh satisfies
Case 2: Next, we consider the complementary case when pIn ´ SΩ
1
Ω
˚
:
˚
}ΠJ T pIn ´ SΩ
1 SΩ1 qh}2 ą 3n}T }1Ñ2 }T }2Ñ8 }ΠrN szJ T pIn ´ SΩ1 SΩ1 qh}2 .

(68)

˚ S 1 qh “ 0. Therefore,
Again, similarly to the proof of Lemma VI.1, we get pIn ´ SΩ
1
Ω
˚
˚
}T h}2 ď }T pIn ´ SΩ
1 SΩ1 qh}2 ` }T SΩ1 SΩ1 T h}2 ď 2}T },

which is smaller than the upper bound on }T h}2 in the previous case.
By applying }h}2 ď }T h}2 {σmin pT q to (67), we obtain the desired upper bound on }h}2 . This completes
the proof.
B. Proof of Theorem II.5
By Theorem II.4, the condition in (13) implies that

n
˚
:
m T SΩ SΩ T

satisfies the condition in (10) with

constant δ “ 1{3. Note that the estimates in Lemmas lemmas VI.3 to VI.5 are implied by (10). Therefore,
the rest of the proof will be identical to that of Theorem II.5 except that we compute a tighter upper
˚ S 1 qh} as follows.
bound on }ΠJ T pIn ´ SΩ
1
2
Ω
˚ S 1 qh as
First, we decompose ΠJ T pIn ´ SΩ
1
Ω

¯
´
n
˚
˚
SΩ T : T h
ΠJ T pIn ´ SΩ
T T : ´ T SΩ
1 SΩ1 qh “ ΠJ
m
n
˚
˚
` ΠJ T pSΩ SΩ ´ SΩ
1 SΩ1 qh
m
¯
´n
˚
´ 1 T SΩ
` ΠJ
1 SΩ1 h.
m

(69)

Let J1 correspond to the indices of the s-largest coefficients of ΠrN szJ T h; J2 to the indices of the
next s-largest coefficients of ΠrN szJ T h, and so on. Then the `2 -norm first term in the right-hand side of
(69) is upper-bounded by
› ´
¯ ›
n
›
›
˚
:
:
Π
T
S
S
T
T h›
T
T
´
› J
Ω Ω
m
› ´
›
¯ 2
n
›
›
:
˚
:
ď ›ΠJ T T ´ T SΩ SΩ T ΠJYJ1 T h›
m
2 ›
¯
ÿ ›› ´
n
›
:
˚
:
`
›ΠJ T T ´ T SΩ SΩ T ΠJi T h› .
m
2
iě2

By (10), the first term in the right-hand side of (70) is upper-bounded by
› ´
›
¯
n
1
1
›
›
˚
SΩ T : ΠJYJ1 T h› ď }ΠJYJ1 T h}2 ď }T h}2 .
›ΠJ T T : ´ T SΩ
m
3
3
2
By (10), the second term in the right-hand side of (70) is upper-bounded by
›
¯
ÿ ›› ´
n
›
˚
SΩ T : ΠJi T h›
›ΠJ T T : ´ T SΩ
m
2
iě2
ÿ
ÿ
1
1
1
ď
}ΠJi T h}2 ď ?
}ΠJi T h}1 “ ? }ΠrN szJ T h}1 .
3 iě2
3 s iě1
3 s

(70)

(71)

(72)

31

Since x̂ is the minimizer to (8), we have the so called “cone” constraint:
}T x}1 ě }T x̂}1 ě }T x ` T h}1 ě }ΠJ T x}1 ´ }ΠJ T h}1 ` }ΠrN szJ T h}1 ´ }ΠrN szJ T x}1 ,

which implies
}ΠrN szJ T h}1 ď 2}ΠrN szJ T x}1 ` }ΠJ T h}1 “ }ΠJ T h}1 ,

where the last step follows since T x is supported on J . Therefore, (72) implies
›
¯
ÿ ›› ´
n
1
1
1
›
˚
SΩ T : ΠJi T h› ď ? }ΠrN szJ T h}1 ď ? }ΠJ T h}1 ď }ΠJ T h}2 .
›ΠJ T T : ´ T SΩ
m
3 s
3 s
3
2
iě2
Plugging (71) and (73) to (70) provides
› ´
¯ ›
n
2
›
›
˚
SΩ T : T h› ď }T h}2 .
›ΠJ T T : ´ T SΩ
m
3
2

(73)

(74)

Next, we derive an upper bound on the `2 -norm of the second term in the right-hand side of (69).
Since Ω1 consists of distinct elements in Ω, it follows that
˚
˚
SΩ
1 SΩ1 SΩ SΩ “

ÿ

˚
˚
SΩ
1 SΩ1 ek ek “

kPΩ

Furthermore,

˚ S 1
SΩ
1
Ω

ÿ

˚
ek e˚k “ SΩ
SΩ .

kPΩ

is idempotent. Therefore, we obtain the following identity:
˚
˚
˚
˚
˚
SΩ
SΩ ´ SΩ
1 SΩ1 “ pSΩ SΩ ´ SΩ1 SΩ1 qSΩ1 SΩ1 .

(75)

From (75), we get
˚
˚
˚
˚
˚
}T pSΩ
SΩ ´ SΩ
1 SΩ1 qh}2 “ }T pSΩ SΩ ´ SΩ1 SΩ1 qSΩ1 SΩ1 h}2
˚
˚
:
˚
“ }T pSΩ
SΩ ´ SΩ
1 SΩ1 qT T SΩ1 SΩ1 h}2
˚
˚
:
˚
ď }T pSΩ
SΩ ´ SΩ
1 SΩ1 qT }}T SΩ1 SΩ1 h}2

(76)

˚
ď max }T ek e˚k T : }p|Ω| ´ |Ω1 |q}T SΩ
1 SΩ1 h}2
k

˚
ď }T }1Ñ2 }T : }2Ñ8 p|Ω| ´ |Ω1 |q}T SΩ
1 SΩ1 h}2 .

Then the `2 -norm of the second term in the right-hand side of (69) is upper-bounded by
›
›
n
n
›
›
˚
˚
˚
˚
SΩ ´ SΩ
ď }T pSΩ
SΩ ´ SΩ
1 SΩ1 qh›
1 SΩ1 qh}2
›ΠJ T pSΩ
m
m
2
n
˚
ď }T }1Ñ2 }T : }2Ñ8 p|Ω| ´ |Ω1 |q}T SΩ
1 SΩ1 h}2 .
m

(77)

By applying (74) and (77) to (69), then combining the result with (61) and (65), we get
´n
¯
?
2
n
}T h}2 ď 2}T } ` 28 N }T } ` }T h}2 ` 2 }T }1Ñ2 }T : }2Ñ8 p|Ω| ´ |Ω1 |q}T } ` 2
´ 1 }T },
3
m
m
which implies
” ?
˘ı
n `
}T h}2 ď 6 14 N `
}T }1Ñ2 }T : }2Ñ8 p|Ω| ´ |Ω1 |q ` 1 }T }.
m

32

In the case when T ˚ T “ In , T ek e˚k T : s correspond to orthogonal projections onto mutually orthogonal
˚ S T : repeat at most R times. Then the
one-dimensional subspaces. Recall that the summands in T SΩ
Ω
˚ S T : ´ T S ˚ S 1 T : repeat at most R ´ 1 times. Therefore, we get a sharper estimate
summands in T SΩ
Ω
Ω1 Ω

than that in (76) given by
˚
˚
˚
˚
:
˚
}T pSΩ
SΩ ´ SΩ
1 SΩ1 qh}2 ď }T pSΩ SΩ ´ SΩ1 SΩ1 qT }}T SΩ1 SΩ1 h}2
˚
ď pR ´ 1q}T SΩ
1 SΩ1 h}2 .

(78)

This completes the proof for the second claim.
VIII. N UMERICAL R ESULTS
In this section, we conduct numerical experiments of solving (5) and (27), with partial Fourier measurements and several different sparsifying transforms. We compare different sampling schemes in MonteCarlo experiments, and observe that the variable density sampling schemes proposed in (15) and (32)
yield superior recovery results in terms of success rate.
The optimization problems (5) and (27) are solved using Alternating Direction Method of Multipliers
(ADMM) [4]. For example, for T “ ΦΨ˚ P Cnˆn , (5) is rewritten in the following form with two linear
constraints, and solved by ADMM with two additional terms in the augmented Lagrangian.
minimize
n
yPC

}y}1

subject to T g “ y,
SΩ g “ SΩ x.

In all experiments, the ADMM algorithm runs for 1,000 iterations.
A. 1D Signals
For 1D signals, we use the DFT Ψ P Cnˆn , and two sparsifying transforms ΨTV,n , ΨW,n,` P Cnˆn ,
denoting the finite difference operator and the discrete Haar wavelet [20] at level `, respectively. For
the finite difference operator ΨTV,n , we use the two-step scheme in Section V-B. In Step 2), we either
use the uniform density according to Corollary V.3 (see Fig. 2a), or the distribution (15) restricted to
t2, 3, . . . , nu computed from the other transform ΨW,n,` (see Fig. 2b). For the discrete Haar wavelet
ΨW,n,` , we test two distributions on rns – the uniform distribution (see Fig. 2a) and the variable density

distribution (15) (see Fig. 2b).
In the numerical experiments, we choose n “ 512, and synthesize signals f at sparsity levels s “
16, 32, 48, . . . , 128 with respect to the above two sparsifying transforms. We use the Haar wavelet at

level ` “ 6. To make the experiments more realistic, we synthesize the sparse signals by thresholding a
real-world signal (see Fig. 1a) in the transform domains. For the discrete Haar wavelet, we analyze the
signal using ΨW,n,` , zero out small coefficients to achieve a certain sparsity level, and synthesize the
signal using Ψ˚W,n,` . Due to the non-injectivity of the finite difference operator, we replace the last row
of ΨTV,n by r1, 1, . . . , 1sJ P Cn in the signal analysis and synthesis steps.

33

For every sampling scheme, we repeat the experiment for m “ 16, 32, 48, . . . , 512. We run 50 MonteCarlo experiments for each setting. An instance is declared a success if the following reconstruction
signal-to-noise ratio (RSNR) of the solution ĝ to (5) exceeds 60dB.
˙
ˆ
}ĝ ´ x}2
.
RSNR “ ´20 log10
}x}2
The success rate is computed for every pair ps, mq and shown in Fig. 2c – 2f.
For signal recovery using the Haar wavelet, the variable density sampling scheme (15) yields higher
success rate than the uniform density sampling scheme (see Fig. 2c and 2d). For 1D TV, the density
(15) computed using 1D TV, which is uniform, yields higher success rate than that computed from the
Haar wavelet (see Fig. 2e and 2f). These experiments show that one can recover sparse signals more
successfully using the sampling density (15) computed from the specific sparsifying transform used in
the recovery, which is adaptive to local incoherence between the transform and the measurement. It is
commonly believed among practitioners that sampling more densely in the low frequency region, where
the energy of a natural signal is concentrated, always provides a better reconstruction. However, that
turns out not be the case when one cares about perfect recovery of exactly sparse signals in a certain
transform domain from noise-free measurements.

0.2
0.1
0

0

100

200

300

400

500

(a)

(b)

Fig. 1: Signals used in the experiments. (a) A line in an MRI brain image, used to synthesize 1D sparse
signals. We only plot the absolute value of this complex signal. (b) The modified Shepp-Logan phantom
(256 ˆ 256), used for 2D signal recovery.

B. 2D Signals
We also run numerical experiments on a 2D signal, the modified Shepp-Logan phantom (see Fig. 1b).
We minimize the anisotropic and isotropic 2D total variations, which correspond to solving (5) and (27)
for the 2D finite difference operator ΦTV,n1 ,n2 .
For the two types of total variations, we use the two-step scheme in Section V-B. In Step 2), we use
the densities in (15) and (32) for anisotropic and isotropic total variations, respectively. As a comparison,
we use the variable density proposed by Krahmer and Ward [26], which is (15) computed with the 2D
separable Haar wavelet ΨW,n2 ,log2 n2 b ΨW,n1 ,log2 n1 .

34

(a)

(b)

1

1

0.75

0.75

0.5

0.5

0.25

0.25

0.125

0.25

0.375

0.5

0.125

(c)
1

1

0.75

0.75

0.5

0.5

0.25

0.25

0.125

0.25

0.25

0.375

0.5

0.375

0.5

(d)

0.375

0.5

0.125

(e)

0.25

(f)

Fig. 2: Sampling densities and empirical success rate for 1D signal recovery. (a) (b) The sampling density
(15) computed from 1D TV (uniform), and from the Haar wavelet. (c) – (f) The success rate plots. The xaxis represents the sparsity level s{n, and the y -axis represents the sub-sampling ratio m{n. The empirical
success rate is represented by the grayscale value (white for 1 and black for 0). (c) (d) Recovery using
the Haar wavelet, under sampling density (a) and (b), respectively. (e) (f) Recovery using 1D TV, under
sampling density (a) and (b), respectively, both restricted to t2, 3, . . . , nu.

We use a phantom of size n “ n1 ˆ n2 “ 256 ˆ 256, and repeat the experiments for m “
n{32, n{16, 3n{32, . . . , n{4. We run 50 Monte-Carlo experiments for each setting, and compute the

success rate for every chioce of m, as shown in Fig. 3d and 3e.
For both anisotropic TV minimization (5) and isotropic TV minimization (27), the success rates using
sampling density computed from TV are higher than those using sampling density computed from
separable Haar wavelet. Although the performances of two sampling schemes are relatively close for
anisotropic TV minimization (see Fig. 3d), the advantage of the density computed from TV over that
computed from wavelet is more pronounced for isotropic TV minimization (see Fig. 3e). Contrary to

35

(a)

(b)

(c)

1
0.8
0.6
0.4
0.2
0
1/321/163/32 1/8 5/323/167/32 1/4

1
0.8
0.6
0.4
0.2
0
1/321/163/32 1/8 5/323/167/32 1/4

(d)

(e)

Fig. 3: Sampling density and empirical success rate for 2D signal recovery. (a) – (c) The sampling
densities on a 256 ˆ 256 grid, computed from 2D anisotropic TV, 2D isotropic TV (uniform), and 2D
separable Haar wavelet. Grayscale values represent samping density in log scale. (d) (e) The empirical
success rate for 2D signal recovery using anisotropic TV minimization and isotropic TV minimization,
respectively. The x-axis represents the sub-sampling ratio m{n, and the y -axis represents the empirical
success rate. Within the same plot, different curves represent the results using different sampling schemes.
The solid red curves in (d) and (e) represent results using sampling density (a) and (b), respectively. The
dashed blue curves represent results using sampling density (c) computed from wavelet.

common belief, sampling low frequencies more densely does not always lead to superior recovery. We
suggest using sampling densities (15) and (32) tailored to the specific sparsifying transform and the
measurement operator.
IX. C ONCLUSION
In this paper, we established a unified theory for recovery of sparse signals in a transform domain. Our
theory guaranteed robust recovery from noisy measurements by convex programming and apply without
relying on a particular choice of measurement and sparsifying transforms. We quantified the sufficient
sampling rate using functions of the two transforms, and this result identifies a class of measurement and
sparsity models enabling recovery at a near optimal sampling rate. We also proposed a variable sampling
density designed with incoherence parameters of the two transforms, which provided recovery guarantee
at a lower sampling rate than previous works in various scenarios. Furthermore, we extended the result
to the group-sparsity models so that it also applies to the popular isotropic total variation minimization.
In particular, for the partial Fourier recovery of sparse signals over a circulant transform, our theory
suggests a uniformly random sampling or its variation. Our numerical results showed that our variable

36

density random sampling strategy outperforms other known sampling strategies in various scenarios. This
suggests that our new theory is indeed universally useful.
ACKNOWLEDGEMENT
The authors thank referees for their valuable comments and suggestions.
A PPENDIX A
B ERNSTEIN INEQUALITIES
Theorem A.1 (Matrix Bernstein Inequality [38]). Let tXj u P Cdˆd be a finite sequence of independent
random matrices. Suppose that EXj “ 0 and }Xj } ď B almost surely for all j and
› ›
›¸
˜›
›ÿ
› ›ÿ
›
›
› ›
›
max › EXj Xj˚ › , › EXj˚ Xj › ď σ 2 .
›
› ›
›
j
j
Then for all t ě 0,

›
˜›
¸
˙
ˆ
›ÿ ›
´t2 {2
›
›
.
P › Xj › ě t ď 2d exp
›
›
σ 2 ` Bt{3
j

Theorem A.2 (Vector Bernstein Inequality [15]). Let tvj u P Cd be a finite sequence of independent
ř
random vectors. Suppose that Evj “ 0 and }vj }2 ď B almost surely for all j and E j }vj }22 ď σ 2 .
Then for all 0 ď t ď σ 2 {B ,
¨›
˛
›
ˆ
˙
›ÿ ›
t2
1
›
›
˝
‚
P › vj › ě t ď exp ´ 2 `
.
›
›
8σ
4
j
2

A PPENDIX B
P ROOF OF L EMMA VI.3
Define
Xj :“ ΠJ pnT eωj e˚ωj T : ´ T T : qΠJ ,

@j P rms.

Then, Xj satisfies EXj “ 0 and }Xj } ď µs for all j . Since
Xj˚ Xj “ n2 ΠJ Treωj e˚ωj T ˚ ΠJ T eωj e˚ωj T : ΠJ
´ nΠJ Treωj e˚ωj T ˚ ΠJ T T : ΠJ
´ nΠJ T T : ΠJ T eωj e˚ωj T : ΠJ
` ΠJ T T : ΠJ T T : ΠJ ,

37

it follows that
EXj˚ Xj “ En2 ΠJ Treωj e˚ωj T ˚ ΠJ T eωj e˚ωj T : ΠJ ´ ΠJ T T : ΠJ T T : ΠJ
ď En2 e˚ωj T ˚ ΠJ T eωj ΠJ Treωj e˚ωj T : ΠJ
“ En2 }γ 1{2 ΠJ T eωj }22 γ ´1 ΠJ Treωj e˚ωj T : ΠJ
ď Enµsγ ´1 ΠJ Treωj e˚ωj T : ΠJ
“ µsγ ´1 ΠJ TrT : ΠJ .

By symmetry, we also have
EXj Xj˚ ď µsγΠJ T T ˚ ΠJ .
Therefore,
›
˜›
m
›ÿ
›
›
˚›
max ›
EXj Xj › ,
›
›
j“1

›
›¸
m
›ÿ
›
mµs
›
›
˚
EXj Xj › ď mµs maxp}γ ´1 TrT : }, }γT T ˚ }q ď
.
›
˚T ´ I }
›
›
1
´
}γT
n
j“1

Applying the above results to Theorem A.1 with t “ mδ completes the proof.
A PPENDIX C
P ROOF OF L EMMA VI.4
Define
vj :“ ΠJ pnT eωj e˚ωj T : ´ T T : qΠJ q,

@j P rms.

Then, vj satisfies Evj “ 0 and
}vj }2 ď }ΠJ nT eωj e˚ωj T : ΠJ q}2 ` }ΠJ T T : ΠJ q}2
?
?
ď p}γ 1{2 ΠJ nT eωj }2 }γ ´1{2 ΠJ nTreωj }2 ` 1q}ΠJ q}2
ď psµ ` 1q}ΠJ q}2 .

Furthermore,
E}vj }22 “ En2 q ˚ ΠJ Treωj e˚ωj T ˚ ΠJ T eωj e˚ωj T : ΠJ q ´ q ˚ ΠJ T T : ΠJ q
ď n}γ 1{2 ΠJ T eωj }22 Enγ ´1 q ˚ ΠJ Treωj e˚ωj T : ΠJ q
ď µsγ ´1 Enq ˚ ΠJ Treωj e˚ωj T : ΠJ q
“ µsγ ´1 q ˚ ΠJ TrT : ΠJ q
ď

µs}ΠJ q}22
,
1 ´ }γT ˚ T ´ In }

where the second inequality follows by the incoherence property. Applying the above results to Theorem A.2 completes the proof.

38

A PPENDIX D
P ROOF OF L EMMA VI.5
Let i P rnszJ be arbitrarily fixed. Define
wj :“ xei , pnT eωj e˚ωj T : ´ T T : qΠJ qy,

@j P rms.

Then, wj satisfies Ewj “ 0 and
|wj | ď |e˚j nT eωj e˚ωj T : ΠJ q| ` }T T : ΠJ q}8
?
?
ď p}γ 1{2 nT eωj }8 }γ ´1{2 nΠJ Treωj }2 ` 1q}ΠJ q}2
?
ď p sµ ` 1q}ΠJ q}2 .

Furthermore,
E|wj |2 “ En2 q ˚ ΠJ Treωj e˚ωj T ˚ ei e˚i T eωj e˚ωj T : ΠJ q ´ q ˚ ΠJ T T : ei e˚i T T : ΠJ q
ď n}γ 1{2 T eωj }28 γ ´1 Enq ˚ ΠJ Treωj e˚ωj T : ΠJ q
ď µγ ´1 q ˚ ΠJ TrT : ΠJ q
ď

µ}ΠJ q}22
.
1 ´ }γT ˚ T ´ In }

Applying the above results to Theorem A.1 gives
˙
ˆ
´ˇA ´ n
¯
Eˇ
¯
m
t2
ˇ
ˇ
˚
?
.
P ˇ ei ,
B ´ B ΠJ q ˇ ě t}ΠJ q}2 ď exp ´
¨
m Ω
2µ 1{p1 ´ }γT ˚ T ´ In }q ` st{3
Combine this for i P rN s with the union bound completes the proof.
A PPENDIX E
P ROOF OF L EMMA VI.6
Let i P rnszJ be arbitrarily fixed. Define
vj :“ ΠGi pnT eωj e˚ωj T : ´ T T : qΠGJ q,

@j P rms.

Then, vj satisfies Evj “ 0 and
}vj }2 ď }ΠGi nT eωj e˚ωj T : ΠGJ q}2 ` }ΠGi T T : ΠGJ q}2
?
?
ď p}γ 1{2 nΠGi T eωj }2 }γ ´1{2 nΠGJ Treωj }2 ` 1q}ΠGJ q}2
?
ď p sµG ` 1q}ΠGJ q}2 .

39

Furthermore,
Evj˚ vj “ En2 q ˚ ΠGJ Treωj e˚ωj T ˚ ΠGi T eωj e˚ωj T : ΠGJ q ´ q ˚ ΠGJ T T : ΠGi T T : ΠGJ q
ď n}γ 1{2 ΠGi T eωj }22 γ ´1 Enq ˚ ΠGJ Treωj e˚ωj T : ΠGJ q
ď µG γ ´1 q ˚ ΠGJ TrT : ΠGJ q
ď

µG }ΠGJ q}22
.
1 ´ }γT ˚ T ´ In }

Note that
vj vj˚ ď vj˚ vj IL ,

@j P rms.

Applying the above results to Theorem A.2 gives
˙
ˆ
›
´›
¯
´n
¯
t2
m
›
›
˚
?
.
B ´ B ΠGJ q › ě t}ΠGJ q}2 ď exp ´
¨
P ›ΠGi
m Ω
2µ 1{p1 ´ }γT ˚ T ´ In }q ` st{3
2
Combine this for i P rN s with the union bound completes the proof.
A PPENDIX F
P ROOF OF T HEOREM II.4
Theorem II.4 is analogous to [32, Theorem 3.1]. It has been shown that if T is of full row rank, then
the deviation of

n
˚
:
m T SΩ SΩ T

from T T : “ IN is small with high probability [32, Theorem 3.1]. On the

contrary, Theorem II.4 assumes that T is of full column rank and shows that the deviation of

n
˚
:
m T SΩ SΩ T

from T T : , which is not necessarily IN , is small with high probability.
The proof of Theorem II.4 is obtained from that of [32, Theorem 3.1] by replacing IN by T T : . For
example, the isotropy condition
n
˚
ET SΩ
SΩ T : “ IN
m

is replaced by
n
˚
ET SΩ
SΩ T : “ T T : .
m

For a matrix M P CN ˆN , the term θs pM q, previously defined by in [32]
θs pM q :“ max }ΠJrpM ´ IN qΠJr}
r
|J|ďs

is replaced by
θs pM q :“ max }ΠJrpM ´ T T : qΠJr}
r
|J|ďs

Clearly, T T : “ IN if T has full row rank. However, in the hypothesis of Theorem II.4, T has full
column rank and T T : may be rank deficient. Since the modifications are rather straightforward, we omit
the details of the proof and refer them to [32, Appendix E].

40

By modifying [32, Theorem 3.1] and its proof as shown above, (10) is implied by (12) and
m ě C1 δ ´2 KT µs log2 s log N log m,

where the factor KT is given by
$˜
¸ ,2
¸1{2 ˜
› 1{2 .
›
&
›
›
›
›
` 2 ` max ›ΠJrpγ ´1 TrT : ´ T T : qΠJr›
2 ` max ›ΠJrpγT T ˚ ´ T T : qΠJr›
KT “
%
r
r
|J|ďs
|J|ďs
¸
˜
ď 4 ` 2 max max }Π rpγT T ˚ ´ T T : qΠ r}, max }Π rpγ ´1 TrT : ´ T T : qΠ r}
r
|J|ďs

J

J

r
|J|ďs

J

J

´
¯
ď 4 ` 2 max }γT T ˚ ´ T T : }, }γ ´1 TrT : ´ T T : }
´
¯
“ 4 ` 2 max }γT ˚ T ´ In }, }γ ´1 T : Tr ´ In } .

Finally, we verify that
}γ ´1 T : Tr ´ In } ď

1
,
}γT ˚ T ´ In }

where the upper bound dominates }γT ˚ T ´ In }. This completes the proof.
R EFERENCES
[1] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, 2006.
[2] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete
frequency information,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, 2006.
[3] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM J. Imaging
Sci., vol. 2, no. 1, pp. 183–202, 2009.
[4] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating
direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011.
[5] D. Needell and J. A. Tropp, “CoSaMP: Iterative signal recovery from incomplete and inaccurate samples,” Appl. Comput.
Harmon. Anal., vol. 26, no. 3, pp. 301–321, 2009.
[6] W. Dai and O. Milenkovic, “Subspace pursuit for compressive sensing signal reconstruction,” IEEE Trans. Inf. Theory,
vol. 55, no. 5, pp. 2230–2249, May 2009.
[7] T. Blumensath and M. E. Davies, “Iterative hard thresholding for compressed sensing,” Appl. Comput. Harmon. Anal.,
vol. 27, no. 3, pp. 265–274, 2009.
[8] S. Foucart, “Hard thresholding pursuit: An algorithm for compressive sensing,” SIAM J. Numer. Anal., vol. 49, no. 6, pp.
2543–2563, 2011.
[9] E. J. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215,
2005.
[10] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, “The convex geometry of linear inverse problems,” Found.
Comput. Math., vol. 12, no. 6, pp. 805–849, 2012.
[11] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: Phase transitions in convex programs with
random data,” Information and Inference, vol. 3, no. 3, p. 224294, 2014.
[12] Y. Bresler, M. Gastpar, and R. Venkataramani, “Image compression on-the-fly by universal sampling in Fourier imaging
systems,” in Proc. 1999 IEEE Information Theory Workshop on Detection, Estimation, Classification, and Imaging, Santa
Fe, NM, Feb. 1999, p. 48.

41

[13] E. J. Candes and T. Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies?” IEEE
Trans. Inf. Theory, vol. 52, no. 12, pp. 5406–5425, 2006.
[14] M. Rudelson and R. Vershynin, “On sparse reconstruction from Fourier and Gaussian measurements,” Comm. Pure Appl.
Math., vol. 61, no. 8, pp. 1025–1045, 2008.
[15] E. J. Candes and Y. Plan, “A probabilistic and RIPless theory of compressed sensing,” IEEE Trans. Inf. Theory, vol. 57,
no. 11, pp. 7235–7254, 2011.
[16] H. Rauhut, “Compressive sensing and structured random matrices,” in Theoretical Foundations and Numerical Methods
for Sparse Recovery, ser. Radon Series Comp. Appl. Math., M. Fornasier, Ed. Berlin: de Gruyter, 2010, vol. 9, pp. 1–92.
[17] E. J. Candes, Y. C. Eldar, D. Needell, and P. Randall, “Compressed sensing with coherent and redundant dictionaries,”
Appl. Comput. Harmon. Anal., vol. 31, no. 1, pp. 59–73, 2011.
[18] S. Nam, M. E. Davies, M. Elad, and R. Gribonval, “The cosparse analysis model and algorithms,” Appl. Comput. Harmon.
Anal., vol. 34, no. 1, pp. 30–56, 2013.
[19] R. Giryes, S. Nam, M. Elad, R. Gribonval, and M. E. Davies, “Greedy-like algorithms for the cosparse analysis model,”
Linear Algebra and its Applications, vol. 441, pp. 22–60, 2014.
[20] S. Mallat, A wavelet tour of signal processing: the sparse way.

Academic press, 2008.

[21] M. N. Do and M. Vetterli, “The contourlet transform: an efficient directional multiresolution image representation,” IEEE
Trans. Image Process., vol. 14, no. 12, pp. 2091–2106, 2005.
[22] J.-L. Starck, E. J. Candès, and D. L. Donoho, “The curvelet transform for image denoising,” IEEE Trans. Image Process.,
vol. 11, no. 6, pp. 670–684, 2002.
[23] M. Lustig, D. L. Donoho, J. M. Santos, and J. M. Pauly, “Compressed sensing MRI,” IEEE Signal Process. Mag., vol. 25,
no. 2, pp. 72–82, 2008.
[24] F. Krahmer and R. Ward, “New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property,”
SIAM J. Math. Anal., vol. 43, no. 3, pp. 1269–1281, 2011.
[25] D. Needell and R. Ward, “Stable image reconstruction using total variation minimization,” SIAM J. Imaging Sci., vol. 6,
no. 2, pp. 1035–1058, 2013.
[26] F. Krahmer and R. Ward, “Stable and robust sampling strategies for compressive imaging,” IEEE Trans. Image Process.,
vol. 23, no. 2, pp. 612–622, 2014.
[27] M. Kabanava, H. Rauhut, and H. Zhang, “Robust analysis `1 -recovery from Gaussian measurements and total variation
minimization,” European Journal of Applied Mathematics, vol. 26, no. 06, pp. 917–929, 2015.
[28] J.-F. Cai and W. Xu, “Guarantees of total variation minimization for signal recovery,” Information and Inference, vol. 4,
no. 4, pp. 328–353, 2015.
[29] M. Kabanava and H. Rauhut, “Analysis `1 -recovery with frames and Gaussian measurements,” Acta Applicandae
Mathematicae, vol. 140, no. 1, pp. 173–195, 2015.
[30] Y. Chen and Y. Chi, “Robust spectral compressed sensing via structured matrix completion,” IEEE Trans. Inf. Theory,
vol. 60, no. 10, pp. 6576–6601, 2014.
[31] D. Gross, “Recovering low-rank matrices from few coefficients in any basis,” IEEE Trans. Inf. Theory, vol. 57, no. 3, pp.
1548–1566, 2011.
[32] K. Lee, Y. Bresler, and M. Junge, “Oblique pursuits for compressed sensing,” IEEE Trans. Inf. Theory, vol. 59, no. 9, pp.
6111–6141, 2013.
[33] J. Huang and T. Zhang, “The benefit of group sparsity,” Ann. Stat., vol. 38, no. 4, pp. 1978–2004, 2010.
[34] L. Pfister and Y. Bresler, “Learning sparsifying filter banks,” in SPIE Optical Engineering+ Applications.

International

Society for Optics and Photonics, 2015, pp. 959 703–959 703.
[35] J. C. Ye, J. M. Kim, K. H. Jin, and K. Lee, “Compressive sampling using annihilating filter-based low-rank interpolation,”
IEEE Transactions on Information Theory, 2016 (in press).
[36] M. Rudelson and S. Zhou, “Reconstruction from anisotropic random measurements,” IEEE Trans. Inf. Theory, vol. 59,
no. 6, pp. 3434–3447, 2013.

42

[37] R. Kueng and D. Gross, “RIPless compressed sensing from anisotropic measurements,” Linear Algebra Appl., vol. 441,
pp. 110–123, 2014.
[38] J. A. Tropp, “User-friendly tail bounds for sums of random matrices,” Found. Comput. Math., vol. 12, no. 4, pp. 389–434,
2012.

