Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality

DOI10.1016/J.SPL.2012.03.038MaRDI QIDQ449436zbMATH OpenOpenAlexFDO

Authors Stéphane Chrétien, Sébastien Darses

Publication date 30 August 2012

Published in Statistics \& Probability Letters (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingdecouplingmatrix Chernoff inequalityrandom sub-matrices

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52)

Abstract: Let $X$ be a $nimesp$ matrix with coherence $mu(X)=ma{x}_{jeq{j}^{\prime }}|X_j^t{X}_{j^{\prime }}|$. We present a simplified and improved study of the quasi-isometry property for most submatrices of $X$ obtained by uniform column sampling. Our results depend on $mu(X)$, $|X|$ and the dimensions with explicit constants, which improve the previously known values by a large factor. The analysis relies on a tail decoupling argument, of independent interest, and a recent version of the Non-Commutative Chernoff inequality (NCCI).

Recommendations

• Invertibility of random matrices: norm of the inverse
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• On the interval of fluctuation of the singular values of random matrices
• Sampling from large matrices
• Tail inequalities for sums of random matrices that depend on the intrinsic dimension

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Near-ideal model selection by \(\ell _{1}\) minimization
• Norms of random submatrices and sparse approximation
• Random vectors in the isotropic position
• Sampling from large matrices
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• User-friendly tail bounds for sums of random matrices

Cited in

(9)

• Pivotal estimation via square-root lasso in nonparametric regression
• Invertibility of random matrices: norm of the inverse
• Paved with good intentions: analysis of a randomized block Kaczmarz method
• The Littlewood-Offord problem and invertibility of random matrices
• Remote sensing via _1-minimization
• Randomized block Kaczmarz method with projection for solving least squares
• Submatrices with nonuniformly selected random supports and insights into sparse approximation
• Invertibility of random matrices: Unitary and orthogonal perturbations
• Block Kaczmarz method with inequalities

This page was built for publication: Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality

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