arXiv:1708.03608v1 [cs.IT] 11 Aug 2017

A Fast Noniterative Algorithm for
Compressive Sensing Using
Binary Measurement Matrices
Mahsa Lotfi and Mathukumalli Vidyasagar

∗

August 14, 2017

Abstract
In this paper we present a new algorithm for compressive sensing that makes use of binary
measurement matrices and achieves exact recovery of sparse vectors, in a single pass, without
any iterations. Our algorithm is hundreds of times faster than ℓ1 -norm minimization, and
methods based on expander graphs (which require multiple iterations). Moreover, our method
requires the fewest measurements amongst all methods that use binary measurement matrices.
The algorithm can accommodate nearly sparse vectors, in which case it recovers the largest
components, and can also accommodate noisy measurements.
Numerical experiments with randomly generated sparse vectors indicate that the sufficient
conditions for our algorithm to work are very close to being necessary. In contrast, the best
known sufficient condition for ℓ1 -norm minimization to recover a sparse vector, namely the
Restricted Isometry Property (RIP), is about thirty times away from being necessary. Therefore
it would be worthwhile to explore alternate and improved sufficient conditions for ℓ1 -norm
minimization to achieve the recovery of sparse vectors.

1

Introduction

1.1

Summary

Compressive sensing refers to the recovery of sparse (or nearly sparse) high-dimensional vectors
using a very small number of measurements, often far fewer than required by the Nyquist sampling
theorem. To date there have been two different approaches to compressive sensing. The older,
and more pervasive, approach is based on ℓ1 -norm minimization, while a recent approach is based
on using expander graphs. In ℓ1 -norm minimization, the measurement matrix A has to satisfy
a property known as the restricted isometry property (RIP). There are two approaches to the
construction of measurement matrices satisfying the RIP, namely probabilistic and deterministic.
In principle, probabilistic approaches lead to a smaller number of measurements. But in practice,
for vectors of dimension a few million or less, deterministic methods require fewer measurements
than probabilistic methods. Indeed, for vectors of dimension 104 or so, the probabilistic approach
requires more measurements than the dimension of the vector! A more recent approach is based
on expander graphs, and makes use of measurement matrices that are binary. If the expander
The authors are with the Erik Jonsson School of Engineering and Computer Science, The University of Texas at
Dallas, Richardson, TX 75080, USA. This research was supported by the National Science Foundation, USA under
Award #ECCS-1306630.
∗

1

graph satisfies appropriate properties, this algorithm recovers the unknown vector exactly in a
finite number of iterations.
In the present paper, we propose a new algorithm for compressive sensing that makes use of a
suitably constructed binary measurement matrix. Our algorithm differs from current algorithms in
a number of ways. First, our algorithm is noniterative, in that it requires only a single pass through
the dimension of the unknown vector. If the unknown vector is sparse, our algorithm recovers the
unknown vector exactly. When the unknown vector is nearly but not exactly sparse, our algorithm
recovers the dominant part of the unknown vector, that is, the components that are the largest in
magnitude. When the unknown vector is sparse and there is measurement noise, our algorithm still
recovers the unknown vector exactly, provided the support set of the noise has sufficiently small
cardinality. Finally, when the unknown vector is nearly sparse and there is measurement noise,
our algorithm recovers the support set of the dominant part of the unknown vector, that is, the
locations of the largest components of the unknown vector. It is worth mentioning that with ℓ1 norm minimization, there is no guarantee that the support set of the dominant components would
be recovered. Due to its noniterative nature, our method is by far the fastest among all known
algorithms for compressive sensing, being hundreds of times faster than the existing algorithm based
on expander graphs, and about a hundred times faster than ℓ1 -norm minimization. It is shown
that the binary measurement matrix used by us can be justified via both the RIP approach and the
expander graph approach. However, by a careful analysis, we are able to establish that our method
requires the fewest number of measurements amongst all methods that use binary measurements.1
To illustrate the new algorithm and to compare it with existing algorithms, we generated 100
vectors at random with n = 20, 000 components, of which only k = 6 are nonzero. Appropriate
measurement matrices were generated using known sufficient conditions based on the restricted
isometry property (for ℓ1 -norm minimization), the expander-graph approach, and our approach.
The performance of all approaches were compared, and as expected, our algorithm outperformed
both ℓ1 -norm minimization and the expander-graph based approach. However, an interesting phenomenon was then observed. We retained the measurement matrices designed for k = 6, but
increased the actual number of nonzero components, to see at what value of k each of these approaches broke down (in terms of failure to recover all 100 randomly generated k-sparse n-vectors).
Our algorithm broke down for k > 9, suggesting that the sufficient condition derived here is very
close to being necessary. In contrast, ℓ1 -norm minimization continued to recover all 100 k-sparse
n-vectors for k up to 208, even though the measurement matrix was guaranteed to work only for
k = 6. This suggests that the current approach of using the restricted isometry property to guarantee the recovery of sparse vectors leads to bounds that are enormously conservative. This would
be an excellent topic for further research.

1.2

Precise Definition of Compressive Sensing

In this subsection we give a very precise formulation of what “compressive sensing” means. The
terminology more or less follows that in [1, 2]. Throughout, n denotes the dimension of the unknown
vector, and [n] stands for the set {1, . . . , n}. The symbol supp(x) ⊆ [n] denotes the “support” of a
vector x ∈ Rn ; that is
supp(x) := {i ∈ [n] : xi 6= 0}.
1

There is another method based on chirp matrices that uses fewer measurements, but the associated algorithm
runs more slowly, not just compared to ours, but also compared to other methods based on ℓ1 -norm minimization.

2

If k < n is a specified integer, then Σk ⊆ Rn denotes the set of k-sparse vectors, that is
Σk := {x ∈ Rn : |supp(x)| ≤ k}.
Suppose k · k is some specified norm on Rn , and k < n is a specified integer. Then the sparsity
index σk (x, k · k) is defined by
σk (x, k · k) := min kx − zk.
(1)
z∈Σk

Rn

For a given x ∈
and an integer k < n, the symbols xd ∈ Rn and xr ∈ Rn denote respectively
the dominant part and the residual part of x. Thus xd is the vector consisting of the k largest
components by magnitude of x with the remaining components set equal to zero, and xr = x − xd .
It is obvious that, for any p ∈ [1, ∞], we have that σk (x, k·kp ) = kxr kp . Note that, strictly speaking,
we should write xdk because the dominant part depends on the specified integer k, but we do not do
this in the interests of less cluttered notation. Also, in case of “ties,” when two or more components
of x have the same magnitude, the symbol xd can be defined in any consistent fashion.
Following the notation in [2], we view compressive sensing as consisting of two maps: A measurement matrix A ∈ Rmn where m < n is the number of measurements, and a decoding map
∆ : Rm → Rn .
Definition 1 A pair (A, ∆) is said to achieve exact sparse recovery of order k if
∆(Ax) = x, ∀x ∈ Σk .

(2)

