1

Limits on Sparse Data Acquisition:
RIC Analysis of Finite Gaussian Matrices
Ahmed Elzanaty, Student Member, IEEE,

arXiv:1802.03195v1 [] 9 Feb 2018

Andrea Giorgetti, Senior Member, IEEE, and Marco Chiani, Fellow, IEEE

Abstract
One of the key issues in the acquisition of sparse data by means of compressed sensing (CS) is
the design of the measurement matrix. Gaussian matrices have been proven to be informationtheoretically optimal in terms of minimizing the required number of measurements for sparse
recovery. In this paper we provide a new approach for the analysis of the restricted isometry constant
(RIC) of finite dimensional Gaussian measurement matrices. The proposed method relies on the exact
distributions of the extreme eigenvalues for Wishart matrices. First, we derive the probability that
the restricted isometry property is satisfied for a given sufficient recovery condition on the RIC,
and propose a probabilistic framework to study both the symmetric and asymmetric RICs. Then,
we analyze the recovery of compressible signals in noise through the statistical characterization
of stability and robustness. The presented framework determines limits on various sparse recovery
algorithms for finite size problems. In particular, it provides a tight lower bound on the maximum
sparsity order of the acquired data allowing signal recovery with a given target probability. Also,
we derive simple approximations for the RICs based on the Tracy-Widom distribution.

Index Terms
Data acquisition, compressed sensing, restricted isometry property, Wishart matrices, Gaussian
measurement matrices, sparse reconstruction, robust recovery.

I. I NTRODUCTION
Compressed sensing (CS) is an acquisition technique for efficiently recovering a signal
from a small set of linear measurements, provided that the sensed data is sparse, i.e., the
This work was supported in part by the European Commission under the EuroCPS project and the EU-METALIC II
project, within the framework of Erasmus Mundus Action 2. This paper was presented in part at the IEEE Statistical Signal
Processing Work. (SSP), Palma de Mallorca, Spain, June 2016.
The authors are with the DEI, University of Bologna, Via Venezia 52, 47521 Cesena, ITALY (e-mail: {ahmed.elzanaty,
andrea.giorgetti, marco.chiani}@unibo.it).

February 12, 2018

DRAFT

2

number of its non-zero elements, s, is much less than its dimension n. If properly chosen,
the number of measurements, m, can be much smaller than the signal dimension [1]–[7].
CS based techniques have been exploited to provide efficient solutions for several problems
in signal processing and communication, e.g., source and channel coding, cryptography,
random access, radar, channel estimation, and sub-Nyquist data acquisition [8]–[16]. The
usability of such applications depends on the maximum sparsity order s such that recovery
is guaranteed with high probability for given m and n.
The three main possible approaches to find the maximum sparsity order s guaranteeing
recovery of all sparse vectors are based on the restricted isometry property (RIP) analysis,
geometric methods, and coherence analysis. The RIP tells how well a linear transformation
preserves distances between sparse vectors, and is quantified by the so-called restricted
isometry constant (RIC) [1]. In general, the smaller the RIC, the closer the transformation
to an isometry (a precise definition of the RIC is given later). Geometric based methods are
useful for the recovery analysis of exactly sparse signals via ℓ1 -minimization in the noiseless
case [17]–[20]. Sparse reconstruction can also be studied looking at the coherence of the
measurement matrix. However, the resulting bounds are too pessimistic compared to RIPbased bounds [21, eq. (6.9) and eq. (6.14)]. This significant gap justifies preferring the RIP
based analysis, whenever bounding the RIC is feasible. Furthermore, non-uniform recovery
guarantees, like those based on Gaussian widths, provide tight bounds for the reconstruction
of a fixed sparse vector, in contrast to the RIP method, which considers the recovery of all
sparse vectors (uniform recovery) [21], [22].
Moreover, the RIP theory is more general compared to the geometric approach, as it also
considers the stability for compressible signals and the robustness to noise, under different
measurement matrices, for a wider range of sparse recovery algorithms. In fact, sufficient
conditions for exact recovery have been obtained for several algorithms in terms of the RIC
(see, e.g., [1], [23]–[28] for ℓ1 -minimization, [29], [30] for iterative hard thresholding (IHT),
and [31]–[34] for greedy algorithms).
It has been shown by using information-theoretic methods that Gaussian random matrices
with independent, identically distributed (i.i.d.) entries are optimal in terms of minimizing
the number of measurements required for recovery [35]. Hence, precisely analyzing the RIP
of such matrices is important. In fact, Gaussian matrices have been proved to satisfy the
RIP with overwhelming probability [1], [3]. The two main tools adopted for the proof are
the concentration of measure inequality for the distribution of the extreme eigenvalues of
a Wishart matrix, and the union bound which accounts for all possible signal supports.

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

3

However, if the aim is to quantify the maximal allowable sparsity order s for a given number
of measurements, the use of the concentration inequalities leads to overly pessimistic results.
In this regard, in [36]–[38] an improved analysis was presented, by bounding the asymptotic
behavior of the distributions given in [39] for the extreme eigenvalues of a Wishart matrix
instead of the concentration inequalities. Explicit bounds for the RIC have been obtained in
some specific asymptotic regions [38], but no bounds are known in the general non-asymptotic
setting. In fact, for finite measurement matrices the asymptotic analysis of the eigenvalues
in [36]–[38] gives approximations of the true distributions; therefore, they cannot provide
guaranteed bounds for a particular problem dimension (s, m, n).
This paper provides an accurate statistical analysis of the RIC for finite dimensional
Gaussian measurement matrices, supporting the design of real CS applications (involving
always finite size problems), with guaranteed recovery probability. In particular, we calculate
the tightest, to our knowledge, lower bound on the probability of satisfying the RIP for an
arbitrary condition on the RIC. For a specified number of measurements, the maximal sparsity
order can then be found such that perfect recovery is feasible for all s-sparse vectors, i.e.,
the matrix satisfies the RIP, considering, on a random draw of the measurement matrix, a
target probability 1 − ǫ of successful recovery. Differently, the usually adopted asymptotic
setting considers that this probability tends to 1 (overwhelming probability).
To get better estimates on the maximal sparsity order, tight lower bounds on the cumulative
distribution functions (CDFs) of the asymmetric RICs (ARICs) are derived, based on the exact
probability that the extreme singular values of a Gaussian submatrix are within a range.
Hence, starting from the derived CDFs, we can find thresholds, below which the ARICs
lie with a predefined probability. These percentiles allow to calculate a lower bound on the
maximal recoverable signal sparsity order, using several reconstruction methods, such as ℓ1 minimization, greedy, and IHT algorithms. The new analysis is used in conjunction with the
recovery conditions relaxed to asymmetric boundaries, as suggested in [36], to prove exact
recovery for signals with larger sparsity orders. In this regard, we relax the symmetric RIC
based condition in [28] to a weaker asymmetric one. Additionally, we provide approximations
for the RIC CDFs based on the Tracy-Widom (TW) distribution, along with convergence
investigation. In comparison with previous literature, the proposed analysis gives, for finite
dimensional problems, a better estimation of the signal sparsity allowing guaranteed recovery.
The contributions of this paper can be summarized as follows:
•

Accurate symmetric and asymmetric RIC analysis for finite dimensional problems, accounting for the exact distribution of finite Gaussian matrices (differently from previous

February 12, 2018

DRAFT

4

methods based on asymptotic behavior of the distributions or loose concentration of
measure bounds).
•

Limits on compressive data acquisition in terms of the maximum achievable sparsity
order guaranteeing arbitrary target reconstruction probability (instead of the common
overwhelming probability approach) via various recovery algorithms.

•

