  Compressed sensing is a technique for finding sparse solutions to
underdetermined linear systems. This technique relies on properties of the
sensing matrix such as the restricted isometry property. Sensing matrices that
satisfy this property with optimal parameters are mainly obtained via
probabilistic arguments. Deciding whether a given matrix satisfies the
restricted isometry property is a non-trivial computational problem. Indeed, we
show in this paper that restricted isometry parameters cannot be approximated
in polynomial time within any constant factor under the assumption that the
hidden clique problem is hard. Moreover, on the positive side we propose an
improvement on the brute-force enumeration algorithm for checking the
restricted isometry property.