A pair (A, ∆) is said to achieve stable sparse recovery of order k if there exists a constant C
such that
k∆(Ax) − xk2 ≤ Cσk (x, k · k1 ), ∀x ∈ Rn .
(3)
A pair (A, ∆) is said to achieve robust sparse recovery of order k if there exist constants C, D
such that, whenever η ∈ Rm satisfies kηk2 ≤ ǫ, we have that
k∆(Ax + η) − xk2 ≤ Cσk (x, k · k1 ) + Dǫ, ∀x ∈ Rn .

(4)

It is easy to check that robust recovery implies stable recovery, which in turn implies exact
recovery.

1.3

Compressive Sensing via ℓ1 -Norm Minimization

One of the most popular approaches to compressive sensing is ℓ1 -norm minimization. This approach
is originally introduced in [3, 4] as a heuristic and is called “basis pursuit.” The method consists
of defining the decoding map ∆ as
∆(y) = x̂ := argmin kzk1 s.t. y = Az
z

(5)

in the case of noiseless measurements, and
∆(y) = x̂ := argmin kzk1 s.t. ky − Azk2 ≤ ǫ
z

(6)

in the case of noisy measurements. In several papers over the years, beginning with [5, 6], it is
shown that ℓ1 -norm minimization achieves robust sparse recovery under suitable conditions. At
present, sufficient conditions for ℓ1 -norm minimization to achieve robust sparse recovery are usually
stated in terms of the so-called restricted isometry property, introduced in [5], defined next.
3

Definition 2 A matrix A ∈ Rmn is said to satisfy the restricted isometry property (RIP) of
order k with constant δ if
(1 − δ)kuk22 ≤ kAuk22 ≤ (1 + δ)kuk22 , ∀u ∈ Σk .

(7)

Available results show that ℓ1 -norm minimization achieves robust sparse recovery provided the
measurement matrix A satisfies the RIP with a sufficiently small constant. The definitive results
in this direction are derived in [7].
Theorem 1 (See Theorems 1.1 and 2.1 of [7].) Suppose
that, for some number t > 1, the matrix
p
A satisfies the RIP of order ⌈tk⌉ with constant δ < (t − 1)/t. Then ℓ1 -norm minimization as in
(6) achieves robust sparse recovery.
Theorem 2 (See [7, Theorem 2.2].) Suppose t ≥ 4/3. Then for all ξp
> 0 and all k ≥ 5/ξ, there
exists a matrix A that satisfies the RIP of order tk with constant δtk < (t − 1)/t + ξ, and a vector
x ∈ Σk such that
1. With the noise-free measurement y = Ax, the decoder map ∆ defined in (5) fails to recover
x.
2. With a noisy measurement y = Ax + η where kηk2 ≤ ǫ, the decoder map ∆ defined in (6)
fails to recover x.
This naturally raises the question as to how one might generate matrices that satisfy the RIP.
There are two distinct approaches, namely probabilistic and deterministic. In [5] and several
subsequent papers (of which we cite only [8] as an example), it is shown that if the matrix A
consists of suitably scaled i.i.d. samples of a sub-Gaussian random variable with zero mean and
unit variance, then with high probability the resulting matrix A satisfies the RIP. Moreover, the
number of measurements is m = O(k log(n/k)).
At present there are very few deterministic approaches to constructing matrices that satisfy
the RIP. In fact the authors are aware of only three approaches. In [9], the author presents a
deterministic method for constructing a binary measurement matrix that is guaranteed to satisfy
the RIP. This paper is most relevant to our work. In [10], the authors begin with a discrete Fourier
matrix (which is unitary), and give a method for choosing a subset of the rows so as to ensure that
the resulting matrix satisfies the RIP. Finally, in [11], the authors interpret an earlier paper [12] to
show that a suitably constructed “chirp” matrix satisfies the RIP. The number of measurements
in both [9] and [10] is the same, and equals q 2 where q is an appropriately chosen prime number.
In the chirp matrix method [12], the number of measurements equals q where q is an appropriately
chosen prime number.
The main criticism of deterministic methods for constructing measurement matrices is that
m = O(n1/2 ), compared to m = O(k log(n/k)) for probabilistic methods. However, as shown in
the Appendix, the O symbol hides a huge constant. Table 7 in the Appendix shows the number of
measurements required by both the probabilistic as well as deterministic methods. From this table
it can be seen that deterministic methods require fewer measurements than probabilistic methods
in most realistic situations. For this reason, in our numerical experiments we use only deterministic
construction methods.
Note that any algorithm based on ℓ1 -norm minimization will never recover a sparse vector
exactly. This is because any implementation of ℓ1 -norm minimization will make use of some convex
optimization algorithm, which will be iterative in nature, and will stop when some termination
4

criterion is satisfied. As a consequence, the recovered vector x̂ will be close to but never exactly
equal to the true vector x. Moreover, the recovered vector x̂ is not necessarily k-sparse, nor is it
the case that (x̂)d ≈ xd . In other words, ℓ1 -norm minimization is not guaranteed to recover the
dominant part of the unknown vector x. In contrast, the algorithm proposed here does do so, under
suitable conditions.

1.4

Compressive Sensing Using Expander Graphs

A recent development is the application of ideas from algebraic coding theory to compressive
sensing. In [13], a method called “sudocodes” is proposed, which is based on low density parity check
(LDPC) codes, which are well-established in coding theory. The sudocodes method can recover
sparse signals with high probability. Motivated by this method, Xu and Hassibi in [14] proposed a
method based on expander graphs, which are a special type of bipartite graph. The measurement
matrix used in [14] is the biadjacency matrix of an expander graph with an expansion factor of 3/4
or more,2 and is therefore binary. Using such a binary measurement matrix, in [14] an iterative
algorithm is proposed for updating the estimate x̂ component by component. It is shown in [14] that
every k-sparse n-dimensional vector can be recovered exactly in O(k log n) iterations. In [15], the
authors improve upon the Xu-Hassibi algorithm by using expander graphs with an expansion factor
of 1 − ǫ, where ǫ ≤ 1/4. With this modification, it is shown in [15] that a k-sparse n-dimensional
vector can be recovered in 2k or fewer iterations. However, making the “expansion factor” closer
and closer to 1 increases the number of required measurements. A key issue in applying these
algorithms is the construction of expander graphs with the requisite expansion factor. In both [14]
and [15] the authors use Hoeffding’s inequality to show that randomly generated bipartite graphs
are indeed expanders, and use randomly generated bipartite graphs in their numerical examples,
without ascertaining whether they are actually expanders or not. Therefore the numerical examples
given in [14, 15] do not correspond to the theory, strictly speaking.

2

The New Algorithm

We present straightaway our new algorithm, and show that it can exactly recover sparse signals
in a single pass, without any iterations. Then we compare its performance with those of existing
algorithms in subsequent sections.

2.1

The New Algorithm

Suppose a matrix A ∈ {0, 1}m×n has the following properties, referred to as the main assumption:
1. Every column aj of A has precisely q entries of 1 and m − q entries of 0.
2. If aj , at are distinct columns of A, then haj , at i ≤ r − 1.
Suppose x ∈ Σk is a k-sparse n-dimensional vector, and define y = Ax to be the measurement
vector. For a given index j ∈ [n], let {v1 (j), . . . , vq (j)} ⊆ [m] denote the q rows such that aij = 1.
For an index j ∈ [n], the reduced measurement vector ȳj ∈ Rq is defined as
ȳj := [yv1 (j) . . . yvq (j) ]⊤ .

