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.
Accepté le :
DOI : 10.1051/ps/2018024
Keywords: Restricted isometry property, Gaussian matrices, Rademacher matrices, deviations inequalities, sparse regression
Dallaporta, Sandrine 1 ; De Castro, Yohann 1
@article{PS_2019__23__430_0,
author = {Dallaporta, Sandrine and De Castro, Yohann},
title = {Sparse recovery from extreme eigenvalues deviation inequalities},
journal = {ESAIM: Probability and Statistics},
pages = {430--463},
year = {2019},
publisher = {EDP Sciences},
volume = {23},
doi = {10.1051/ps/2018024},
zbl = {1447.60055},
mrnumber = {3989600},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ps/2018024/}
}
TY - JOUR AU - Dallaporta, Sandrine AU - De Castro, Yohann TI - Sparse recovery from extreme eigenvalues deviation inequalities JO - ESAIM: Probability and Statistics PY - 2019 SP - 430 EP - 463 VL - 23 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ps/2018024/ DO - 10.1051/ps/2018024 LA - en ID - PS_2019__23__430_0 ER -
%0 Journal Article %A Dallaporta, Sandrine %A De Castro, Yohann %T Sparse recovery from extreme eigenvalues deviation inequalities %J ESAIM: Probability and Statistics %D 2019 %P 430-463 %V 23 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ps/2018024/ %R 10.1051/ps/2018024 %G en %F PS_2019__23__430_0
Dallaporta, Sandrine; De Castro, Yohann. Sparse recovery from extreme eigenvalues deviation inequalities. ESAIM: Probability and Statistics, Tome 23 (2019), pp. 430-463. doi: 10.1051/ps/2018024
[1] and , Handbook of Mathematical Functions. National Bureau of Standards, Washington DC (1965) | MR
[2] , , and , Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Constr. Approx. 34 (2011) 61–88 | Zbl | MR | DOI
[3] , , and , Living on the edge: phase transitions in convex programs with random data. Inf. Inference 3 (2014) 224–294 | Zbl | MR | DOI
[4] , and , Uniform recovery of fusion frame structured sparse signals. Appl. Comput. Harmon. Anal. 41 (2016) 341–361 | Zbl | MR | DOI
[5] , and , A rice method proof of the null-space property over the grassmannian. Ann. Inst. Henri Poincaré - Probab. Stat. 53 (2017) 1821–1838 | Zbl | MR
[6] and , Improved bounds on restricted isometry constants for gaussian matrices. SIAM J. Matrix Anal. Appl. 31 (2010) 2882–2898 | Zbl | MR | DOI
[7] and , Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices. Linear Algebra Appl. 441 (2014) 88–109 | Zbl | MR | DOI
[8] , , and , A simple proof of the restricted isometry property for random matrices. Constr. Approx. 28 (2008) 253–263 | Zbl | MR | DOI
[9] , and , Adaptive dantzig density estimation. Ann. Inst. Henri Poincaré - Probab. Stat. 47 (2011) 43–74 | Zbl | MR | Numdam | DOI
[10] , and , Simultaneous analysis of lasso and Dantzig selector. Ann. Stat. 37 (2009) 1705–1732 | Zbl | MR | DOI
[11] , and , Compressed sensing: how sharp is the restricted isometry property? SIAM Rev. 53 (2011) 105–125 | Zbl | MR | DOI
[12] and , Increasing subsequences and the hard-to-soft edge transition in matrix ensembles. J. Phys. A 36 (2003) 2963–2981 | Zbl | MR | DOI
[13] and , Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE Trans. Inf. Theory 60 (2014) 122–132 | Zbl | MR | DOI
[14] , and , Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52 (2006) 489–509 | Zbl | MR | DOI
[15] and , Decoding by linear programming. IEEE Trans. Inf. Theory 51 (2005) 4203–4215 | Zbl | MR | DOI
[16] and , Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52 (2006) 5406–5425 | Zbl | MR | DOI
[17] , The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris 346 (2008) 589–592 | Zbl | MR | DOI
[18] A remark on the lasso and the dantzig selector. Stat. Probab. Lett. 83 (2013) 304–314 | Zbl | MR | DOI
[19] , , and , Interaction Between Compressed Sensing, Random Matrices and High Dimensional Geometry. No 37 of Panoramas et synthèses. Société Mathématique de France (2012) | Zbl | MR
[20] and , Local operator theory, random matrices and banach spaces. In Handbook of the Geometry of Banach Spaces, vol. 1. Elsevier, Amsterdam (2001) 317–366 | Zbl | MR | DOI
[21] , Tail bounds via generic chaining. Electron. J. Probab. 20 (2015) 53 | Zbl | MR | DOI
[22] and , Neighborliness of randomly projected simplices in high dimensions. Proc. Nat. Acad. Sci. USA 102 (2005) 9452–9457 | Zbl | MR | DOI
[23] and , Counting faces of randomly projected polytopes when the projection radically lowers dimension. J. Am. Math. Soc. 22 (2009) 1–53 | Zbl | MR | DOI
[24] and , Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philos. Trans. R. Soc. A Math. Phys. Eng. Sci. 367 (2009) 4273–4293 | Zbl | MR | DOI
[25] and , A universality result for the smallest eigenvalues of certain sample covariance matrices. Geom. Funct. Anal. 20 (2010) 88–123 | Zbl | MR | DOI
[26] and , Sparsest solutions of underdetermined linear systems via lq-minimization for 0 < q < = 1. Appl. Comput. Harmon. Anal. 26 (2009) 395–407. | Zbl | MR | DOI
[27] and , A Mathematical Introduction to Compressive Sensing. Springer (2013) | Zbl | MR | DOI
[28] , Shape fluctuations and random matrices. Commun. Math. Phys. 209 (2000) 437–476 | Zbl | MR | DOI
[29] and , Accuracy guarantees for l1-recovery. IEEE Trans. Inf. Theory 57 (2011) 7818–7839 | Zbl | MR | DOI
[30] and , Sparse recovery under weak moment assumptions. J. Eur. Math. Soc. 19 (2017) 881–904 | Zbl | MR | DOI
[31] and , Regularization and the small-ball method i: sparse recovery. Ann. Stat. 46 (2018) 611–641 | Zbl | MR | DOI
[32] and , Small deviations for beta ensembles. Electron. J. Probab. 15 (2010) 1319–1343 | Zbl | MR | DOI
[33] , Deviation inequalities on largest eigenvalues. In Geometric Aspects of Functional Analysis, vol. 1910 of Lecture Notes in Mathematics. Springer, Berlin (2007) 167–219 | Zbl | MR | DOI
[34] , , and , A simple tool for bounding the deviation of random matrices on geometric sets. In Geometric Aspects of Functional Analysis. Springer (2017) 277–299 | Zbl | MR | DOI
[35] , , and , Smallest singular value of random matrices and geometry of random polytopes. Adv. Math. 195 (2005) 491–523 | Zbl | MR | DOI
[36] and , Sharp recovery bounds for convex demixing, with applications. Found. Comput. Math. 14 (2014) 503–567 | Zbl | MR | DOI
[37] , and , Uniform uncertainty principle for Bernoulli and subgaussian ensembles. Constr. Approx. 28 (2008) 277–289 | Zbl | MR | DOI
[38] , Universality results for the largest eigenvalues of some sample covariance matrix ensembles. Probab. Theory Relat. Fields 143 (2009) 481–516 | Zbl | MR | DOI
[39] and , Universality of covariance matrices. Ann. Appl. Probab. 24 (2014) 935–1001 | Zbl | MR | DOI
[40] and , On sparse reconstruction from Fourier and Gaussian measurements. Commun. Pure Appl. Math. 61 (2008) 1025–1045 | Zbl | MR | DOI
[41] and , Non-asymptotic theory of random matrices: extreme singular values, in Proceedings of the International Congress of Mathematicians. vol. III. Hindustan Book Agency, New Delhi (2010) 1576–1602 | Zbl | MR
[42] , A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices. J. Stat. Phys. 108 (2002) 1033–1056 | Zbl | MR | DOI
[43] and , Stable recovery of low-dimensional cones in hilbert spaces: one rip to rule them all. Appl. Comput. Harmon. Anal. 45 (2016) 170–205 | Zbl | MR | DOI
[44] and , On the conditions used to prove Oracle results for the lasso. Electron. J. Stat. 3 (2009) 1360–1392 | Zbl | MR | DOI
[45] , Random covariance matrices: universality of local statistics of eigenvalues up to the edge. Random Matrices Theory Appl. 1 (2012) 1150005 | Zbl | MR | DOI
Cité par Sources :