Accurate study for stable and robust recovery of compressible signals with tight bounds
on the reconstruction error.

•

Simple approximations for the RICs based on the TW laws.

Throughout this paper, we indicate with det(·) the determinant of a matrix, with card(·)
P
1
the cardinality of a set, with k · kq = ( ni=1 |xi |q ) q the ℓq norm of an n-dimensional vector,
Ry
with k · k the ℓ2 norm, with Γ(·) the gamma function, with γ (a; x, y) = x ta−1 e−t dt the
1
γ(a; 0, x) the regularized lower
generalized incomplete gamma function, with P (a, x) = Γ(a)
R
y
1
ta−1 e−t dt = P (a, y) − P (a, x) the
incomplete gamma function, with P (a; x, y) = Γ(a)
x

generalized regularized incomplete gamma function, with N(µ, σ 2 ) the Gaussian distribution
with mean µ and variance σ 2 .

II. M ATHEMATICAL BACKGROUND
Compressed sensing allows recovering a signal from a small number of linear measurements, under some constraints on both the sensed signal and the sensing system. More
precisely, assume that we have
y = Ax

(1)

where y ∈ Rm and A ∈ Rm×n are known, the number of equations is m < n, and x ∈ Rn is
the unknown. Since m < n, we can think of y as a compressed version of x. Without other
constraints, the system is underdetermined, and there are infinitely many distinct solutions of
(1). If we assume that at most s < m elements of x are non-zero (i.e., the vector is s-sparse),
then there is a unique solution (the right one) to (1), provided that all possible submatrices
consisting of 2s columns of A are maximum rank. The solution can be found by solving the
following ℓ0 -minimization [1]
x̂ = arg min kxk0 subject to y = Ax

(2)

where kxk0 is the number of the non-zero elements of x. However, even when the maximum
rank condition is satisfied, the solution of (2) is computationally prohibitive for dimensions of

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

5

practical interest. A much easier problem is to find the ℓ1 -minimization solution. It is proved
in [1], under some conditions on A, that the solution provided by the ℓ1 -minimization
x̂ = arg min kxk1 subject to y = Ax

(3)

is the same as that of (2). The conditions on A are given in term of the RIC.
Definition 1 (The RIC [1]). The RIC of order s of A, δs (A), is the smallest constant, larger
than zero, such that the inequalities
kAS ck2
1 − δs (A) ≤
≤ 1 + δs (A)
(4)
kck2
are simultaneously satisfied for every c ∈ Rs and every m × s submatrix AS of A with

columns indexed by S ⊂ Ω , {1, 2, ..., n} with card(S) = s. Under this condition, the
matrix A is said to satisfy the RIP of order s with constant δs (A).
Specifically, the importance of the RIP in CS comes from the possibility to use the
computationally feasible ℓ1 -minimization instead of the impractical ℓ0 one, under some
constraints on the RIC. For example, it was shown that the ℓ1 and the ℓ0 solutions are
coincident for every s-sparse vectors x if δs (A) < δ with δ = 1/3 [28].
The next question is how to design a matrix A with a prescribed RIC. One possible way
to design A consists simply in randomly generating its entries according to some statistical
distribution. In this case, for a given n, s and δ, the target is to find a way to generate A
such that the probability P {δs (A) < δ} is close to one. An optimal choice is to build the
measurement matrix A with i.i.d. entries ai,j ∼ N(0, 1/m) [1], [35]. Then, in order to find
the number of measurements m needed, we start by using the Rayleigh quotient inequality
for a fixed S

kAS ck2
≤ λmax (W)
λmin (W) ≤
kck2

(5)

where W = ATS AS , and λmin (W) and λmax (W) are its minimum and maximum eigenvalues,
respectively. Considering that the inequalities in (4) should be satisfied for all the s-column
submatrices of A, the RIC constant can be written as




δs (A) = max 1−min λmin (W), max λmax (W)−1 .
S⊂Ω
 S⊂Ω

card(S)=s

(6)

card(S)=s

Hence, the probability that the measurement matrix satisfies the RIP with a RIC at most δ,
denoted as β(δ) , P {δs (A) ≤ δ}, is represented by




β(δ)=P min λmin (W)≥ 1−δ,max λmax (W) ≤ 1+δ .
S⊂Ω
 S⊂Ω

card(S)=s

February 12, 2018

(7)

card(S)=s

DRAFT

6

The union bound gives a lower bound for the probability of satisfying the RIP as
 
n
(1 − Psw (δ))
(8)
β(δ) ≥ 1 −
s

where ns is the binomial coefficient and Psw (δ) is the probability that AS is well conditioned
defined as:

Psw (δ) , P {1 − δ ≤ λmin (W), λmax(W) ≤ 1 + δ} .

(9)

The probability Psw (δ) is of fundamental importance, since it determines the performance
of CS. In the next section, a approach for exactly calculating (9) for Gaussian matrices is
proposed.

III. E IGENVALUES S TATISTICS
In this section, we start by recalling the known concentration inequality based bound on
1 −Psw (δ), which is the approach used in [1], [2]. Then, an alternative method to find Psw (δ)
for Gaussian measurement matrices are provided. The proposed technique relies on the exact
probability that the eigenvalues of W are within a predefined interval.

A. Eigenvalues Statistics Based on the Concentration Inequality
Deviation bounds for the largest and the smallest eigenvalues of the Wishart matrix W
are obtained using the concentration of measure inequality [1], [2], as
P

np

P

np

λmax (W) ≥ 1 +

o
2
s/m + o(1) + t ≤ e−mt /2

(10)

o
2
s/m + o(1) − t ≤ e−mt /2

(11)

p

and
λmin (W) ≤ 1 −

p

where t > 0 and o(1) is a small term tending to zero as m increases, which will be neglected
in the following. Using the inequality P {Ac B c } ≥ 1 − P {A} − P {B} where A, B are

arbitrary events, and Ac , B c are their complements, i.e., the union bound, we get


√
+ 2
√
− 21 m (−1− s/m+ 1+δ)

Psw (δ) ≥ 1 − e



√
+ 2
√
− 12 m (1− s/m− 1−δ)

−e

(12)

where (x)+ = max{0, x}. We will see later that this bound, which we use as a benchmark,
is far from the exact probability.

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

7

B. Exact Eigenvalues Statistics
We propose a method to compute exactly the probability that a Wishart matrix is well
conditioned, i.e, its eigenvalues are within a predefined limit. The method is based on the
following recent result [40].
Theorem 1. The probability that all non-zero eigenvalues of the real Wishart matrix M =
GTS GS , where GS is m × s matrix with entries gi,j ∼ N(0, 1), are within the interval
[a, b] ⊂ [0, ∞) is
ψms (a, b) = P {a ≤ λmin (M), λmax (M) ≤ b}
p
= K ′ det (Q(a, b))

with the constant

(13)

s

Y
π s /2
Γ (α + ℓ)
2αs+s(s+1)/2
K = s m/2
2
Γs (m/2)Γs (s/2)
2

′

ℓ=1

where Γs (a) , π

Qs
s(s−1)/4

i=1

Γ(a − (i − 1)/2), and α =

m−s−1
.
2

In (13), when s is even the

elements of the s × s skew-symmetric matrix Q(a, b) are
 

 

Z b/2

b
a
a b
2
qi,j = P αj ,
+ P αj ,
P αi ; ,
−
xα+i−1 e−x P (αj , x) dx (14)
2
2
2 2
Γ(αi ) a/2

for i, j = 1, . . . , s, where αℓ = α + ℓ. When s is odd, the elements of the (s + 1) × (s + 1)
skew-symmetric matrix Q(a, b) are as in (14), with the additional elements


