From paley graphs to deterministic sensing matrices with real-valued Gramians

The performance guarantees in recovery of a sparse vector in a compressed sensing scenario, besides the reconstruction technique, depends on the choice of the sensing matrix. The so-called restricted isometry property (RIP) is one of the well-used tools to determine and compare the performance of various sensing matrices. It is a standard result that random (Gaussian) matrices satisfy RIP with high probability. However, the design of deterministic matrices that satisfy RIP has been a great challenge for many years now. The common design technique is through the coherence value (maximum modulus correlation between the columns). In this paper, based on the Paley graphs, we introduce deterministic matrices of size q+1/2 × q with q a prime power, such that the corresponding Gram matrix is real-valued. We show that the coherence of these matrices are less than twice the Welch bound, which is a lower bound valid for general matrices. It should be mentioned that the introduced matrix differs from the equiangular tight frame (ETF) of size q-1/2 × q arising from the Paley difference set.