New constructions of RIP matrices with fast multiplication and fewer rows. arxiv:1211.0986

In this paper, we present novel constructions of matrices with the restricted isometry property (RIP) that support fast matrix-vector multiplication. Our guarantees are the best known, and can also be used to obtain the best known guarantees for fast Johnson Lindenstrauss transforms. In compressed sensing, the restricted isometry property is a sufficient condition for the ef-ficient reconstruction of a nearly k-sparse vector x ∈ Cd from m linear measurements Φx. It is desirable for m to be small, and further it is desirable for Φ to support fast matrix-vector multiplication. Among other applications, fast multiplication improves the runtime of iterative recovery algorithms which repeatedly multiply by Φ or Φ∗. The main contribution of this work is a novel randomized construction of RIP matrices Φ ∈ Cm×d, preserving the `2 norms of all k-sparse vectors with distortion 1+ε, where the matrix-vector multiply Φx can be computed in nearly linear time. The number of rows m is on the order of ε−2k log d log2(k log d), an improvement on previous analyses by a logarithmic factor. Our construction, together with a connection between RIP matrices and the Johnson-Lindenstrauss lemma in [Krahmer-Ward, SIAM. J. Math. Anal. 2011], also implies fast Johnson-Lindenstrauss embeddings with asymptotically fewer rows than previously known. Our construction is actually a recipe for improving any existing family of RIP matrices. Briefly, we apply an appropriate sparse hash matrix with sign flips to any suitable family of RIP matrices. We show that the embedding properties of the original family are maintained, while at the same time improving the number of rows. The main tool in our analysis is a recent bound for the supremum of certain types of Rademacher chaos processes in [Krahmer-Mendelson-Rauhut