a b
i = 1, . . . , s
qi,s+1 = P αi ; ,
2 2
qs+1,j = −qj,s+1
j = 1, . . . , s

(15)

qs+1,s+1 = 0 .
Moreover, the elements qi,j can be computed iteratively, without numerical integration or
series expansion [40, Algorithm 1].
Considering that in our case the entries of AS are distributed as N(0, 1/m), the exact
probability that AS is well conditioned is calculated from Theorem 1 as
Psw (δ) = P {λmin(W) ≥ 1 − δ, λmax (W) ≤ 1 + δ}
= ψms (m(1 − δ), m(1 + δ))

(16)

where ψms (a, b) can now be computed exactly. The exact expression (16) is computationally
easy for moderate matrix dimensions (we used it up to m = 1 · 105 and s = 150).
February 12, 2018

DRAFT

8

PSfrag replacements

λ∗min (m, s, η), λ∗max (m, s, η)

3

2

1

m = 400
m = 300
m = 200

0
0.1

0.2

0.3

0.4

s/m

Fig. 1. The asymmetric extreme eigenvalues thresholds of the Wishart matrix W as a function of s/m, for η = 10−10 . The
lower threshold λ∗min (m, s, η) and the upper threshold λ∗max (m, s, η) are represented by dashed and solid lines, respectively.

C. Asymmetric Nature of the Extreme Eigenvalues
Clearly, the RIC in (6) depends on the deviation of the extreme eigenvalues from unity. It
has been shown that the smallest and the largest eigenvalues of Wishart matrices asymptotically deviate from 1 [36]. Hence, the symmetric RIC can not efficiently describe the RIP of
Gaussian matrices. Now, it is essential to illustrate whether such asymmetric behavior is still
valid for finite measurement matrices. In this regard, we proposed to find the two percentiles
λ∗min (m, s, η) and λ∗max (m, s, η) for the extreme eigenvalues of W, such that
P {λmin (W) ≤ λ∗min (m, s, η)} = P {λmax (W) ≥ λ∗max (m, s, η)} = η .
In fact, such percentiles can be calculated form the exact eigenvalues distribution in Theorem
1 as
−1
−1
λ∗min (m, s, η) = ψmin
(η), λ∗max (m, s, η) = ψmax
(η)

(17)

−1
−1
where ψmin
(η) and ψmax
(η) are the inverse of ψms (0, m x) and ψms (m x, ∞), respectively.

In Fig. 1 we report the thresholds λ∗min(m, s, η) and λ∗max (m, s, η) as a function of s/m,
for some finite values of m and a fixed exceeding probability η = 10−10 . We can see that
they asymmetrically deviate from unity, as already observed for asymptotic large matrices

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

9

in [36]. Additionally, since for small values of m the deviation of the extreme eigenvalues
from unity is more significant, i.e., the RIC should be larger, the asymptotic tail behavior of
the eigenvalues distributions in [36]–[38] cannot be used for upper bounding the RICs in the
finite case.
Definition 2 (ARIC [24], [36]). The lower RIC (LRIC) of order s of A, δ s (A), is defined
as the smallest constant larger than zero that satisfies
1 − δ s (A) ≤

kAS ck2
kck2

∀ c ∈ Rs ,∀ S ⊂ Ω : card(S) = s

(18)

and the upper RIC (URIC) of order s of A, δ s (A), is defined as the smallest constant larger
than zero that satisfies
kAS ck2
≤ 1 + δ s (A) ∀ c ∈ Rs ,∀ S ⊂ Ω : card(S) = s.
kck2

(19)

Clearly, the relation with the symmetric RIC is δs (A) = max{δ s (A), δs (A)}. Moreover,
from Definition 2 and (5), we can represent the ARICs as
δ s (A) = 1 −

min λmin (W)

S⊂Ω
card(S)=s

δ s (A) = max λmax (W) − 1.
S⊂Ω
card(S)=s

IV. S YMMETRIC

AND

(20)
(21)

A SYMMETRIC RIC S

The symmetric and asymmetric RICs of a Gaussian matrix can be seen as functions of
the extreme eigenvalues of Wishart matrices as in (20) and (21), and hence are themselves
random variables (r.v.s). In this section, we derive at first lower bounds on the probability of
satisfying RIP for finite dimensional Gaussian random matrices using the exact eigenvalues
distribution, and then a lower bound on the RIC. Additionally, the CDFs of the ARICs are
lower bounded using the CDFs of the extreme eigenvalues. Finally, thresholds for ARICs
that are not exceeded with a target probability are deduced.
In the following, the analysis derived starting from the exact eigenvalues statistic (16) will
be referred as the exact eigenvalues distribution (EED) based approach.

A. RIP Analysis for Gaussian Matrices
A Gaussian matrix is said to satisfy the RIP of order s if its RIC, δs (A), is less than
a constant δ with high probability on a random draw of A. In other words, if a sufficient

February 12, 2018

DRAFT

10

condition for perfect reconstruction using a sparse recovery algorithm is satisfied with high
probability. This probability can be lower bounded from (8) and (16) as
 h
i
n
1 − ψms (m(1−δ), m(1+δ)) .
β(δ, m, n, s) ≥ 1−
s

(22)

The expression (22) gives, to the best of our knowledge, the tightest lower bound on the
probability of satisfying the RIP, β(δ), for finite dimensional Gaussian matrices. This is
attributed to employing the exact joint distribution of the extreme eigenvalues of Wishart
matrices, providing a quantitatively sharper estimates compared to the concentration bound
and the asymptotic approaches.
When applying CS, it is important to estimate the RIC to assess the recovery property
∗
of the measurement matrix. Let us define δs,min
(m, n, ǫ) as the RIC which is exceeded with

probability ǫ, such that
∗
P{δs (A) ≤ δs,min
(m, n, ǫ)} = 1 − ǫ .

(23)

Using (22) we can upper bound this value as
∗
δs,min
(m, n, ǫ)

≤

δs∗ (m, n, ǫ)

,

−1
ψms


 
n
1 − ǫ/
s

(24)

−1
where ψms
(y) is the inverse of ψms(m(1−x),m(1+x)). In the following we will refer to

δs∗ (m, n, ǫ) in (24) as the RIC threshold (RICt), where from (23) and (24) we have
P{δs (A) ≤ δs∗ (m, n, ǫ)} ≥ 1 − ǫ .

(25)

B. Asymmetric RIP Analysis for Gaussian Matrices
Let δs (A) be the LRIC as defined in (20). The CDF of the LRIC, FℓRIC (x), is lower
bounded as

 h
i
n
P {δ s (A) ≤ x} ≥ 1 −
1 − ψms (m(1 − x), ∞)
s

In fact, from (20) the CDF of the LRIC δ s (A) is




FℓRIC (x) = P 1 − min λmin(W) ≤ x
S⊂Ω


card(S)=s
 
n
P {λmin (W) ≤ 1 − x}
≥1−
s
 h
i
n
1 − ψms (m (1 − x), ∞) .
=1−
s

(26)

(27)

Let us define δ ∗s,min(m, n, ǫ) as the LRIC which is exceeded with probability ǫ, such that
P{δs (A) ≤ δ ∗s,min(m, n, ǫ)} = 1 − ǫ .

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

11

This quantity is upper bounded as follows
−1
δ ∗s,min(m, n, ǫ) ≤ δ ∗s (m, n, ǫ) = ψms,lower


 
n
1 − ǫ/
s

(28)

−1
where ψms,lower
(y) is the inverse of ψms (m(1 − x), ∞). In the following we will refer to

δ ∗s (m, n, ǫ) as the LRIC threshold (LRICt).

