  A matrix is said to possess the Restricted Isometry Property (RIP) if it acts
as an approximate isometry when restricted to sparse vectors. Previous work has
shown it to be NP-hard to determine whether a matrix possess this property, but
only in a narrow range of parameters. In this work, we show that it is NP-hard
to make this determination for any accuracy parameter, even when we restrict
ourselves to instances which are either RIP or far from being RIP. This result
implies that it is NP-hard to approximate the range of parameters for which a
matrix possesses the Restricted Isometry Property with accuracy better than
some constant. Ours is the first work to prove such a claim without any
additional assumptions.

Computational Complexity