The main result is given next. Note that we use the standard notation kvk0 to denote the
number of nonzero components of a vector v.
2

These terms are defined precisely in subsequent sections.

5

Theorem 3 Suppose x ∈ Σk , y = Ax. Then:
1. If j 6∈ supp(x), then kȳj k0 ≤ k(r − 1).
2. If j ∈ supp(x), then ȳj contains at least q − (k − 1)(r − 1) components that are all equal to xj .
Proof: For t ∈ [n], let et ∈ Rn denote the t-th canonical basis vector, which has a 1 as its
t-th element, and zeros elsewhere, and let 1q ∈ Rq denote the column vector consisting of all ones.
Then we can write:
X
x=
xt et ,
t∈supp(x)
X
X
y = Ax =
xt Aet =
xt at ,
t∈supp(x)
t∈supp(x)
where at denotes the t-th column of A. Therefore, for a fixed j ∈ [n] and l ∈ [q], we have that
X
yvl (j) =
xt (at )vl (j) .
t∈supp(x)
Letting l range over [q] shows that
ȳj =

X

xt (at )j ,

(8)

t∈supp(x)

where (at )j is the reduced vector of at consisting of (at )v1 (j) , . . . , (at )vq (j) .
Proof of (1): Suppose j 6∈ supp(x). Then j 6= t for all t ∈ supp(x). Therefore, according to
item (ii) of the main assumption, we have that haj , at i ≤ r − 1. Recall that v1 (j), . . . , vq (j) are
the row indices of column j that contain a 1. Therefore, for a fixed index t 6= j, the number of 1’s
in the set {(at )v1 (j) , . . . , (at )vq (j) } equals the inner product haj , at i and thus cannot exceed r − 1.
Therefore, for a fixed index t ∈ supp(x), the vector xt (at )j contains no more than r − 1 nonzero
entries. Substituting this fact into (8) shows that ȳj is the sum of at most k vectors (because x is
k-sparse), each of which has no more than r − 1 nonzero entries. Therefore kȳj k0 ≤ k(r − 1).
Proof of (2): Suppose j ∈ supp(x). Then we can write
X
ȳj =
xt (at )j
(9)
t∈supp(x)
X
= xj 1q +
xt (at )j ,
(10)
t∈supp(x)\{j}
because the “reduced vector” (aj )j consists of q 1’s, as denoted by 1q . By the same reasoning as
in the proof of (1), it follows that
X

≤ (k − 1)(r − 1).

xt (at )j

t∈supp(x)\{j}

0

Therefore at least q − (k − 1)(r − 1) terms in ȳj equal xj .

In view of Theorem 3, we can formulate an algorithm for the recovery of k-sparse vectors, as
follows:
Note that there is no iterative process involved in the recovery – the estimate x̂ is generated
after a single pass through all n indices.
6

New Recovery Algorithm
1: for j ∈ [n] do
2:
Construct the reduced measurement vector ȳj .
3:
Find the number of the elements of ȳj that are nonzero; call it ν.
⊲ (In implementation,
we find the number of elements that are greater than some tolerance δ.)
4:
if ν > q/2 then
5:
Find a group of q/2 elements in ȳj that are equal; call this value θj .
⊲ (In
implementation, we allow some tolerance here.)
6:
x̂j = θj .
7:
else
8:
x̂j = 0
end
10: end
9:

Theorem 4 If x is k-sparse, and A satisfies the main assumption with q > 2k(r − 1), then x̂ = x.
Proof: Note q > 2k(r − 1) implies that
k(r − 1) < q/2, q − (k − 1)(r − 1) > q − k(r − 1) > q/2.
Therefore, by Statement 1 of Theorem 3, it follows that if j 6∈ supp(x), then kȳj k0 ≤ k(r −1) < q/2.
Taking the contrapositive shows that if kȳj k0 ≥ q/2, then j ∈ supp(x). Therefore, by Statement 2
of Theorem 3, it follows that at least q − (k − 1)(r − 1) > q − k(r − 1) > q/2 elements of ȳj equal
xj .

Next we present the extension of our basic algorithm to the cases of a sparse signal with
measurement noise, and a nearly sparse signal.

2.2

Recovery of Sparse Signals with Measurement Noise

In previous work, the model for noisy measurements is that y = Ax + η where there is a prior
bound of the form kηk2 ≤ ǫ. If x ∈ Σk , then σk (x, k · k1 ) = 0. Therefore, if robust sparse recovery is
achieved, then the bound in (4) becomes kx̂−xk2 ≤ Dǫ. However, our approach draws its inspiration
from coding theory, wherein it is possible to recover a transmitted signal correctly provided the
transmission is not corrupted in too many places. Therefore our noise model is that kηk0 ≤ M .
In other words, it is assumed that a maximum of M components of the “true” measurement Ax
are corrupted by additive noise, but there are no assumptions regarding the magnitude of the error
signal η. In this case it is shown that, by increasing the number of measurements, it is possible to
recover the true sparse vector x perfectly.
Theorem 5 Suppose x ∈ Σk , and that y = Ax + η where kηk0 ≤ M . Suppose further that the
matrix A satisfies the main assumption. Then
1. If j 6∈ supp(x), then ȳj contains no more than k(r − 1) + M nonzero components.
2. If j ∈ supp(x), then ȳj contains at least q − [(k − 1)(r − 1) + M ] components that are all equal
to xj .
3. Suppose the new recovery algorithm is applied with a measurement matrix A that satisfies the
main assumption with q > 2[k(r − 1) + M ]. Then x̂ = x.
7

Proof: Suppose x ∈ Σk and let y = Ax+η where A satsfies the main assumption and kηk0 ≤ M .
Let u = Ax denote the uncorrupted measurement. For a fixed index j ∈ [n], let ȳj ∈ Rq denote the
reduced measurement vector, consisting of the components yv1 (j) through yvq (j) , and define ūj ∈ Rq
and η̄j ∈ Rq analogously.
First suppose j 6∈ supp(x). Then it follows from Item (1) of Theorem 3 that kūj k0 ≤ k(r − 1).
Moreover, because η has no more than M nonzero components and η̄j is a subvector of η, it follows
that kη̄j k0 ≤ M . Therefore
kȳj k0 = kūj + η̄j k0 ≤ kūj k0 + kη̄j k0 ≤ k(r − 1) + M.
This is Item (1) above. Next, suppose that j ∈ supp(x). Then it follows from Item (1) of Theorem
3 that at least q − (k − 1)(r − 1) elements of ūj equal xj . Because kη̄j k0 ≤ M , it follows that
at least q − (k − 1)(r − 1) − M components of ȳj equal xj . This is Item (2) above. Finally, if
q > 2k(r − 1) + 2M , it follows as in the proof of Theorem 4 that x̂ = x.

