Certifying the restricted isometry property is hard

Abstract

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.

Cited by in corpus (19)

• Optimal detection of sparse principal components in high dimension
• $L_{1/2}$ Regularization: Convergence of Iterative Half Thresholding Algorithm
• Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery
• Adaptive compressive tomography with no a priori information
• Group Sparse Recovery via the ${\ell }^0({\ell }^2)$ Penalty: Theory and Algorithm
• End-to-End Optimization of Metasurfaces for Imaging with Compressed Sensing
• Adaptive compressive tomography: a numerical study
• Sensing Matrix Design and Sparse Recovery on the Sphere and the Rotation Group
• Optimizing Sensing Matrices for Spherical Near-Field Antenna Measurements
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• Conditioning of Random Block Subdictionaries with Applications to Block-Sparse Recovery and Regression
• Semi-device-dependent blind quantum tomography
• Approximately certifying the restricted isometry property is hard
• Lower Bound for RIP Constants and Concentration of Sum of Top Order Statistics
• A Kronecker-Based Sparse Compressive Sensing Matrix for Millimeter Wave Beam Alignment
• Regularity Properties for Sparse Regression
• Enhanced block sparse signal recovery based on $q$-ratio block constrained minimal singular values
• Tight bounds on the mutual coherence of sensing matrices for Wigner D-functions on regular grids
• One-Shot Messaging at Any Load Through Random Sub-Channeling in OFDM