Similarly, for the CDF of the URIC, FuRIC (x), we have
 

n
P {λmax (W) ≥ 1 + x}
P δ s (A) ≤ x ≥ 1 −
s
 h
i
n
1 − ψms (0, m (1 + x)) .
=1−
s

(29)

∗

Then, we can compute a threshold such that P{δ s (A) ≤ δ s,min(m, n, ǫ)} = 1 − ǫ, which leads
to
∗
δ s,min(m, n, ǫ)

≤

∗
−1
δ s (m, n, ǫ) = ψms,upper

1−

ǫ
n
s

!

 −1

(30)

−1
where ψms,upper
(y) is the inverse of ψms (0, m(1 + x)). In the following we will refer to
∗

δ s (m, n, ǫ) as the URIC threshold (URICt).
Note that, while previously known approaches refer to infinite dimensional matrices, our
analysis accounts for the (always finite) true dimensions of the problem.
V. C ONDITIONS F OR P ERFECT R ECOVERY
In this section, the estimated thresholds for the RICs (both symmetric and asymmetric) of
finite matrices are used to quantify the maximum allowed signal sparsity order for various
recovery algorithms.
Definition 3 (The maximum sparsity order). Let A be a random m × n measurement matrix,
s be the signal sparsity order, and 0 < ǫ < 1 be an arbitrary constant. The maximum sparsity
order, s∗ , is the value such that every s-sparse vector with s < s∗ can be recovered perfectly
with probability PPR at least 1 − ǫ on a random draw of A. Then the maximum oversampling
ratio, a finite regime version of the asymptotic phase transition function, is defined as s∗ /m.
The maximum sparsity order is used to compare the performance of different recovery
algorithms and their associated sufficient conditions. As mentioned before, the perfect reconstruction conditions for many sparse recovery algorithms are stated in terms of the RICs [1],
[23], [25]–[34]. We now exploit these conditions to provide a probabilistic framework for
the recovery problem.

February 12, 2018

DRAFT

12

A. Symmetric RIC Based Sparse Recovery
About the symmetric RIC, the sufficient condition for perfect signal recovery via ℓ1 minimization can be represented in a generic form as δks (A) < δ, where k is a positive
integer and δ is a constant. As a consequence, the probability of perfect recovery can be
bounded as
PPR ≥ P {δks (A) < δ} = β(δ, m, n, ks)

(31)

with the proposed (22). Sufficient recovery condition of this class are, e.g., δs (A) < 1/3
[28], δ2s (A) < 0.6246 [21], etc.
The inverse problem is the calculation of the maximum sparsity order, for a given m and
a given n, such that the PPR is at least 1 − ǫ. For this target we have
s∗ = max {s : β(δ, m, n, ks) ≥ 1 − ǫ} .

(32)

B. Asymmetric RIC Based Sparse Recovery
Although the asymmetric RICs are less investigated, it is known that the conditions stated
in terms of them lead to tighter bounds for the maximum sparsity order [36]. This is attributed
to the asymmetric behavior of the extreme eigenvalues for Wishart matrices as analyzed in
section III-C.
A general class of sufficient recovery conditions based on the ARICs has the form

(33)
µ(s, A) , f δ k1 s (A) , δk2 s (A) < 1

where k1 and k2 are arbitrary positive integers and f δ k1 s (A) , δk2 s (A) is a non-decreasing

function in both δ k1 s (A) and δ k2 s (A). In this regard, we propose a generalization of the
symmetric RIC based condition, δs (A) < 13 , to an asymmetric one. In particular, it is possible
to prove that if the following condition is satisfied
µECG (s, A) , 2 δs (A) + δ s (A) < 1

(34)

then all s-sparse vectors can be recovered perfectly using ℓ1 -minimization.1 Other sufficient
conditions in the form of (33) are found in [24], [41]. For example, it is shown in [24] that
if



√  1 + δ2s (A)
1
µFL (s, A) ,
−1 <1
(35)
1+ 2
4
1 − δ 2s (A)

and in [41] that if µBT (s, A) , δ 2s (A)+ δ 6s (A)+δ6s (A) /4 < 1, then perfect reconstruction is

also guaranteed.
1

The proof is obtained by reformulating equations (33) and (34) in [28] to account for the asymmetric RICs.

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

13

Therefore, for random measurement matrices, the probability of perfect recovery by incorporating the ARICs can be bounded as
PPR ≥ P {µ(s, A) < 1} .

(36)

For the design problem of calculating the maximum sparsity order, by exploiting the monotonicity of the function f (·, ·), we have
n
o
∗
P {µ(s, A) ≤ 1} ≥ P δ k1 s (A) ≤ δ ∗k1 s , δ k2 s (A) ≤ δ k2 s
o
n
o
n
∗
(37)
≥ 1 − P δ k1 s (A) ≥ δ ∗k1 s − P δ k2 s (A) ≥ δ k2 s


∗
∗
for any δ∗k1 s and δk2 s such that f δ ∗k1 s , δ k2 s < 1. Equation (37) is due to the union bound,
(20), and (21). Setting the bound (37) to 1 − η and distributing equally the probability on
the lower and upper RICs, we get
o
n
n
o
η
∗
∗
P δ k2 s (A) ≤ δ k2 s = P δ k1 s (A) ≤ δ k1 s = 1 − .
2

(38)


∗
∗
∗
Finally, the maximum sparsity order s is the maximum s compatible with f δ k1 s , δk2 s <
∗

1, where δ ∗k1 s , δk2 s are calculated from (28) and (30) with ǫ = η/2 to satisfy (38). Then, every
sparse vector with s < s∗ can be perfectly recovered with probability at least 1 − η on a
random draw of A.

Although we focused on ℓ1 -minimization based recovery, the same approach can be used to
estimate the maximum sparsity order using greedy or thresholding algorithms. For example,
sufficient conditions on the RIC for perfect recovery using compressive sampling matching
pursuit (CoSaMP), orthogonal matching pursuit (OMP), and IHT are δ4s (A) < 0.4782
[21], δ13s (A) < 0.1666 [21], [34], and δ3s (A) < 0.5773 [42], respectively. Additionally,
asymmetric RIC based conditions have been obtained in [43] for CoSaMP, IHT, and subspace
pursuit (SP). For example,
√

µBCTT (s, A) , 2 2



δ 3s (A) + δ 3s (A)
2 + δ3s (A) − δ 3s (A)



<1

is a sufficient condition for perfect recovery using IHT [43].
VI. ROBUST R ECOVERY

OF

C OMPRESSIBLE S IGNALS

Up to now, we have studied the case of perfect recovery of sparse data in noiseless setting.
However, in practice signals can also be not exactly sparse, but rather compressible, i.e., the
data is well approximated by a sparse signal. Moreover, noise can be present during the
acquisition process.

February 12, 2018

DRAFT

14

A measure of the discrepancy between a compressible signal and its sparse representation
is the ℓ1 -error of best s-term approximation σs (x)1 , defined as
σs (x)1 , inf{kx − xs k1 ,

xs ∈ Rn is s-sparse} .

(39)

Hence, a signal is well approximated by an s-sparse vector if σs (x)1 is small [21]. Besides
considering compressible signals, we can also include the measurement noise in the model,
so that the measured vector can be written as
y = Ax + z

(40)

where z is a bounded noise with kzk ≤ κ. Assuming κ is known, we can account for the
noise term by modifying the constraint in the ℓ1 -minimization problem (3) as
x̂ = arg min kxk1 subject to ky − Axk ≤ κ .

(41)

