Timezone: »

 
Poster
Average-case hardness of RIP certification
Tengyao Wang · Quentin Berthet · Yaniv Plan

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #161
in Wednesday Posters »

The restricted isometry property (RIP) for design matrices gives guarantees for optimal recovery in sparse linear models. It is of high interest in compressed sensing and statistical learning. This property is particularly important for computationally efficient recovery methods. As a consequence, even though it is in general NP-hard to check that RIP holds, there have been substantial efforts to find tractable proxies for it. These would allow the construction of RIP matrices and the polynomial-time verification of RIP given an arbitrary matrix. We consider the framework of average-case certifiers, that never wrongly declare that a matrix is RIP, while being often correct for random instances. While there are such functions which are tractable in a suboptimal parameter regime, we show that this is a computationally hard task in any better regime. Our results are based on a new, weaker assumption on the problem of detecting dense subgraphs.

Keywords: (Other) Statistics · Learning Theory · (Other) Probabilistic Models and Methods · Sparsity and Feature Selection
[ PDF] 

Author Information

Tengyao Wang (University of Cambridge)
Quentin Berthet (University of Cambridge)

Quentin Berthet is a University Lecturer in the Statslab, in the DPMMS at Cambridge, and a faculty fellow at the Alan Turing Institute. He is a former student of the Ecole Polytechnique, received a Ph.D. from Princeton University in 2014, and was a CMI postdoctoral fellow at Caltech.

Yaniv Plan (University of British Columbia)

More from the Same Authors