## Restricted isometry constants in compressed sensing

##### Abstract

Compressed Sensing (CS) is a framework where we measure data through a non-adaptive linear
mapping with far fewer measurements that the ambient dimension of the data. This is made
possible by the exploitation of the inherent structure (simplicity) in the data being measured.
The central issues in this framework is the design and analysis of the measurement operator
(matrix) and recovery algorithms. Restricted isometry constants (RIC) of the measurement
matrix are the most widely used tool for the analysis of CS recovery algorithms. The addition
of the subscripts 1 and 2 below reflects the two RIC variants developed in the CS literature,
they refer to the ℓ1-norm and ℓ2-norm respectively.
The RIC2 of a matrix A measures how close to an isometry is the action of A on vectors with
few nonzero entries, measured in the ℓ2-norm. This, and related quantities, provide a mechanism
by which standard eigen-analysis can be applied to topics relying on sparsity. Specifically,
the upper and lower RIC2 of a matrix A of size n × N is the maximum and the minimum
deviation from unity (one) of the largest and smallest, respectively, square of singular values of
all (N/k)matrices formed by taking k columns from A. Calculation of the RIC2 is intractable for
most matrices due to its combinatorial nature; however, many random matrices typically have
bounded RIC2 in some range of problem sizes (k, n,N). We provide the best known bound
on the RIC2 for Gaussian matrices, which is also the smallest known bound on the RIC2 for
any large rectangular matrix. Our results are built on the prior bounds of Blanchard, Cartis,
and Tanner in Compressed Sensing: How sharp is the Restricted Isometry Property?, with
improvements achieved by grouping submatrices that share a substantial number of columns.
RIC2 bounds have been presented for a variety of random matrices, matrix dimensions and
sparsity ranges. We provide explicit formulae for RIC2 bounds, of n × N Gaussian matrices
with sparsity k, in three settings: a) n/N fixed and k/n approaching zero, b) k/n fixed and
n/N approaching zero, and c) n/N approaching zero with k/n decaying inverse logarithmically
in N/n; in these three settings the RICs a) decay to zero, b) become unbounded (or approach
inherent bounds), and c) approach a non-zero constant. Implications of these results for RIC2
based analysis of CS algorithms are presented.
The RIC2 of sparse mean zero random matrices can be bounded by using concentration
bounds of Gaussian matrices. However, this RIC2 approach does not capture the benefits of
the sparse matrices, and in so doing gives pessimistic bounds. RIC1 is a variant of RIC2 where
the nearness to an isometry is measured in the ℓ1-norm, which is both able to better capture
the structure of sparse matrices and allows for the analysis of non-mean zero matrices.
We consider a probabilistic construction of sparse random matrices where each column has
a fixed number of non-zeros whose row indices are drawn uniformly at random. These matrices
have a one-to-one correspondence with the adjacency matrices of fixed left degree expander
graphs. We present formulae for the expected cardinality of the set of neighbours for these
graphs, and present a tail bound on the probability that this cardinality will be less than the
expected value. Deducible from this bound is a similar bound for the expansion of the graph
which is of interest in many applications. These bounds are derived through a more detailed
analysis of collisions in unions of sets using a dyadic splitting technique. This bound allows
for quantitative sampling theorems on existence of expander graphs and the sparse random
matrices we consider and also quantitative CS sampling theorems when using sparse non mean-zero
measurement matrices.