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

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

Type: Preprint

Publication Date: 2020-01-01

Citations: 4

DOI: https://doi.org/10.48550/arxiv.2005.11270

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Average-case hardness of RIP certification	2016	Tengyao Wang Quentin Berthet Yaniv Plan
+	Average-case Hardness of RIP Certification	2016	Tengyao Wang Quentin Berthet Yaniv Plan
+	On the Certification of the Restricted Isometry Property	2011	Pascal Koiran Anastasios Zouzias
+ PDF Chat	Certifying the Restricted Isometry Property is Hard	2013	Afonso S. Bandeira Edgar Dobriban Dustin G. Mixon William F. Sawin
+	The Average-Case Time Complexity of Certifying the Restricted Isometry Property	2021	Yunzi Ding Dmitriy Kunisky Alexander S. Wein Afonso S. Bandeira
+	A strong restricted isometry property, with an application to phaseless compressed sensing	2014	Vladislav Voroninski Zhiqiang Xu
+	On the Certification of the Restricted Isometry Property	2011	Pascal Koiran Anastasios Zouzias
+ PDF Chat	Construction of a Large Class of Deterministic Sensing Matrices That Satisfy a Statistical Isometry Property	2010	Robert Calderbank Howard Caygill Sina Jafarpour
+ PDF Chat	Compressed Sensing: How Sharp Is the Restricted Isometry Property?	2011	Jeffrey D. Blanchard Coralia Cartis Jared Tanner
+	Compressed Sensing: How sharp is the Restricted Isometry Property	2010	Jeffrey D. Blanchard Coralia Cartis Jared Tanner
+ PDF Chat	Lower Bound for RIP Constants and Concentration of Sum of Top Order Statistics	2020	Gen Li Xingyu Xu Yuantao Gu
+	Deterministic Bounds for Restricted Isometry of Compressed Sensing Matrices	2011	Shriram Sarvotham Richard G. Baraniuk
+ PDF Chat	SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More	2024	Ilias Diakonikolas Samuel B. Hopkins Ankit Pensia Stefan Tiegel
+	Semi-Random Sparse Recovery in Nearly-Linear Time	2022	Jonathan A. Kelner Jerry Li Allen P. Liu Aaron Sidford Kevin Tian
+	Deterministic bounds for restricted isometry in compressed sensing matrices	2016	Igor Kaporin
+	Hidden cliques and the certification of the restricted isometry property	2012	Pascal Koiran Anastasios Zouzias
+	Hidden cliques and the certification of the restricted isometry property	2012	Pascal Koiran Anastasios Zouzias
+	Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck	2014	Dustin G. Mixon
+ PDF Chat	On the Restricted Isometry Property of Kronecker-structured Matrices	2024	Yanbin He Geethu Joseph
+ PDF Chat	Hidden Cliques and the Certification of the Restricted Isometry Property	2014	Pascal Koiran Anastasios Zouzias

Works That Cite This (4)

Action	Title	Year	Authors
+	Optimal Spectral Recovery of a Planted Vector in a Subspace	2021	Cheng Mao Alexander S. Wein
+ PDF Chat	Tensor clustering with planted structures: Statistical optimality and computational limits	2022	Yuetian Luo Anru R. Zhang
+	Beyond Independent Measurements: General Compressed Sensing with GNN Application.	2021	Alireza Naderi Yaniv Plan
+	Hypothesis testing with low-degree polynomials in the Morris class of exponential families	2020	Dmitriy Kunisky

Works Cited by This (32)

Action	Title	Year	Authors
+ PDF Chat	Adaptive estimation of a quadratic functional by model selection	2000	Béatrice Laurent Pascal Massart
+	Computational Complexity of Certifying Restricted Isometry Property	2014	Abhiram Natarajan Yi Wu
+ PDF Chat	Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck	2015	Dustin G. Mixon
+ PDF Chat	Sharp RIP bound for sparse signal and low-rank matrix recovery	2012	Tommaso Cai Anru R. Zhang
+ PDF Chat	Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices	2014	Tommaso Cai Anru R. Zhang
+ PDF Chat	Hidden Cliques and the Certification of the Restricted Isometry Property	2014	Pascal Koiran Anastasios Zouzias
+ PDF Chat	A Simple Proof of the Restricted Isometry Property for Random Matrices	2008	Richard G. Baraniuk Mark A. Davenport Ronald DeVore Michael B. Wakin
+	Steiner equiangular tight frames	2011	Matthew Fickus Dustin G. Mixon Janet C. Tremain
+ PDF Chat	Rounding sum-of-squares relaxations	2014	Boaz Barak Jonathan A. Kelner David Steurer
+ PDF Chat	The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing	2013	Andreas M. Tillmann Marc E. Pfetsch