UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Average-case hardness of RIP certification

Wang, T; Berthet, Q; Plan, Y; (2016) Average-case hardness of RIP certification. In: Lee, D D and Sugiyama, M and Luxburg, U V and Guyon, I and Garnett, R, (eds.) Advances in Neural Information Processing Systems 29 (NIPS 2016). NIPS Proceedings: Barcelona, Spain. Green open access

[thumbnail of testRIP_FA.pdf]
Preview
Text
testRIP_FA.pdf - Accepted Version

Download (586kB) | Preview

Abstract

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.

Type: Proceedings paper
Title: Average-case hardness of RIP certification
Event: Neural Information Processing Systems 2016
Open access status: An open access version is available from UCL Discovery
Publisher version: https://papers.nips.cc/book/advances-in-neural-inf...
Language: English
Additional information: © 2016 NIPS Foundation - All Rights Reserved.This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Statistical Science
URI: https://discovery.ucl.ac.uk/id/eprint/10055408
Downloads since deposit
13Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item