On the restricted isometry of deterministically subsampled Fourier matrices

Matrices satisfying the Restricted Isometry Property (RIP) are central to the emerging theory of compressive sensing (CS). Initial results in CS established that the recovery of sparse vectors x from a relatively small number of linear observations of the form y = Ax can be achieved, using a tractable convex optimization, whenever A is a matrix that satisfies the RIP; similar results also hold when x is nearly sparse or the observations are corrupted by noise. In contrast to random constructions prevalent in many prior works in CS, this paper establishes a collection of deterministic matrices, formed by deterministic selection of rows of Fourier matrices, which satisfy the RIP. Implications of this result for the recovery of signals having sparse spectral content over a large bandwidth are discussed.