This algorithm is called quadratically constrained ℓ1 -minimization [44]. There are also other
algorithms for sparse recovery in noisy cases, e.g., Dantzig selector [45], basis pursuit
denoising [46], denoising-orthogonal approximate message passing [47], etc.
For the model illustrated in (40), we cannot guarantee perfect signal recovery, but rather an
approximate reconstruction can be assured with bounded error. For example, it was shown in
[28] that if δs (A) < 1/3, the error after recovery can be bounded by a weighted combination
of κ and σs (x)1 , i.e.,

where
C1 (δs (A)) =
C2 (δs (A)) =

σs (x)1
kx̂ − xk ≤ C1 κ + C2 √
s

(42)

p

(43)

8 (1 + δs (A))
1 − 3δs (A)

p
√ 
8 2δs (A) + (1 − 3δs (A)) δs (A)
1 − 3δs (A)

+2.

(44)

The constants C1 and C2 give an insight about both the robustness (ability to handle noise) and
the stability (ability to handle compressible signals) of the recovery algorithm, respectively.
When A is a random matrix, both C1 and C2 are random variables. To characterize their
∗
statistical distribution, we propose to find a bound on the threshold Ci,min
, with i = 1, 2,

which is not exceeded with a predefined probability ǫi , i.e.,

∗
P Ci (δs (A)) ≤ Ci,min
= 1 − ǫi .

(45)

Noting that Ci (δs (A)) is monotonically increasing in δs (A), we have
P {Ci (δs (A)) ≤ Ci (δs∗ (m, n, ǫi ))} = P {δs (A) ≤ δs∗ (m, n, ǫi )} ≥ 1 − ǫi
DRAFT

(46)

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

15

where the RICt δs∗ (m, n, ǫi ) can be calculated from (24). Consequently, from (45) and (46)
∗
we upper bound Ci,min
as

∗
Ci,min
≤ Ci∗ , Ci (δs∗ (m, n, ǫi )) .

(47)

The inverse problem is finding the maximum sparsity order, for a given m and a given n,
such that the r.v. Ci , with i = 1, 2, is less than a targeted constant ci with probability at least
1 − ǫi . For this aim we have
s∗ = max {s : Ci (δs∗ (m, n, ǫi )) ≤ ci } .
Analogous results relating the recovery error with σs (x)1 and κ have been obtained for
different algorithms under suitable symmetric and asymmetric RIC based sufficient conditions
[24], [43], [48]–[50]. By following the same approach, the proposed methodology can be
applied to describe the statistics of the stability and robustness constants also for these cases.

VII. T RACY-W IDOM BASED RIC A NALYSIS
Although the proposed framework based on the exact distribution of the eigenvalues (16)
provides tight bounds on the RICs, it could be computationally expensive for large matrices,
for which easier approaches are preferred.
In this section, we derive approximations for the RICs of finite matrices based on the TW
distribution, much tighter than those obtained from concentration of measure inequalities.
Also, we study the convergence rate of the distribution of extreme eigenvalues to those based
on the TW by exploiting the small deviation analysis of the extreme eigenvalues around
their mean. In particular, we prove that TW based distributions approximate the eigenvalues
statistics of finite Gaussian matrices with exponentially small error in m, leading to accurate
estimation of the RICs.
In fact, it is well known that the distribution of the smallest and largest eigenvalues
of Wishart matrices tend, under some conditions, to a properly scaled and shifted TW
distributions [51]–[57]. Specifically, it has been shown that for the real Wishart matrix M
when m, s−
→∞ and m/s−
→γ ∈ (0, ∞)
λmax (M) − µms D
−
→ TW1
σms
February 12, 2018

(48)

DRAFT

16

where TW1 is a Tracy-Widom r.v. of order 1 with complementary CDF (CCDF) ΨTW1 (t),
√ 2
√
√
√
√
µms = ( m + s) , and σms = µms (1/ s + 1/ m)1/3 [53]. More precisely, from the
convergence in distribution definition and letting ρ , s/m we have
lim P {λmax (M) ≥ µms + t σms } =
n
1
2
√
√ 4o
lim P λmax (W) ≥ (1 + ρ)2 + t m− 3 ρ− 6 (1 + ρ) 3 = ΨTW1 (t).
m−
→∞

m−
→∞

(49)

Similarly, for the smallest eigenvalue, when m, s−
→∞ and m/s−
→γ ∈ (1, ∞) [56]
−

ln λmin (M) − vms D
−
→ TW1
τms

(50)

with scaling and centering parameters
τms
vms

(s − 1/2)−1/2 − (m − 1/2)−1/2
p
p
=
m − 1/2 − s − 1/2

1/3

 1
p
p
2
m − 1/2 − s − 1/2 + τms
= 2 ln
.
8
∗

Regarding the RIC analysis for finite Gaussian matrices, let δ s (m, n, ǫ), δ ∗s (m, n, ǫ), and
δs∗ (m, n, ǫ) be the RIC thresholds as defined in (30), (28), and (24), respectively. We will
show that they can be approximated as
  
√
n
+ρ+2 ρ
ǫ/
≃ δ TW , m ρ (1 + ρ)
s
  

1
n
δ∗s (m, n, ǫ) ≃ δ ∗TW , 1− exp vms − τms Ψ−1
ǫ/
TW1
s
m

 
n
∗
−1
δs∗ (m, n, ǫ) ≃ δTW
, Pesw
1 − ǫ/
s
∗
δs (m, n, ǫ)

∗

∗

− 23 − 61

√

4
3

Ψ−1
TW1

(51)
(52)
(53)

∗
less than one, where Ψ−1
for δ TW , δ ∗TW , and δTW
TW1 (y) is the inverse of the TW’s CCDF and
−1
Pesw
(y) is the inverse of




m(1 + x) − µms
vms − ln m(1 − x)
e
− ΨTW1
.
(54)
Psw (x) , 1 − ΨTW1
τms
σms

In order to prove these formulas, at first the convergence rate of the extreme eigenvalue

distributions to those based on the TW is provided. For the URIC, it has been shown in [58,
Theorem 2] that there exists a constant c > 0, depending only on ρ, such that


1 3
P {λmax (M) ≥ µms (1 + z)} ≤ c exp − s z 2
c

(55)

for all m > s ≥ 1 and 0 < z ≤ 1. This small deviation analysis provides tighter bounds
compared to the concentration inequality (10) and Edelman bound [39, Lemma 4.2] used for

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

17

large m in [36]–[38]. From (55), the L.H.S. of (49) can be tightly bounded for finite m and
√ 2/3
for t ≤ m2/3 ρ1/6 1 + ρ
as


n
3
1
2
√ 4o
√
(56)
P λmax (W) ≥ (1 + ρ)2 + t m− 3 ρ− 6 (1 + ρ) 3 ≤ c exp − c1 t 2
where c1 , c−1 ρ3/4 1 +

√ −1
ρ . Regarding the R.H.S, for sufficiently large t we have


3
(57)
ΨTW1 (t) ≤ c2 exp −c3 t 2

where c2 > 0 and c3 > 0 are constants [59, eq. (2)], [60]. Now the error in using the TW

can be bounded as

n

3
1
2
√
√ 4o
P λmax (W) ≥ (1 + ρ)2 + t m− 3 ρ− 6 (1 + ρ) 3 − ΨTW1 (t) ≤ c4 exp −c5 t 2
(58)

where c4 = max{c, c2 } and c5 = min{c1 , c3 }. Therefore, the error due to approximating
P {λmax (W) ≥ 1 + x} in (29) by that of the TW can be bounded from (58) as


1
2
√ − 34
√
P {λmax (W) ≥ 1 + x} −ΨTW1 (x−2 ρ−ρ) m 3 ρ 6 (1+ ρ)


