Bounds on restricted isometry constants of random matrices

Mihailo Stojnic

Published 2013-06-17, updated 2015-07-16Version 2

In this paper we look at isometry properties of random matrices. During the last decade these properties gained a lot attention in a field called compressed sensing in first place due to their initial use in \cite{CRT,CT}. Namely, in \cite{CRT,CT} these quantities were used as a critical tool in providing a rigorous analysis of $\ell_1$ optimization's ability to solve an under-determined system of linear equations with sparse solutions. In such a framework a particular type of isometry, called restricted isometry, plays a key role. One then typically introduces a couple of quantities, called upper and lower restricted isometry constants to characterize the isometry properties of random matrices. Those constants are then usually viewed as mathematical objects of interest and their a precise characterization is desirable. The first estimates of these quantities within compressed sensing were given in \cite{CRT,CT}. As the need for precisely estimating them grew further a finer improvements of these initial estimates were obtained in e.g. \cite{BCTsharp09,BT10}. These are typically obtained through a combination of union-bounding strategy and powerful tail estimates of extreme eigenvalues of Wishart (Gaussian) matrices (see, e.g. \cite{Edelman88}). In this paper we attempt to circumvent such an approach and provide an alternative way to obtain similar estimates.