Volume 23, 2019
|Page(s)||430 - 463|
|Published online||07 August 2019|
Sparse recovery from extreme eigenvalues deviation inequalities
CMLA, ENS Cachan, CNRS, Université Paris-Saclay,
2 Laboratoire de Mathématiques d’Orsay, Université Paris-Sud, CNRS, Université Paris-Saclay, 91405 Orsay, France
3 INRIA Paris, 2 rue Simone Iff, 75012 Paris, France
4 CERMICS Laboratory at Ponts ParisTech, 6 et 8 avenue Blaise Pascal, 77455 Marne la Vallée Cedex 2, France
Accepted: 5 November 2018
This article provides a new toolbox to derive sparse recovery guarantees – that is referred to as “stable and robust sparse regression” (SRSR) – from deviations on extreme singular values or extreme eigenvalues obtained in Random Matrix Theory. This work is based on Restricted Isometry Constants (RICs) which are a pivotal notion in Compressed Sensing and High-Dimensional Statistics as these constants finely assess how a linear operator is conditioned on the set of sparse vectors and hence how it performs in SRSR. While it is an open problem to construct deterministic matrices with apposite RICs, one can prove that such matrices exist using random matrices models. In this paper, we show upper bounds on RICs for Gaussian and Rademacher matrices using state-of-the-art deviation estimates on their extreme eigenvalues. This allows us to derive a lower bound on the probability of getting SRSR. One benefit of this paper is a direct and explicit derivation of upper bounds on RICs and lower bounds on SRSR from deviations on the extreme eigenvalues given by Random Matrix theory.
Mathematics Subject Classification: 60F10 / 62J05 / 62J07 / 15A18 / 15A42 / 65F15
Key words: Restricted isometry property / Gaussian matrices / Rademacher matrices / deviations inequalities / sparse regression
© EDP Sciences, SMAI 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.