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.

本文研究矩阵的 Restricted Isometry Property（RIP），即在限制了稀疏向量时，矩阵能够给出一个近似的等度映射。先前研究表明，确定一个矩阵是否具有 RIP 是 NP 难的，但仅限于一定范围的参数。就算我们将实例局限于 RIP 或与之相差甚远，我们仍然不能在任何精度参数下确定矩阵是否拥有该特性。这个结果意味着在一个常数范围内，精度无法达到比简化参数更好的程度，因此无法近似确定矩阵具有 Restricted Isometry Property 的参数范围。我们是第一个在不依赖额外假设的前提下证明这种结论的研究。