The Average-Case Time Complexity of Certifying the Restricted Isometry Property

DOI10.1109/TIT.2021.3112823zbMath1487.94038arXiv2005.11270OpenAlexW3199680764MaRDI QIDQ5032580

Afonso S. Bandeira, Dmitriy Kunisky, Yunzi Ding, Alexander S. Wein

Publication date: 17 February 2022

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

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

zbMATH Keywords

compressed sensingrestricted isometry property (RIP)exact average-case time complexity

Mathematics Subject Classification ID

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

Related Items (1)

Tensor clustering with planted structures: statistical optimality and computational limits

This page was built for publication: The Average-Case Time Complexity of Certifying the Restricted Isometry Property