Hidden Cliques and the Certification of the Restricted Isometry Property

DOI10.1109/TIT.2014.2331341zbMATH Open1360.94081arXiv1211.0665MaRDI QIDQ2986237FDOQ2986237

Pascal Koiran, Anastasios Zouzias

Publication date: 16 May 2017

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

Abstract: Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy this property with optimal parameters are mainly obtained via probabilistic arguments. Deciding whether a given matrix satisfies the restricted isometry property is a non-trivial computational problem. Indeed, we show in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard. Moreover, on the positive side we propose an improvement on the brute-force enumeration algorithm for checking the restricted isometry property.

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cited In (12)

• Subexponential-time algorithms for sparse PCA
• Computational barriers in minimax submatrix detection
• Tensor clustering with planted structures: statistical optimality and computational limits
• Cryptography from planted graphs: security with logarithmic-size messages
• Computing the spark: mixed-integer programming for the (vector) matroid girth problem
• Non-Negative Sparse Regression and Column Subset Selection with L1 Error
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Multiple sparse measurement gradient reconstruction algorithm for DOA estimation in compressed sensing
• Hardness self-amplification: simplified, optimized, and unified
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Optimal detection of sparse principal components in high dimension

This page was built for publication: Hidden Cliques and the Certification of the Restricted Isometry Property

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