General constructions of deterministic (S)RIP matrices for compressive sampling

Compressive sampling is a technique of recovering sparse N-dimensional signals from low-dimensional sketches, i.e., their linear images in ℝ^m, m ≪ N. The main question associated with this technique is construction of linear operators that allow faithful recovery of the signal from its sketch. The most frequently used sufficient condition for robust recovery is the near-isometry property of the operator when restricted to k-sparse signals. We study ±1-matrices of dimensions m × N that satisfy the restricted isometry property of order k (k-RIP). As our main set of results, we describe a general method of constructing sampling matrices for which a statistical version of k-RIP holds. We also show that m×N matrices with k-RIP and m = O(k² logN) can be constructed with time complexity O(k²N logN).