Source-linked AI summary
Certifying the restricted isometry property is hard
Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin
TL;DR
The paper asks whether the restricted isometry property, a key condition for compressed-sensing reconstruction guarantees, can be efficiently tested for a given matrix. It reduces RIP certification from a linearly dependent-column problem and proves that testing RIP is NP-hard. Consequently, efficient RIP testing would imply an efficient solution to an NP-complete problem, under the assumption P ≠ NP.
Problem
The paper asks whether a given matrix satisfies the (K, δ)-restricted isometry property, an important condition for compressed-sensing reconstruction guarantees.
Method
The paper proves hardness by reducing from the problem of deciding whether K columns of a matrix are linearly dependent.
Results
RIP certification is NP-hard.
Takeaways & Limitations
If P ≠ NP, no method can efficiently test whether an arbitrary matrix satisfies RIP.
Abstract
from arXiv · showhide
This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP is NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided P \neq NP.
I. INTRODUCTION
Compressed sensing uses few measurements to reconstruct high-dimensional sparse vectors, with RIP serving as a central condition for reconstruction guarantees. The paper studies whether RIP can be efficiently certified for a given matrix.
- Compressed sensing enables efficient and stable reconstruction of high-dimensional sparse vectors from few sensing measurements.
- RIP is a widely used sensing-matrix condition underlying reconstruction guarantees for Basis Pursuit, CoSaMP, and Iterative Hard Thresholding.
- The paper proves the conjecture that certifying RIP for an arbitrary matrix is NP-hard.
- RIP certification asks whether a matrix Φ satisfies the (K, δ)-restricted isometry property for a given positive integer K and δ ∈(0, 1).
- The result implies that no efficient method can test for RIP when P ≠ NP.
II. A BRIEF REVIEW OF COMPUTATIONAL COMPLEXITY
The paper uses computational-complexity concepts to establish hardness results. Its reduction strategy starts from the problem of finding linearly dependent column subsets and targets RIP certification.
- Problems in P are solvable in polynomial time, whereas NP problems have solutions verifiable in polynomial time given a certificate.
- A polynomial-time reduction solves problem A using an oracle for problem B, showing that A is no harder than B up to polynomial-time factors.
- To prove a problem NP-hard, it suffices to reduce an already NP-hard problem to it.
- The paper demonstrates RIP-certification hardness by reducing from the problem of finding K linearly dependent columns of a matrix Ψ.
- Prior work established hardness for related or restricted versions of the dependent-column problem, including reductions involving transversal matroids and subset sum.
III. MAIN RESULT
The paper proves RIP certification is NP-hard by reducing the problem of detecting small linearly dependent column sets to RIP testing. A scaled matrix and an appropriately chosen δ make the oracle answer equivalent to whether Spark(Ψ) exceeds K, while the result concerns worst-case testing.
- Theorem 4 establishes that deciding whether a matrix satisfies the (K, δ)-RIP is NP-hard.
- The reduction starts from deciding whether an integer matrix Ψ has Spark(Ψ) ≤ K, where Spark is the smallest number of linearly dependent columns.
- Scaling Ψ to form Φ preserves column linear dependence and ensures the matrix entries have polynomial-bit representations without truncation.
- The RIP oracle is queried on Φ, with its answer distinguishing Φ being (K, δ)-RIP from Spark(Ψ) ≤ K.
- When Spark(Ψ) ≤ K, a K-sparse nullspace vector violates the left RIP inequality; when Spark(Ψ) > K, every K-column submatrix is linearly independent.
- Choosing δ := 1 − 2^-5MNp(M,N) makes the reduction polynomial-time because δ has a standard representation using poly(M, N) bits.
- The theorem addresses worst-case RIP testing and does not exclude matrices whose RIP can be verified efficiently for restricted settings.