3
1
√
√
≤ c4 exp −m (x − 2 ρ − ρ) 2 c5 ρ 4 (1 + ρ)−2 (59)

√ 2
for x ≤ 2 1+ ρ −1.2 Hence, the absolute error in approximating the exact probability

with that based on the TW distribution is exponentially small in m and the URICt can be
approximated by (51).
A similar reasoning can be used to derive the thresholds for the lower and symmetric RICs
(the proof is not reported here for the sake of conciseness).
Finally, we would like to remark that Tracy-Widom based approaches could be used not

only for Wishart ensembles, but also for a wider class of matrices like those drawn from some
sub-Gaussian distributions, e.g., Rademacher and Bernoulli measurement matrices. This is
motivated by the universality of the TW laws for the extreme eigenvalues of large random
matrices [61], [62], although further research is required to investigate such extensions.
VIII. N UMERICAL R ESULTS
In this section, numerical results are presented to compare the proposed exact and TW
approaches with the concentration inequalities, for analyzing the probability that the RIP is
satisfied. Moreover, the statistics of the RICs, the probability of perfect reconstruction, the
maximum sparsity order for various recovery algorithms, and the robustness and stability
constants are also investigated.
2

√ 2
Note that x ≤ 1 is a stronger condition than x ≤ 2 1+ ρ −1.

February 12, 2018

DRAFT

18

0

10

-2

10

-4

PSfrag replacements

P {δs (A) ≥ 1/3}

10

-6

10

-8

10

-10

10

Concentr. bound
TW approx.
EED approach

-12

10

1

-14

10

1

2

3

4

5

7

6

8

9

−4
10 ×10

s/n

Fig. 2. Symmetric RIP: upper bounds on the probability of not satisfying the RIP, P {δs (A) ≥ 1/3}, for m/n = 0.1
(solid) and m/n = 0.4 (dashed). The signal dimension is n = 3 · 104 . Curves obtained through the concentration bound,
(8) and (12), the EED, (22), and the TW approximation, (8) and (54).

Fig. 2 shows upper bounds on the probability of not satisfying the RIP, P{δs (A) ≥ 1/3},
using the EED based approach (22), the TW approximation (8), (54), and the concentration
bound (8), (12). Note that when the sparsity level is beyond some threshold value, the
probability of not satisfying the RIP rapidly increases from zero to one. This figure also
illustrates the limit on the maximum sparsity ratio that still permits satisfying the RIP with a
targeted probability. We can see that the EED based approach indicates higher sparsity ratios
(less sparse vectors) compared to those estimated by the well-known concentration bound
(more than 220% increase in s/n when the probability is 10−14 and m/n = 0.4). In fact,
the concentration inequality is quite loose in bounding the probability that a submatrix is ill
conditioned, 1 − Psw (δ), and consequently in analyzing the RIP.
∗

Regarding the ARICs, the upper RIC thresholds, δ s (m, n, ǫ), computed by means of (30)
and (51), are plotted in Fig. 3 for an excess probability ǫ = 10−3 , as a function of the
compression ratio, m/n, and the oversampling ratio, s/m. In this figure, we set m = 4000
and vary n from 2 · 105 to 4000. As can be noticed the TW approximation is quite accurate.
To further investigate the RIC bounds, we report in Table I both the LRIC and URIC
thresholds for different m/n using various approaches: the proposed EED (28), (30), the TW

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

19

×10−3

8

0.7

6

s/m

0.6
0.5

4

0.4

2

PSfrag replacements
0.3

0
0

0.2

0.4

0.6

0.8

m/n
∗

∗

Fig. 3. Level sets of the upper RIC threshold δ s (m, n, ǫ) ∈ {0.3, 0.4, 0.5, 0.6, 0.7} such that P{δ s (A) ≥ δ s (m, n, ǫ)} ≤ ǫ,
using the EED (solid) and TW (dashed), for m = 4000 and ǫ = 10−3 .

approximation (52), (51), the empirical lower bounds in [63], and the asymptotic bounds in
[36], [37]. We can see that the upper bounds on the RICs obtained from the EED approach is
sharp, with small differences from the empirical lower bounds (averaged over 100 different
realizations) indicated by [63].
With the aim of comparing different sufficient recovery conditions via ℓ1 -minimization,
IHT, and CoSaMP algorithms, in Fig. 4 we report the maximum oversampling ratio, s∗ /m,
such that PPR ≥ 0.999. All curves have been obtained by using the EED based approach.
Specifically, for ℓ1 -minimization we consider the symmetric RIC condition δs (A) ≤ 1/3 [28],
its relaxed asymmetric extension µECG (s, A) < 1 proposed in Section V-B, δ2s (A) < 0.624 [21],
µFL (s, A) < 1 [24], and µBT (s, A) < 1 [41]. For IHT we used the conditions δ3s (A) <
0.5773 [42] and µBCTT (s, A) < 1 [43], while for the CoSaMP we considered δ4s (A) <
0.4782 [21]. We can see that the asymmetric conditions provide higher estimates of the
sparsity which can be handled by compressed sensing, compared to the symmetric conditions
(more than 40% increase in s). As known, the ℓl -minimization and IHT algorithms allow
higher oversampling ratios than the CoSaMP algorithm.

February 12, 2018

DRAFT

20

TABLE I
T HE RIC THRESHOLDS USING THE EED BOUND AND TW APPROXIMATION FOR ǫ = 10−2 , EMPIRICAL AVERAGED
LOWER BOUNDS

[63], BCT [36], AND BT [37] APPROACHES , FOR m = 2000
ROWS GIVE THE UPPER AND LOWER

s = 4. F OR EACH m/n, THE TWO

RIC.

Finite
m/n ↓

AND

Asymptotic

EED

TW

Empirical

upper bounds

approximation

lower bounds

(30), (28)

(51), (52)

[63]

0.3071

0.3395

0.2561

BCT

BT

[36]

[37]

0.2703

0.3408

0.3402

0.2846

0.2322

0.2777

0.2772

0.3000

0.3304

0.2626

0.3344

0.3337

0.2512

0.2778

0.2268

0.2734

0.2729

0.2949

0.3239

0.2580

0.3297

0.3291

0.2477

0.2729

0.2214

0.2703

0.2698

0.4

0.6

0.8

Moreover, we provide in Fig. 5 the maximum oversampling ratio, for uniform recovery,
indicated by our proposed approach along with those obtained from the polytope [20], Null
space [21, Theorem 9.29], geometric functional [18, Theorem 4.1], and RIP [21, Theorem
9.27] analyses for finite matrices with m = 4000 and PPR ≥ 0.5. However, we would like to
note that the polytope based approach suggests tighter bounds on the maximum sparsity order,
as it fully exploits the geometry of the ℓ1 -minimization for signal recovery from Gaussian
measurements. On the other hand, the RIP is suitable for analyzing the robust and stable
reconstruction with several sparse recovery algorithms, such as optimization, greedy, and
thresholding.
Finally, regarding the analysis for compressible signals in noise, the contours for robustness
and stability thresholds C1∗ and C2∗ are shown in Fig. 6. As can be seen for small s/m the
thresholds are small, indicating that the more sparse is the signal, the more robust and stable is
the reconstruction process. Therefore, a compromise between sparsity and robustness/stability
should be considered when designing the acquisition system. This figure also gives the
maximum oversampling ratio for a given m and n, such that the minimization program
(41) can approximately recover the measured signal with a predefined discrepancy.

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

×10−3

12

ℓ1 , µBT (s, A) < 1

11
PSfrag replacements

ℓ1 , δ2s (A) < 0.624

10

ℓ1 , µFL (s, A) < 1
ℓ1 , µECG (s, A) < 1

9

