  Consider the approximate sparse recovery problem: given Ax, where A is a
known m-by-n dimensional matrix and x is an unknown (approximately) sparse
n-dimensional vector, recover an approximation to x. The goal is to design the
matrix A such that m is small and recovery is efficient. Moreover, it is often
desirable for A to have other nice properties, such as explicitness, sparsity,
and discreteness.
  In this work, we show that we can use spectral expander graphs to explicitly
design binary matrices A for which the column sparsity is optimal and for which
there is an efficient recovery algorithm (l1-minimization). In order to recover
x that is close to {\delta}n-sparse (where {\delta} is a constant), we design
an explicit binary matrix A that has m = O(sqrt{{\delta}} log(1/{\delta}) * n)
rows and has O(log(1/{\delta})) ones in each column. Previous such
constructions were based on unbalanced bipartite graphs with high vertex
expansion, for which we currently do not have explicit constructions. In
particular, ours is the first explicit non-trivial construction of a
measurement matrix A such that Ax can be computed in O(n log(1/{\delta})) time.
