ABSTRACT
In this chapter we give examples of matrices satisfying RIP. Namely, we consider matrices with i.i.d. random entries that decay sufficiently fast (e.g., subgaussian), matrices with randomly selected rows from the DFT (or DCT) matrix, and matrices with the rows randomly selected from a general orthogonal matrix. We provide complete and self-contained proofs of RIP in these cases, trying to keep them concise but complete. All necessary background material that goes beyond the standard probability and linear algebra courses can be found in the Appendix. Also, recall that matrices that have RIP satisfy this property uniformly for all subsets of size s or less. For non-uniform results that nevertheless imply the sparse signal recovery we refer to (Cande`s and Plan, 2011) and to recent monographs (Foucart and Rauhut, 2013; Chafai et al., 2012).