ℓ1 , δs (A) < 1/3

8

IHT, δ3s (A) < 0.5773
IHT, µBCTT (s, A) < 1

s∗ /m

7

11 δ 12 s (A) + δ 11 s (A) < 10

21

CoSaMP, δ4s (A) < 0.4782

6
5
4
3
2
1
0

0.1

0.2

0.3

0.4

0.6

0.5

0.7

0.8

0.9

1

m/n

Fig. 4. The maximum oversampling ratio, s∗ /m, for various recovery algorithms and their associated sufficient conditions
using the proposed EED based approach, for m = 4000 and PPR ≥ 0.999 (η = 10−3 ).

IX. C ONCLUSION
For sparse data acquisition we have found that the concentration of measure inequality
provides a loose upper bound on the probability that a measurement submatrix is ill conditioned. For example, in some cases it overestimate the maximum sparsity ratio by over
220% with respect to the proposed exact eigenvalues based approach. For finite matrices,
by tightly bounding the symmetric and asymmetric RICs, the best current lower bound on
the maximum sparsity order guaranteeing successful recovery has been provided, for various
sparse reconstruction algorithms. For stable and robust recovery of compressible data, we
have noticed that when the sparsity order decreases the discrepancy between the recovered
and original signals reduces. Finally, we have shown that simple approximations for the RICs
can be obtained based on TW distributions.
R EFERENCES
[1] E. Candes and T. Tao, “Decoding by linear programming,” IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215,
Dec. 2005.

February 12, 2018

DRAFT

22

128

×10−3

64

Polytope analysis [20]
Null space property [21]
RIP analysis (EED), µBT (s, A) < 1

32

Geometric functional analysis [18]

PSfrag replacements

s∗ /m

RIP analysis [21], δ2s (A) < 0.624

16
8
4
2
1

0.2

0.4

0.6

0.8

m/n

Fig. 5. The maximum oversampling ratio, s∗ /m, for perfect recovery via ℓ1 -minimization, estimated by the proposed RIP
based approach (EED) along with the RIP [21], polytope [20], Null space [21], and geometric functional [18] analyses, for
m = 4000 and PPR ≥ 0.5.

[2] D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289 –1306, April 2006.
[3] ——, “For most large underdetermined systems of linear equations the minimal ℓ1 -norm solution is also the sparsest
solution,” Comm. on Pure and Applied Math., vol. 59, no. 6, pp. 797–829, 2006.
[4] E. 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, Dec. 2006.
[5] E. Candes and M. Wakin, “An introduction to compressive sampling,” IEEE Signal Process. Mag., vol. 25, no. 2, pp.
21–30, March 2008.
[6] Y. Eldar, P. Kuppinger, and H. Bolcskei, “Block-sparse signals: Uncertainty relations and efficient recovery,” IEEE
Trans. Signal Process., vol. 58, no. 6, pp. 3042–3054, June 2010.
[7] Y. Eldar and G. Kutyniok, Compressed sensing: theory and applications.

Cambridge University Press, 2012.

[8] G. Coluccia, A. Roumy, and E. Magli, “Operational rate-distortion performance of single-source and distributed
compressed sensing,” IEEE Trans. Commun., vol. 62, no. 6, pp. 2022–2033, June 2014.
[9] D. Valsesia, G. Coluccia, and E. Magli, “Graded quantization for multiple description coding of compressive
measurements,” IEEE Trans. Commun., vol. 63, no. 5, pp. 1648–1660, May 2015.
[10] H. Schepker, C. Bockelmann, and A. Dekorsy, “Efficient detectors for joint compressed sensing detection and channel
decoding,” IEEE Trans. Commun., vol. 63, no. 6, pp. 2249–2260, June 2015.
[11] A. Kipnis, G. Reeves, Y. Eldar, and A. Goldsmith, “Fundamental limits of compressed sensing under optimal
quantization,” in Proc. IEEE Inter. Sympos. on Information Theory (ISIT), June 2017.

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

9

23

×10−4

9
8

7

7

s/m

6

5

5

3

PSfrag replacements
4

1
0.2

0.4

0.6

0.8

1

m/n

Fig. 6. Level sets of robustness and stability thresholds in Section VI, C1∗ (solid) and C2∗ (dashed), with C1∗ , C2∗ ∈
{4, 5, 6, 7, 8, 9}, for m = 2 · 104 and ǫ1 = ǫ2 = 10−3 , using the EED based approach.

[12] J. Mota, N. Deligiannis, and M. Rodrigues, “Compressed sensing with prior information: Strategies, geometry, and
bounds,” IEEE Trans. Inf. Theory, vol. 63, no. 7, pp. 4472–4496, July 2017.
[13] L. Potter, E. Ertin, J. Parker, and M. Cetin, “Sparsity and compressed sensing in radar imaging,” Proc. of the IEEE,
vol. 98, no. 6, pp. 1006–1020, June 2010.
[14] D. Dorsch and H. Rauhut, “Refined analysis of sparse MIMO radar,” J. of Fourier Anal. and Appl., vol. 23, no. 3,
pp. 485–529, Jun 2017.
[15] G. Taubock, F. Hlawatsch, D. Eiwen, and H. Rauhut, “Compressive estimation of doubly selective channels in
multicarrier systems: Leakage effects and sparsity-enhancing processing,” IEEE J. Sel. Topics Signal Process., vol. 4,
no. 2, pp. 255–271, April 2010.
[16] M. Mishali and Y. Eldar, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” IEEE
J. Sel. Topics Signal Process., vol. 4, no. 2, pp. 375–391, April 2010.
[17] D. Donoho and J. Tanner, “Precise undersampling theorems,” Proc. IEEE, vol. 98, no. 6, pp. 913–924, May 2010.
[18] M. Rudelson and R. Vershynin, “On sparse reconstruction from Fourier and Gaussian measurements,” Comm. on Pure
and Applied Math., vol. 61, no. 8, pp. 1025–1045, 2008.
[19] M. Bayati, M. Lelarge, and A. Montanari, “Universality in polytope phase transitions and message passing algorithms,”
The Annals of Applied Probability, vol. 25, no. 2, pp. 753–822, March 2015.
[20] D. Donoho and J. Tanner, “Exponential bounds implying construction of compressed sensing matrices, error-correcting
codes, and neighborly polytopes by random sampling,” IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 2002–2016, April
2010.

February 12, 2018

DRAFT

24

[21] S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing.

Springer, 2013.

