Sparse recovery from extreme eigenvalues deviation inequalities

DOI10.1051/PS/2018024zbMATH Open1447.60055arXiv1604.01171OpenAlexW3098125792WikidataQ128997752 ScholiaQ128997752MaRDI QIDQ5228345FDOQ5228345

S. Dallaporta, Yohann De Castro

Publication date: 12 August 2019

Published in: ESAIM: Probability and Statistics (Search for Journal in Brave)

Abstract: This article provides a new toolbox to derive sparse recovery guarantees from small 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 small 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 small deviations on the extreme eigenvalues given by Random Matrix theory.

Full work available at URL: https://arxiv.org/abs/1604.01171

Recommendations

• Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
• Simple bounds for recovering low-complexity models
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Nonuniform sparse recovery with subgaussian matrices
• Sparse recovery under weak moment assumptions

zbMATH Keywords

restricted isometry propertysparse regressionGaussian matricesdeviations inequalitiesRademacher matrices

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Large deviations (60F10) Ridge regression; shrinkage estimators (Lasso) (62J07) Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15)

Cites Work

• On the conditions used to prove oracle results for the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Title not available (Why is that?)
• Local operator theory, random matrices and Banach spaces.
• Decoding by Linear Programming
• A simple proof of the restricted isometry property for random matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices
• Shape fluctuations and random matrices
• A mathematical introduction to compressive sensing
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Neighborliness of randomly projected simplices in high dimensions
• Adaptive Dantzig density estimation
• Small deviations for beta ensembles
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Interactions between compressed sensing random matrices and high dimensional geometry
• On sparse reconstruction from Fourier and Gaussian measurements
• Sparse recovery under weak moment assumptions
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Living on the edge: phase transitions in convex programs with random data
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Smallest singular value of random matrices and geometry of random polytopes
• Universality of covariance matrices
• Random covariance matrices: universality of local statistics of eigenvalues up to the edge
• Non-asymptotic theory of random matrices: extreme singular values
• Universality results for the largest eigenvalues of some sample covariance matrix ensembles
• Tail bounds via generic chaining
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Compressed Sensing: How Sharp Is the Restricted Isometry Property?
• Accuracy Guarantees for <formula formulatype="inline"> <tex Notation="TeX">$\ell_1$</tex></formula>-Recovery
• A universality result for the smallest eigenvalues of certain sample covariance matrices
• Sharp recovery bounds for convex demixing, with applications
• Improved Bounds on Restricted Isometry Constants for Gaussian Matrices
• Uniform recovery of fusion frame structured sparse signals
• Deviation Inequalities on Largest Eigenvalues
• A Simple Tool for Bounding the Deviation of Random Matrices on Geometric Sets
• Increasing subsequences and the hard-to-soft edge transition in matrix ensembles
• Regularization and the small-ball method. I: Sparse recovery
• A remark on the Lasso and the Dantzig selector
• Bounds of restricted isometry constants in extreme asymptotics: formulae for Gaussian matrices
• A Rice method proof of the null-space property over the Grassmannian
• Stable recovery of low-dimensional cones in Hilbert spaces: one RIP to rule them all

Cited In (1)

• Asymptotic analysis for extreme eigenvalues of principal minors of random matrices

This page was built for publication: Sparse recovery from extreme eigenvalues deviation inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5228345)