Approximately Certifying the Restricted Isometry Property is Hard
From MaRDI portal
Publication:4682856
DOI10.1109/TIT.2017.2776131zbMATH Open1401.94053arXiv1704.00468MaRDI QIDQ4682856
Publication date: 19 September 2018
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: A matrix is said to possess the Restricted Isometry Property (RIP) if it acts as an approximate isometry when restricted to sparse vectors. Previous work has shown it to be NP-hard to determine whether a matrix possess this property, but only in a narrow range of parameters. In this work, we show that it is NP-hard to make this determination for any accuracy parameter, even when we restrict ourselves to instances which are either RIP or far from being RIP. This result implies that it is NP-hard to approximate the range of parameters for which a matrix possesses the Restricted Isometry Property with accuracy better than some constant. Ours is the first work to prove such a claim without any additional assumptions.
Full work available at URL: https://arxiv.org/abs/1704.00468
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Special matrices (15B99)
Related Items (1)
This page was built for publication: Approximately Certifying the Restricted Isometry Property is Hard