[22] V. Chandrasekaran, B. Recht, P. Parrilo, and A. Willsky, “The convex geometry of linear inverse problems,” Found.
of Computational Math., vol. 12, no. 6, pp. 805–849, 2012.
[23] E. Candès, “The restricted isometry property and its implications for compressed sensing,” Comptes Rendus
Mathematique, vol. 346, no. 9, pp. 589–592, May 2008.
[24] S. Foucart and M.-J. Lai, “Sparsest solutions of underdetermined linear systems via ℓq -minimization for 0 < q ≤ 1,”
Appl. Comput. Harmon. Anal., vol. 26, no. 3, pp. 395 – 407, 2009.
[25] S. Foucart, “A note on guaranteed sparse recovery via ℓ1 -minimization,” Appl. Comput. Harmon. Anal., vol. 29, no. 1,
pp. 97–103, 2010.
[26] T. Cai, L. Wang, and G. Xu, “New bounds for restricted isometry constants,” IEEE Trans. Inf. Theory, vol. 56, no. 9,
pp. 4388–4394, Sept. 2010.
[27] Q. Mo and S. Li, “New bounds on the restricted isometry constant δ2k ,” Appl. Comput. Harmon. Anal., vol. 31, no. 3,
pp. 460–468, Nov. 2011.
[28] T. Cai and A. Zhang, “Sharp RIP bound for sparse signal and low-rank matrix recovery,” Appl. Comput. Harmon.
Anal., vol. 35, no. 1, pp. 74–93, 2013.
[29] T. Blumensath and M. Davies, “Iterative thresholding for sparse approximations,” J. Fourier Anal. Appl., vol. 14, no.
5-6, pp. 629–654, Sep. 2008.
[30] S. Foucart, “Sparse recovery algorithms: Sufficient conditions in terms of restricted isometry constants,” Approximation
Theory XIII, San Antonio 2010, vol. 13, pp. 65–77, 2012.
[31] J. Tropp, D. Needell, and R. Vershynin, “Iterative signal recovery from incomplete and inaccurate measurements,” in
Proc. Information Theory and Applications Workshop, San Diego, USA, Jan. 2008.
[32] 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.
[33] D. Needell and R. Vershynin, “Signal recovery from incomplete and inaccurate measurements via regularized
orthogonal matching pursuit,” IEEE J. Sel. Topics Signal Process., vol. 4, no. 2, pp. 310–316, April 2010.
[34] T. Zhang, “Sparse recovery with orthogonal matching pursuit under RIP,” IEEE Trans. Inf. Theory, vol. 57, no. 9, pp.
6215–6221, Sept 2011.
[35] W. Wang, M. Wainwright, and K. Ramchandran, “Information-theoretic limits on sparse signal recovery: Dense versus
sparse measurement matrices,” IEEE Trans. Inf. Theory, vol. 56, no. 6, pp. 2967–2979, June 2010.
[36] J. Blanchard, C. Cartis, and J. Tanner, “Compressed sensing: How sharp is the restricted isometry property,” SIAM
review, vol. 53, no. 1, pp. 105–125, 2011.
[37] B. Bah and J. Tanner, “Improved bounds on restricted isometry constants for Gaussian matrices,” SIAM J. Matrix
Anal. Appl., vol. 31, no. 5, pp. 2882–2898, 2010.
[38] ——, “Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices,” Linear
Algebra and Its Applications, vol. 441, no. Complete, pp. 88–109, Jan. 2014.
[39] A. Edelman, “Eigenvalues and condition numbers of random matrices,” SIAM J. Matrix Anal. Appl., vol. 9, no. 4, pp.
543–560, 1988.
[40] M. Chiani, “On the probability that all eigenvalues of Gaussian, Wishart, and double Wishart random matrices lie
within an interval,” IEEE Trans. Inf. Theory, vol. PP, no. 99, pp. 1–10, 2017.
[41] J. Blanchard and A. Thompson, “On support sizes of restricted isometry constants,” Appl. Comput. Harmon. Anal.,
vol. 29, no. 3, pp. 382–390, 2010.
[42] S. Foucart, “Hard thresholding pursuit: An algorithm for compressive sensing,” SIAM J. Numer. Anal., vol. 49, no. 6,
pp. 2543–2563, 2011.

DRAFT

February 12, 2018

ELZANATY et al.: LIMITS ON SPARSE DATA ACQUISITION: RIC ANALYSIS OF FINITE GAUSSIAN MATRICES

25

[43] J. Blanchard, C. Cartis, J. Tanner, and A. Thompson, “Phase transitions for greedy sparse approximation algorithms,”
Appl. Comput. Harmon. Anal., vol. 30, no. 2, pp. 188–203, 2011.
[44] R. Tibshirani, “Regression shrinkage and selection via the LASSO,” J. R. Stat. Soc.. Series B (Methodological), pp.
267–288, 1996.
[45] E. Candes and T. Tao, “The Dantzig selector: Statistical estimation when p is much larger than n,” The Annals of
Statistics, vol. 35, no. 6, pp. 2313–2351, Dec. 2007.
[46] S. Chen and D. Donoho, “Basis pursuit,” in Proc. of the Twenty-Eighth Asilomar Conf. on Signals, Systems and
Computers, Pacific Grove, CA, USA, vol. 1, Oct. 1994, pp. 41–44.
[47] Z. Xue, J. Ma, and X. Yuan, “D-OAMP: A denoising-based signal recovery algorithm for compressed sensing,” in
Proc. IEEE Global Conf. on Signal and Inf. Process. (GlobalSIP), Dec. 2016, pp. 267–271.
[48] R. Saab, R. Chartrand, and O. Yilmaz, “Stable sparse approximations via nonconvex optimization,” in Proc. IEEE
International Conf. on Acoustics, Speech and Sig. Process., ICASSP, Las Vegas, USA, March 2008, pp. 3885–3888.
[49] L. Jacques, D. Hammond, and J. Fadili, “Weighted ℓp constraints in noisy compressed sensing,” in Proc. Sig. Process.
with Adaptive Sparse Structured Representations Workshop, Edinburgh, Scotland, UK, June 2011, p. 49.
[50] W. Zeng, H. So, and X. Jiang, “Outlier-robust greedy pursuit algorithms in ℓp -space for sparse approximation,” IEEE
Trans. Signal Process., vol. 64, no. 1, pp. 60–75, Jan 2016.
[51] C. Tracy and H. Widom, “Level-spacing distributions and the Airy kernel,” Comm. Math. Phys., vol. 159, no. 1, pp.
151–174, Dec. 1994.
[52] K. Johansson, “Shape fluctuations and random matrices,” Comm, in Math. Physics, vol. 209, no. 2, pp. 437–476, 2000.
[53] M. Johnstone, “On the distribution of the largest eigenvalue in principal components analysis,” The Annals of Statistics,
vol. 29, no. 2, pp. 295–327, 2001.
[54] C. Tracy and H. Widom, “The distributions of random matrix theory and their applications,” New Trends in
Mathematical Physics, V. Sidoravicius (ed.), pp. 753–765, 2009.
[55] F. Bornemann, “On the numerical evaluation of distributions in random matrix theory: a review,” J. Markov Process.
Related Fields, vol. 16, p. 803866, 2010.
[56] Z. Ma, “Accuracy of the TracyWidom limits for the extreme eigenvalues in white Wishart matrices,” Bernoulli, vol. 18,
no. 1, pp. 322–359, 02 2012.
[57] E. Basor, Y. Chen, and L. Zhang, “PDEs satisfied by extreme eigenvalues distributions of GUE and LUE,” Random
Matrices: Theory and Applications, vol. 01, no. 01, p. 1150003, 2012.
[58] M. Ledoux and B. Rider, “Small deviations for beta ensembles,” Electron. J. Prob., vol. 15, pp. 1319–1343, 2010.
[59] G. Aubrun, “A sharp small deviation inequality for the largest eigenvalue of a random matrix,” in Séminaire de
Probabilités XXXVIII. Springer, 2005, pp. 320–337.
[60] L. Dumaz and B. Virág, “The right tail exponent of the Tracy-Widom distribution,” Ann. l’institut Henri Poincare
Prob. Stat., vol. 49, no. 4, pp. 915–923, 2011.
[61] O. Feldheim and S. Sodin, “A universality result for the smallest eigenvalues of certain sample covariance matrices,”
Geometric and Functional Analysis, vol. 20, no. 1, pp. 88–123, 2010.
[62] S. Péché, “Universality results for the largest eigenvalues of some sample covariance matrix ensembles,” Probability
Theory and Related Fields, vol. 143, no. 3, pp. 481–516, 2009.
[63] C. Dossal, G. Peyr, and J. Fadili, “A numerical exploration of compressed sampling recovery,” Linear Algebra Appl.,
vol. 432, no. 7, pp. 1663 – 1679, 2010.

February 12, 2018

DRAFT

