Paper Info
Title
Restricted Isometry Constants for Gaussian and Rademacher matrices.
Abstract
Restricted Isometry Constants (RICs) are a pivotal notion in Compressed Sensing (CS) as these constants finely assess how a linear operator is conditioned on the set of sparse vectors and hence how it performs in stable and robust sparse regression (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. One of the most popular model may be the sub-Gaussian matrices since it encompasses random matrices with Gaussian or Rademacher i.i.d. entries. In this paper, we provide a description of the phase transition on SRSR for those matrices using state-of-the-art (small) deviation estimates on their extreme eigenvalues. In particular, we show new upper bounds on RICs for Gaussian and Rademacher matrices. This allows us to derive a new lower bound on the probability of getting SRSR. One of the benefit of this novel approach is to broaden the scope of phase transition on RICs and SRSR to the quest of universality results in Random Matrix Theory.
Year
Venue
Field
2016
arXiv: Statistics Theory
Discrete mathematics,Matrix (mathematics),Upper and lower bounds,Isometry,Gaussian,Linear map,Statistics,Eigenvalues and eigenvectors,Restricted isometry property,Mathematics,Random matrix
DocType
Volume
Citations 
Journal
abs/1604.01171
0
PageRank 
References 
Authors
0.34
6
2
Name
Order
Citations
PageRank
Sandrine Dallaporta100.34
Yohann de Castro2286.39