Certifying the Restricted Isometry Property is Hard

DOI10.1109/TIT.2013.2248414zbMath1364.94109arXiv1204.1580MaRDI QIDQ2989185

Dustin G. Mixon, William F. Sawin, Edgar Dobriban, Afonso S. Bandeira

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.1580

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items (31)

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ Regularity properties for sparse regression ⋮ Best subset selection via a modern optimization lens ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ A General Framework of Rotational Sparse Approximation in Uncertainty Quantification ⋮ Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck ⋮ 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory ⋮ Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee ⋮ Optimal detection of sparse principal components in high dimension ⋮ Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry ⋮ Maximum turn‐off control for discrete‐time linear systems ⋮ Flavors of Compressive Sensing ⋮ Stability of 1-bit compressed sensing in sparse data reconstruction ⋮ Non-Negative Sparse Regression and Column Subset Selection with L1 Error ⋮ The road to deterministic matrices with the restricted isometry property ⋮ On the restricted isometry property of the Paley matrix ⋮ Sparse approximate reconstruction decomposed by two optimization problems ⋮ On Collaborative Compressive Sensing Systems: The Framework, Design, and Algorithm ⋮ Low Complexity Regularization of Linear Inverse Problems ⋮ A Scale-Invariant Approach for Sparse Signal Recovery ⋮ Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids ⋮ Memoryless scalar quantization for random frames ⋮ Learning directed acyclic graph SPNs in sub-quadratic time ⋮ Characterization of ℓ1 minimizer in one-bit compressed sensing ⋮ Unnamed Item ⋮ Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit ⋮ Minimization of $\ell_{1-2}$ for Compressed Sensing ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices ⋮ Error analysis of reweighted \(l_1\) greedy algorithm for noisy reconstruction ⋮ Compressed sensing in the spherical near-field to far-field transformation ⋮ Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing

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