Note that the assumption on the noise signal η can be modified to kη̄j k0 ≤ M for each j ∈ [n].
In other words, instead of assuming that η has no more than M nonzero components, one can
assume that every reduced vector η̄j has no more than E nonzero components.

2.3

Recovery of Nearly Sparse Signals

As before, if x 6∈ Σk , then let xd ∈ Rn denote the projection of x onto its k largest components, and
let xr = x − xd . We refer to xd , xr as the dominant part and the residual respectively. Note that,
for any p ∈ [1, ∞], we have that the sparsity index σk (x, k · kp ) equals kxr kp . To (nearly) recover
such a vector, we modify the New Recovery Algorithm slightly. Let δ be a specified threshold.
Modified Recovery Algorithm
1: for j ∈ [n] do
2:
Construct the reduced measurement vector ȳj .
3:
Find the number of the elements of ȳj that are greater than δ in magnitude; call it ν.
4:
if ν > q/2 then
5:
Find a group of q/2 elements in ȳj such that the difference between the largest and
smallest elements is no larger than 2δ; Let θj denote the average of these numbers.
6:
x̂j = θj .
7:
else
8:
x̂j = 0
9:
10:

end
end

Theorem 6 Suppose x ∈ Rn and that σk (x, k·k1 ) ≤ δ. Write x = xd +xr where xd is the dominant
part of x consisting of its k largest components, and xr = x − xd is the residual. Let y = Ax where
A satisfies the main assumption with q > 2k(r − 1), and apply the modified recovery algorithm.
Then (i) supp(x̂) = supp(xd ), and (ii) kx̂ − xd k∞ ≤ δ.
Proof: Write x = xd + xr where xd consists of the dominant part of x and xr consists of the
residual part. By assumption, kxr k1 ≤ δ. Note that the measurement y equals Ax = Axd + Axr .
Let u = Axd and observe that xd ∈ Σk . Further, observe that, because the matrix A is binary, we
8

have that the induced matrix norm
kAk1→∞ := sup
v6=0

kAvk∞
= max |aij | = 1.
i,j
kvk1

Therefore kAxr k∞ ≤ kxr k1 ≤ δ. Now, by Item (1) of Theorem 3, we know that if j 6∈ supp(xd ),
then no more than k(r − 1) components of the reduced vector ūj are nonzero. Therefore then no
more than k(r − 1) components of the reduced vector ȳj have magnitude more than δ. By Item (2)
of Theorem 3, we know that if j ∈ supp(xd ), then at least q − (k − 1)(r − 1) components of ūj equal
xj . Therefore at least q − (k − 1)(r − 1) components of ȳj lie in the interval [xj − δ, xj + δ]. Finally, if
q > 2k(r − 1), then there is only one collection of q − (k − 1)(r − 1) > q/2 components of the reduced
vector ȳj that lie in an interval of width 2δ. The true xj lies somewhere within this interval, and
we can set x̂j equal to the midpoint of the interval containing all of these components. In this case
|x̂j − xj | ≤ δ. Because this is true for all j ∈ supp(xd ), it follows that (i) supp(x̂) = supp(xd ), and
(ii) kx̂ − xd k∞ ≤ δ.

Finally, it is easy to combine the two proof techniques and to establish the following theorem
for the case where x is not exactly sparse and the measurements are noisy.
Theorem 7 Suppose x ∈ Rn and that σk (x, k·k1 ) ≤ δ. Write x = xd +xr where xd is the dominant
part of x consisting of its k largest components, and xr = x − xd is the residual. Let y = Ax + η
where kηk0 ≤ M , and A satisfies the main assumption with q > 2k(r − 1) + 2M . Apply the modified
recovery algorithm. Then (i) supp(x̂) = supp(xd ), and (ii) kx̂ − xd k∞ ≤ δ.

2.4

Construction of a Binary Measurement Matrix

The results presented until now show that the key to the procedure is the construction of a binary
matrix A that satisfies the main assumption. In this subsection, it is shown that previous work by
DeVore [9] provides a simple recipe for constructing a binary matrix with the desired properties.
Note that [9] was the first paper to propose a completely deterministic procedure for constructing
a matrix that satisfies the restricted isometry property. Therefore the reinterpretation of this
construction to achieve sparse recovery in a highly efficient manner is one of the contributions of
the present paper. We now describe the construction in [9].
Suppose q is a prime number. Then Fq denotes the set {0, 1, . . . , q − 1} with arithmetic modulo
q, and is a field. If q = ps where p is a prime number and s > 1, then it is possible to define a finite
field Fq with q elements by identifying an irreducible polynomial ψ of degree s with coefficients
in Fp , and then doing arithmetic on the polynomial ring Fp [z] modulo ψ(z). Note that for rapid
implementation in Matlab, we would choose q to be a prime number, in which case Fq denotes the
set {0, 1, . . . , q − 1} with arithmetic modulo q. However, the theory itself is applicable even to the
case where q is a power of a prime number but not a prime number.
Suppose a is a polynomial of degree r − 1 or less with coefficients in Fq , and define its “graph”
2
as the set of all pairs (x, a(x)) as x varies over Fq . Now construct a vector ua ∈ {0, 1}q ×1 by
setting the entry in row (i, j) to 1 if j = a(i), and to zero otherwise. To illustrate, suppose q = 3,
r = 4, and that a(x) = 1 + 2x + x2 + x3 . Because q is a prime number, the associated field Fq is just
{0, 1, 2} with arithmetic modulo 3. Therefore a(0) = 1, a(1) = 2, and a(2) = 2. The corresponding
9 × 1 column vector has 1’s in positions (0, 1), (1, 2), (2, 2) and zeros elsewhere. This construction
results in a q 2 × 1 column vector ua that contains q elements of 1 and the rest equal to zero. In
fact the column vector has even more structure, though we do not make use of it. The vector ua
consists of q blocks of size q × 1, each of which contains a single 1 and q − 1 zeros.
9

