  Compressed sensing is a celebrated framework in signal processing and has
many practical applications. One of challenging problems in compressed sensing
is to construct deterministic matrices having restricted isometry property
(RIP). So far, there are only a few publications providing deterministic RIP
matrices beating the square-root bottleneck on the sparsity level. In this
paper, we investigate RIP of certain matrices defined by higher power residues
modulo primes. Moreover, we prove that the widely-believed generalized Paley
graph conjecture implies that these matrices have RIP breaking the square-root
bottleneck.
