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 eq NP.

Recommendations

Approximately Certifying the Restricted Isometry Property is Hard
Computational complexity of certifying restricted isometry property
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Rigorous restricted isometry property of low-dimensional subspaces
Restricted isometry property for general p-norms
Restricted Isometry Property for General p-Norms
A simple proof of the restricted isometry property for random matrices
An Improved Estimate in the Restricted Isometry Problem
Restricted isometry properties and nonconvex compressive sensing
Restricted p-Isometry Properties of Nonconvex Matrix Recovery

Cited in

(33)

Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids
Compressed sensing in the spherical near-field to far-field transformation
Stability of 1-bit compressed sensing in sparse data reconstruction
The road to deterministic matrices with the restricted isometry property
scientific article; zbMATH DE number 7307477 (Why is no real title available?)
Sparse approximate reconstruction decomposed by two optimization problems
On collaborative compressive sensing systems: the framework, design, and algorithm
Regularity properties for sparse regression
Robust width: a characterization of uniformly stable and robust compressed sensing
Error analysis of reweighted l₁ greedy algorithm for noisy reconstruction
Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit
On the restricted isometry property of the Paley matrix
Low complexity regularization of linear inverse problems
Derandomizing restricted isometries via the Legendre symbol
Derandomized compressed sensing with nonuniform guarantees for _1 recovery
Sparse recovery from quadratic measurements with external field
Maximum turn‐off control for discrete‐time linear systems
A general framework of rotational sparse approximation in uncertainty quantification
On the hardness of the L₁-L₂ regularization problem
Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
A Scale-Invariant Approach for Sparse Signal Recovery
1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
Explicit matrices with the restricted isometry property: breaking the square-root bottleneck
Best subset selection via a modern optimization lens
Memoryless scalar quantization for random frames
Non-negative sparse regression and column subset selection with \(L_1\) error
Doubly transitive equiangular tight frames that contain regular simplices
Minimization of L₁ over L₂ for sparse signal recovery with convergence guarantee
Optimal detection of sparse principal components in high dimension
Learning directed acyclic graph SPNs in sub-quadratic time
Minimization of \(\ell_{1-2}\) for compressed sensing
Flavors of compressive sensing

This page was built for publication: Certifying the Restricted Isometry Property is Hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989185)