Now let Πr−1 (Fq ) denote the set of all polynomials of degree r − 1 or less with coefficients in
Fq . In other words,
)
(
r−1
X
i
ai x , ai ∈ Fq .
Πr−1 (Fq ) := a(x) =
i=0

Note that Πr−1 (Fq ) contains precisely
q different values.3 Now define

qr

polynomials, because each of the r coefficients can assume

A := [ua , a ∈ Πr−1 (Fq )] ∈ {0, 1}q

2 ×q r

.

(11)

The following theorem shows that the matrix A constructed as above satisfies the main assumption.
Theorem 8 (See [9, Theorem 3.1]) For the matrix A ∈ {0, 1}q

2 ×q r

defined in (11), we have that

hua , ub i ≤ r − 1

(12)

whenever a, b are distinct polynomials in Πr−1 (Fq ).
Theorem 8 suggests the following procedure for constructing a binary matrix that satisfies the
conditions of Theorem 4. Given integers k and n with k ≪ n, choose a prime number q and an
2
r
integer r ≥ 3 such that q > 2k(r − 1) and q r ≥ n. Construct a binary matrix A ∈ {0, 1}q ×q as in
(11), and then retain any n columns of this matrix, which we continue to refer to as A. Theorem 4
can be applied using this matrix. Note that the two inequalities q > 2k(r − 1) and q r ≥ n provide
lower bounds on q. An upper bound is provided by the requirement that q 2 ≤ n, so that the
number of measurements m does not exceed n.

3

Compressive Sensing Using Expander Graphs

In the previous section it was shown that the construction of a binary matrix satisfying the main
assumption can be interpreted in terms of the restricted isometry property. One of the objectives
of this section is to show that the main assumption can also be interpreted in terms of expander
graphs. This permits us to compare our algorithm with other algorithms in the literature based on
expander graphs.

3.1

Basics of Expander Graphs

Expander graphs are the subject of much recent investigation in the compressive sensing literature.
In this section we give a brief overview that covers only those aspects that are relevant to compressive sensing. We deal with undirected bipartite graphs, consisting of a set VI of input vertices,
a set VO of output vertices, and an edge set E ⊆ VO × VI , where (i, j) ∈ E if and only if there is
an edge between node i ∈ VO and node j ∈ VI . The corresponding matrix A ∈ {0, 1}|VO |×|VI | is
called the biadjacency matrix of the bipartite graph. The graph is said to be left-regular of
degree D, or D-left regular, if every input node has degree D. This is equivalent to requiring
that every column of the biadjacency matrix A has exactly D elements equal to 1. Given an input
vertex j ∈ VI , let N (i) ⊆ VO denote the set of its neighbors, defined as
N (j) := {i ∈ VO : (i, j) ∈ E}.
3

If the leading coefficient of a polynomial is zero, then the degree would be less than r.

10

Given set of input vertices S ⊆ VI , the set of its neighbors N (S) ⊆ VO is defined as
[
N (S) :=
N (j) = {i ∈ VO : ∃j ∈ S s.t. (i, j) ∈ E}.
j∈S

Definition 3 A D-left regular bipartite graph (VI , VO , E) is said to be a (K, 1 − β)-expander for
some integer K and some number β ∈ (0, 1) if, for every S ⊆ VI with |S| ≤ K, we have that
|N (S)| ≥ (1 − β)D|S|.
In [14], Xu and Hassibi introduce a new signal recovery algorithm in which the bi-adjacency
matrix of an expander graph with β ≤ 1/4 is used as the measurement matrix. It is referred to
here as the “Expander Recovery Algorithm”. Xu and Hassibi show that their algorithm recovers
an unknown k-sparse vector x exactly in O(k log n) iterations. Subsequently, their method was
updated in [15] by increasing the expansion factor from 1 − 1/4 = 3/4 to 1 − ǫ in which ǫ < 14 .
With this change, it is shown that the number of recovery iterations required is O(k). However,
the number of measurements is more than in the Xu-Hassibi algorithm.
Expander Recovery Algorithm
1: Initialize x − 0n×1
2: if Y = Ax then return output x and exit
3: else
4: find a variable xj such that at least (1 − 2ǫ)D of the measurements it participates in have
identical gap g
5: xj ← xj + g and go to step 2
6: end if

3.2

Construction of Expander Graphs

The Expander Recovery Algorithm depends on using the biadjacency matrix of a left-regular expander graph as the measurement matrix. It is known that randomly generated left-regular graphs
are expanders with high probability. However, given a graph with n input nodes, it requires O(nK )
operations to determine whether a particular (possibly randomly generated) left-regular graph is,
or is not, a (K, A) expander. Therefore in both [14] and [15] the authors simply use randomly
generated graphs without checking whether they are expanders.
However, there are explicit construction methods that are guaranteed to produce an expander
graph. One such procedure is given in [16, Section 3]. Since it is germane to our method, it is
described here without proof.
Let q be a prime number or a power of a prime number. Let Fq denote the finite field with
q elements. For fixed integers r and s, the bipartite graph has Frq as the set of input vertices VI ,
and Fs+1
as the set of output vertices. Let E(Y ) be any irreducible polynomial of degree r with
q
coefficients in Fq . Then we can identify Frq with the set of all polynomials of degree r − 1 or less in
some indeterminate Y , with coefficients in the field Fq . Addition and subtraction of polynomials
is done in the usual manner, while multiplication is modulo E(Y ). In particular, if φ(Y ) is a
polynomial of degree r − 1 or less, and j is any integer, then φj (Y ) is interpreted modulo E(Y )
and is thus another polynomial of degree r − 1 or less, and thus belongs to Frq .
The construction in [16] is as follows: Let h ≥ 2 be any integer. Then the map Γ : Frq ×Fq → Fs+1
is defined as
s−1
2
(13)
Γ(f, y) := [y, f (y), f h (y), f h (y), . . . , f h (y)].
11

An alternate way to express the function Γ is:
i

Γ(f, y) = [y, (f h (y), i = 0, . . . , s − 1)].
In the definition of the function Γ, y ranges over Fq as the “counter,” and the above graph is
left-regular with degree q. The set of input vertices is Frq , consisting of polynomials in some
indeterminate Y with coefficients in Fq of degree no larger than r − 1. The set of input vertices
has cardinality q r . The set of output vertices is Fs+1 and each output vertex is an (s + 1)-tuple
consisting of elements from Fq . The set of output vertices has cardinality q s+1 . Note that the graph
is q-left regular in that every input vertex has exactly q outgoing edges.
Theorem 9 (See [16, Theorem 3.3].) For every pair of integers h, s, the bipartite graph defined in
(13) is a (hs , 1 − β)-expander with
β=

(r − 1)(h − 1)s
.
q

(14)

Now we relate the construction of DeVore with that in [16].
Theorem 10 The matrix A constructed in [9] is a special case of the graph in Theorem 9 with
s = 1, and any value for h.
Proof: Suppose that s = 1 and that h is any integer. In this case each polynomial f with
coefficients in Fq of degree r − 1 or less gets mapped into the pair (y, f (y)) as y ranges over Fq .
This is precisely what was called the “graph” of the polynomial f in [9].


4

Computational Results

Theorems 8 and 10 show that the measurement matrix proposed by us (based on DeVore’s construction) falls within the ambit of both the restricted isometry property as well as expander graphs.
√
Specifically, it follows from (12) that the column-normalized matrix A′ = (1/ q)A satisfies the
RIP of order k with constant δk = (k − 1)(r − 1)/p. Hence this matrix can be used together with
ℓ1 -norm minimization to achieve compressive sensing. Moreover, because the matrix A satisfies the
main assumption, it can also be used in our new algorithm. In this section, we compare the computational performance of our new algorithm with ℓ1 -norm minimization as well as the Xu-Hassibi
algorithm.

4.1

Number of Measurements Required by Various Methods

In this subsection we compare the number of measurements required by ℓ1 -norm minimization,
expander graphs, and our method.
In ℓ1 -norm minimization, as shown in Theorem 8, the matrix A, after column normalization
√
dividing each column by q, satisfies the RIP with constant δk = (k − 1)(r − 1)/q. Combined with
Theorem 1, we conclude that ℓ1 -norm minimization with the DeVore construction achieves robust
k-sparse recovery whenever
r
t−1
(⌈tk⌉ − 1)(r − 1)
<
.
(15)
q
t

12

Method
Bound: q ≥
Bound: m ≥
q with k = 6
m with k = 6

ℓ1 -norm
Min.
6k
36k2
37
1,369

Expander
Graphs
8(2k − 1)
64(2k − 1)2
89
7,921

New
Alg.
4k
16k2
29
841

Table 1: Number of Measurements for Various Approaches
To maximize the value of k for which the above inequality holds, we set r to its minimum permissible
value, which is r = 3. Also, we replace ⌈tk⌉ − 1 by its upper bound tk, which leads to
r
r
2tk
2k
t−1
t−1
<
, or
<
.
q
t
q
t3
Elementary calculus shows that the right side is maximized when t = 1.5. So the RIP constant of
the measurement matrix must satisfy
p
√
δtk < (t − 1)/t = 1/ 3 ≈ 0.577.

Let us choose a value of 0.5 for δtk to give some “cushion.” Substituting the values t = 1.5, r = 2
in (15) and ignoring the rounding operations finally leads to the condition
3k
< 0.5, or q > 6k.
q

(16)

For expander graphs, we can calculate the expansion factor 1 − ǫ from Theorem 9. This gives
ǫ=

(r − 1)(h − 1)s
.
q

Since we wish the expansion factor 1 − ǫ to be as close to one as possible, or equivalently, ǫ to be
as small as possible, we choose s to be its minimum value, namely s = 1. Now we substitute r = 3,
h = 2k (following [14]), and set 1 − ǫ ≥ 3/4, or equivalently ǫ ≤ 1/4. This leads to
2(2k − 1)
≤ 1/4, or q ≥ 8(2k − 1).
q
Finally, for the new algorithm, it has already been shown that q ≥ 2(r − 1)k = 4k. Therefore
the required number of measurements for each of the three algorithms are as shown in Table 1.
Note that, since the matrix A has q 3 columns, we must also have that n ≤ q 3 .

4.2

Numerical Examples

In this section we present a numerical example to compare the three methods. We chose n = 20, 000
to be the dimension of the unknown vector x. Since all√three methods produce a measurement
matrix with m = q 2 rows, we must have q < 141 ≈ 20000, because otherwise the number
of measurements would exceed the dimension of the vector! Since the expander graph method
requires the most measurements, the sparsity count k must satisfy 8(2k − 1) < 141, which gives
k ≤ 9. However, if we try to recover k-sparse vectors with k = 9 using the expander graph method,
13

k
6
9
10
12
15
16
17
18
20
32
33
70
79
80
208

Exp. Graph Method
Error Time Rec.
0
76
100
0
122
100
0
136
100
0
153
100
0
158
100
0
212
100
0
232
100
0
246
100
0
273
100
0
438
100
≈0
452
80
≈0
958
0
≈0
1072
0
4.12
1577
0
8.49
1733
0

New
Err.
0
0
0.0121
0.0672
0.5818
1
1.0327
1.3179
1.6910
3.1917
3.2620
4.8240
5.1545
5.1472
8.3321

Algorithm
Time Rec.
0.0951
100
0.096
100
0.1045
98
0.1446
80
0.1348
27
0.1325
11
0.2403
0
0.1191
0
0.1380
0
0.2406
0
0.2378
0
0.1334
0
0.1320
0
0.1445
0
0.1533
0

Table 2: Recovery error and the processing time of the expander graph and our new recovery algorithms. The expander graph algorithm used 892 = 7, 921 measurements while the new algorithm
used 292 = 841 measurements. The column REC shows the number of correctly recovered vectors.
the number of measurements m would be essentially equal to the dimension of the vector n. Hence
we chose value of k = 6. With this choice, the values of q and the number of measurements are
shown in Table 1. Note that q must be chosen as a prime number.
Having chosen the values of n and k, we generated 100 different k-sparse n-dimensional vectors,
with both the support set of size k and the nonzero values of x generated at random.4 As expected,
both the expander graph method and the new algorithm recovered the unknown vector x exactly
in all 100 cases. The ℓ1 -norm minimization method recovers x with very small error.
Next, we examined how close the sufficient conditions in Table 1 are to being necessary. So
for this purpose, we retained n at 20, 000 and retained the binary measurement matrix A that is
appropriate for each method, increased k from 6 to ever-larger numbers, and noted how many of
the 100 randomly generated vectors were recovered using each method. Note that the number of
measurements for each method was as shown in Table 1. Thus the number of measurements for
the expander graph method was roughly ten times that for our approach. The results are shown in
Tables 2 and 3. It is important to note that the number of measurements with the new algorithm
is roughly 10% of those used in the expander graph algorithm, and roughly 60% of those used in
ℓ1 -norm minimization.
Next, to make a “like to like” comparison, we ran the Xu-Hassibi algorithm and the new
algorithm with the same number of measurements, namely m = 892 = 7, 921, and compared their
performance. Note that q = 89 is the smallest value of q to satisfy the constraints for the Xu and
Hassibi expander recovery algorithm with k = 6. The results are shown in Table 4. From this table,
it can be seen that for the same number of measurements, our new algorithm achieves complete
recovery for higher values of k compared to Xu and Hassibi expander recovery algorithm (k = 39
4

Matlab codes are available from the authors.

14

k
6
9
10
12
15
16
17
18
20
32
33
70
79
80
208
209

ℓ1 -Norm Min.
Err.
Time
≈0
21.09
≈0
15.89
≈0
17.33
≈0
18.66
≈0
24.60
≈0
23.71
≈0
19.40
≈0
16.26
≈0
31.80
≈0
16.83
≈0
14.51
≈0
27.25
≈0
26.58
≈0
29.47
≈0
50.94
0.1342 34.75

New
Error
0
0
0.0121
0.0672
0.5818
1
1.0327
1.3179
1.6910
3.1917
3.2620
4.8240
5.1545
5.1472
8.3321
8.3168

Algorithm
Time Rec.
0.0951
100
0.096
100
0.1045
98
0.1446
80
0.1348
27
0.1325
11
0.2403
0
0.1191
0
0.1380
0
0.2406
0
0.2378
0
0.1334
0
0.1320
0
0.1445
0
0.1533
0
0.1191
0

Table 3: Recovery error and the processing time of the l1 -norm minimization and our new recovery
algorithms. The ℓ1 -norm minimization algorithm used 372 = 1, 369 measurements while our algorithm used 292 = 841 measurements. The column REC shows the number of correctly recovered
vectors.
versus k = 33). Moreover, the computation time is one-thousandth of the time required by the
expander recovery algorithm. If we compare the results in Table 2 and Table 4, we see that by
increasing the value of q in our algorithm, we are able to achieve exact recovery for higher values
of k (38 versus 32) compared to the expander graph algorithm.
Similarly, we ran ℓ1 -norm minimization and the new algorithm with the same number of measurements, namely m = 372 = 1, 369, and compared their performance. The results are shown in
Table 5. We have already seen from Table 3 that with q = 37, ℓ1 -norm minimization achieves exact
recovery for far higher values of k than our new algorithm with q = 29. When q is increased to
37 in our algorithm, the same situation persists as can be seen from Table 5. However, the computational time of our algorithm continues to be far smaller than that for ℓ1 -norm minimization,
roughly one-hundredth.
As a final example, we introduced measurement noise into the output. As per Theorem 5,
if y = Ax + η where kηk0 ≤ M , then it is still possible to recover x exactly by increasing the
prime number q. Note that the only thing that matters here is the number of nonzero components
of the noise η, and not their magnitudes. One would expect that, if the norm of the noise gets
larger and larger, our algorithm would continue to recover the unknown sparse vector exactly, while
ℓ1 -norm minimization would not be able to. In other words, our algorithm is tolerant to “shot”
noise whereas ℓ1 -norm minimization is not. The computational results bear this out. We choose
n = 20, 000 and k = 6 as before, and M = 6, so that we perturb the true measurement Ax in six
locations. Specifically we chose η = αv where each component of v is normally distributed, and
then increased the scale factor α. Each experiment was repeated with 100 randomly generated

15

k
6
9
20
32
33
38
39

Expander Graph Method
Error
Time Rec.
0
76.75
100
0
122.98 100
0
273.24 100
0
438.24 100
6.0666e-17 452.84
80
1.4415e-16 487.99
45
1.3761e-16 497.89
45

New Method
Error
Time Rec.
0
0.1360 100
0
0.1304 100
0
0.1418 100
0
0.2004 100
0
0.1345 100
0
0.1394 100
0.0068 0.1484
99

Table 4: Recovery error and the processing time of the Expander recovery algorithm and our
new recovery algorithm using 892 = 7, 921 measurements. The column REC shows the number of
correctly recovered vectors.

k
6
7
9
12
13
15

ℓ1 -norm minimization
Error
Time
1.044e-09
21.09
5.5505e-08
22.92
1.5985e-09
15.89
2.314e-08
18.66
1.0329e-07
26.59
1.135e-08
24.60

New Method
Error
Time Rec.
0
0.1345 100
0
0.0851 100
0
0.1117 100
0
0.1251 100
0.0046 0.1443
99
0.0330 0.1155
91

Table 5: Recovery error and the processing time of the ℓ1 -norm minimization and our new recovery
algorithms using 372 = 1, 369 measurements. The column REC shows the number of correctly
recovered vectors.

16

Alpha
10−5
10−4
10−3
10−2
10−1
10
20

New Algorithm
Err. Time Rec.
0
0.1335 100
0
0.1325 100
0
0.1336 100
0
0.1357 100
0
0.1571 100
0
0.1409 100
0
0.1494 100

ℓ1 -norm minimization
Err.
Time Rec.
3.2887e-06 26.8822
0
3.2975e-05 26.6398
0
3.3641e-04 28.1876
0
0.0033
23.1727
0
0.033
28.9145
0
1.3742
26.6362
0
1.3967
26.5336
0

Table 6: Performance of new algorithm and ℓ1 -norm minimization with additive shot noise
sparse vectors and shot noise. The results are shown in Table 6.

5

Discussion and Conclusions

In this paper we have presented a new algorithm for compressive sensing that makes use of binary
measurement matrices and achieves exact recovery of sparse vectors, without any iterations. Exact
recovery continues to hold even when the measurements are corrupted by a noise vector with a
sufficiently small support set; this noise model is reminiscent of the model used in algebraic coding.
When the unknown vector is not exactly sparse, but is nearly sparse with a sufficiently small
residual, our algorithm exactly recovers the support set of the dominant components, and finds an
approximation for the dominant part of the unknown vector. Because our algorithm is noniterative,
it executes orders of magnitude faster than algorithms based on ℓ1 -norm minimization and methods
based on expander graphs (both of which require multiple iterations). Moreover, our method
requires the fewest measurements amongst all methods that use binary measurement matrices.
On test examples of k-sparse n-dimensional vectors with k = 6 and n = 20, 000, our algorithm
executes roughly 1, 000 times faster than the Xu-Hassibi algorithm [14] based on expander graphs,
and roughly 200 times faster than ℓ1 -norm minimization.
On the other hand, these two methods do have their own advantages over the algorithm proposed
here. The Xu-Hassibi algorithm [14] and its extension in [15] can be used with any expander graph
with an expansion factor that is sufficiently close to one. In contrast, our algorithm makes use of
a particular family of expander graphs whose biadjacency matrix satisfies the “main assumption.”
Similarly, if ℓ1 -norm minimization is used to reconstruct a vector, then a bound of the form (4)
holds no matter what the unknown vector is. In contrast, our error bounds require that the residual
part of the unknown vector must be sufficiently small compared to the dominant part of the vector.
This might not be a serious drawback however, because the objective of compressed sensing is to
recover nearly sparse vectors, and not arbitrary vectors.
Computational results also show that ℓ1 -norm minimization continues to recover the unknown
vector for far larger values of k than our method. Whereas we designed the measurement matrix
for k = 6, ℓ1 -norm minimization achieved sparse recovery up to k = 208. In contrast, our method
worked only for k up to 9. This suggests that our sufficient condition that provides a bound on k
is nearly tight, which is good. This also suggests that the known sufficient conditions for ℓ1 -norm
minimization to achieves robust sparse recovery, namely those based on the restricted isometry
property (RIP), are overly conservative and can be improved. Therefore an interesting area for

17

further research is to find alternate sufficient conditions that are not based on the RIP for ℓ1 -norm
minimization to achieve robust sparse recovery.

Appendix
In this appendix, we compare the number of measurements used by probabilistic as well as deterministic methods to guarantee that the corresponding measurement matrix A satisfies the restricted
isometry property (RIP), as stated in Theorem 1. Note that the number of measurements is computed from the best available sufficient condition. In principle it is possible that matrices with
fewer rows might also satisfy the RIP. But there would not be any theoretical justification for using
such matrices.
In probabilistic methods, the number of measurements m is O(k log(n/k)). However, in reality
the O symbol hides a huge constant. It is possible to replace the O symbol by carefully collating
the relevant theorems in [1]. This leads to the following explicit bounds.
Theorem 11 Suppose X is a random variable with zero mean, unit variance, and suppose in
addition that there exists a constant c such that5
E[exp(θX)] ≤ exp(cθ 2 ), ∀θ ∈ R.

(17)

γ = 2, ζ = 1/(4c), α = γe−ζ + eζ , β = ζ,

(18)

Define

c̃ :=

β2
.
2(2α + β)

(19)

√
Suppose an integer k and real numbers δ, ξ ∈ (0, 1) are specified, and that A = (1/ m)Φ, where
Φ ∈ Rm×n consists of independent samples of X. Then A satisfies the RIP of order k with constant
δ with probability ≥ 1 − ξ provided


4
en 14k 4 2
1
k ln
+
+ ln
m≥ 2
.
(20)
c̃δ
3
k
3
3 ξ
In (20), the number of measurements m is indeed O(k log(n/k)). However for realistic values
of n and k, the number of measurements n would be comparable to, or even to exceed, n, which
would render “compressed” sensing meaningless.6 For “pure” Gaussian variables it is possible to
find improved bounds for m (see Also, for binary random variables where X equals ±1 with equal
probability, another set of bounds is available [17]. While all of these bounds are O(k log(n/k)), in
practical situations the bounds are not useful.
This suggests that it is worthwhile to study deterministic methods for generating measurement
matrices that satisfy the RIP. There are very few such methods. Indeed, the authors are aware
of only three methods. The paper [9] uses a finite field method to construct a binary matrix, and
this method is used in the present paper. The paper [10] gives a procedure for choosing rows from
a unitary Fourier matrix such that the resulting matrix satisfies the RIP. This method leads to
the same values for the number of measurements m as that in [9]. Constructing partial Fourier
matrices is an important part of reconstructing time-domain sparse signals from a limited number of
5

Such a random variable is said to be sub-Gaussian. A normal random variable satisfies (17) with c = 1/2.
In many papers on compressed sensing, especially those using Gaussian measurement matrices, the number of
measurements m is not chosen in accordance with any theory, but simply picked out of the air.
6

18

frequency measurements (or vice versa). Therefore the results of [10] can be used in this situation.
In both of these methods, m equals q 2 where q is appropriately chosen prime number. Finally, in
[11] a method is given based on chirp matrices. In this case m equals a prime number q. Note
that the partial Fourier matrix and the chirp matrix are complex, whereas the method in [9] leads
to a binary matrix. In all three methods, m = O(n1/2 ), which grows faster than O(k log(n/k)).
However, the constant under this O symbol is quite small. Therefore for realistic values of k and
n, the bounds for m from these methods are much smaller than those derived using probabilistic
methods.
Table 7 gives the values of m for various values of n and k. Also, while the chirp matrix has
fewer measurements than the binary matrix, ℓ1 -norm minimization with the binary matrix runs
much faster than with the chirp matrix, due to the sparsity of the binary matrix. In view of these
numbers, in the present paper we used DeVore’s construction as the benchmark for the recovery of
sparse vectors.

References
[1] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing.
Verlag, 2013.

Springer-

[2] A. Cohen, W. Dahmen, and R. DeVore, “Compressed sensing and best k-term approximation,”
Journal of the American Mathematical Society, vol. 22(1), pp. 211–231, January 2009.
[3] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,”
SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 33–61, 1999.
[4] ——, “Atomic decomposition by basis pursuit,” SIAM Review, vol. 41, no. 1, pp. 129–159,
2001.
[5] E. J. Candès and T. Tao, “Decoding by linear programming,” IEEE Transactions on Information Theory, vol. 51(12), pp. 4203–4215, December 2005.
[6] D. L. Donoho, “For most large underdetermined systems of linear equations, the minimal
ℓ1 -norm solution is also the sparsest solution,” Communications in Pure and Applied Mathematics, vol. 59(6), pp. 797–829, 2006.
[7] T. Cai and A. Zhang, “Sparse representation of a polytope and recovery of sparse signals and
low-rank matrices,” IEEE Transactions on Information Theory, vol. 60(1), pp. 122–132, 2014.
[8] R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof of the restricted
isometry property for random matrices,” Constructive Approximation, vol. 28, pp. 253–263,
2008.
[9] R. DeVore, “Deterministic construction of compressed sensing matrices,” Journal of Complexity, vol. 23, pp. 918–925, 2007.
[10] G. Xu and Z. Xu, “Compressed sensing matrices from Fourier matrices,” IEEE Transactions
on Information Theory, vol. 61(1), pp. 469–478, January 2015.
[11] L. Applebaum, S. D. Howard, S. Searle, and R. Calderbank, “Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery,” Applied and Computational Harmonic
Analysis, vol. 26, pp. 283–290, 2009.
19

n
104
104
104
104
104
104
105
105
105
105
105
105
106
106
106
106
106
106
106
106
106
106
106
106

k
5
6
7
8
9
10
10
12
14
16
18
20
5
10
15
20
25
30
50
60
70
80
90
100

mG
5,333
5,785
6,674
7,111
7,972
8,396
10,025
11,620
13,190
14,739
16,268
17,781
7,009
11,639
16,730
21,069
25,931
30,116
47,527
55,993
64,335
72,573
80,718
88,781

mSG
28,973
31,780
37,308
40,035
45,424
48,089
57,260
66,988
76,582
86,061
95,441
104,733
38,756
66,431
96,976
123,076
152,373
177,635
283,042
334,440
385,171
435,331
484,992
534,210

mA
3,492
3,830
4,496
4,825
5,474
5,796
6,901
8,073
9,229
10,372
11,502
12,622
4,671
8,006
11,687
14,832
18,363
21,407
34,110
40,304
46,417
52,462
58,447
64,378

mD
841
1,369
1,681
2,209
2,809
3,481
3,481
5,041
6,889
9,409
11,449
16,129
10,201
10,201
10,201
16,129
22,201
32,041
94,249
128,881
175,561
229,441
292,681
358,801

mC
197
257
401
487
677
787
787
1,163
1,601
2,129
2,707
3,371
1,009
1,009
1,949
3,371
5,477
7,753
21,911
31,687
43,271
56,659
71,837
88,807

Table 7: Best available bounds for the number of measurements for various choices of n and
k using both probabilistic and deterministic constructions. For probabilistic constructions, the
failure probability is ξ = 10−9 . mG , mSG , mA denote respectively the bounds on the number of
measurements using a normal Gaussian, a sub-Gaussian with c = 1/2, and a bipolar random
variable and the bound of Achlioptas. For deterministic methods mD denotes the number of
measurements using DeVore’s construction, while mC denotes the number of measurements using
chirp matrices.

20

[12] P. G. Casazza and M. Fickus, “Fourier transforms of finite chirps,” EURASIP Journal of
Applied Signal Processing, p. ID70204, 2006.
[13] S. Sarvotham, D. Baron, and R. G. Baraniuk, “Sudocodes – fast measurement and reconstruction of sparse signals,” in Proceedings of the International Symposium on Information Theory,
2006, pp. 2804–2808.
[14] W. Xu and B. Hassibi, “Efficient compressive sensing with deterministic guarantees using
expander graphs,” in Proceedings of IEEE Information Theory Workshop, Lake Tahoe, 2007.
[15] S. Jafarpour, W. Xu, B. Hassibi, and R. Calderbank, “Efficient compressed sensing using
optimized expander graphs,” IEEE Transactions on Information Theory, vol. 55, no. 9, pp.
4299–4308, 2009.
[16] V. Guruswami, C. Umans, and S. Vadhan, “Unbalanced expanders and randomness extractors
from ParvareshVardy codes,” Journal of the ACM, vol. 56, no. 4, pp. 20:1–20:34, 2009.
[17] D. Achlioptas, “Database-friendly random projections: Johnson-Lindenstrauss with binary
coins,” Journal of Computer and System Sciences, vol. 66, pp. 671–687, 2003.

21

