Hidden Cliques and the Certification of the Restricted Isometry Property

DOI10.1109/TIT.2014.2331341MaRDI QIDQ2986237zbMATHFDO

Authors Anastasios Zouzias, Pascal Koiran

Publication date 16 May 2017

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

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)

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.

Cited in

(12)

• Computational barriers in minimax submatrix detection
• Tensor clustering with planted structures: statistical optimality and computational limits
• Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
• Hardness self-amplification: simplified, optimized, and unified
• Cryptography from planted graphs: security with logarithmic-size messages
• Optimal detection of sparse principal components in high dimension
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• A nearly tight sum-of-squares lower bound for the planted clique problem
• Non-negative sparse regression and column subset selection with \(L_1\) error
• Subexponential-time algorithms for sparse PCA
• Multiple sparse measurement gradient reconstruction algorithm for DOA estimation in compressed sensing
• Computing the spark: mixed-integer programming for the (vector) matroid girth problem

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)