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 information-theoretically 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.