Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

DOI10.1007/S00365-010-9117-4MaRDI QIDQ634656zbMATH OpenOpenAlexWikidataFDO

Authors Radosław Adamczak, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Publication date 16 August 2011

Published in Constructive Approximation (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingrandom matricesrestricted isometry propertycentrally-neighborly polytopesunderdetermined systems of linear equations

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Asymptotic theory of Banach spaces (46B06) Asymptotic theory of convex bodies (52A23) Approximation by arbitrary linear expressions (41A45) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors $pm{X}_1,\mathrm{...},pm{X}_{N}in{R}^n$, ($Ngen$). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property (RIP) with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a sub-exponential tail inequality possess this property RIP with overwhelming probability. We show that such "sensing" matrices are valid for the exact reconstruction process of $m$-sparse vectors via $el{l}_1$ minimization with $mleCn/lo{g}^2(cN/n)$. The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if $Ksubset{R}^n$ is a convex body and $X_1,\mathrm{...},X_{N}inK$ are i.i.d. random vectors uniformly distributed on $K$, then, with overwhelming probability, the symmetric convex hull of these points is an $m$-centrally-neighborly polytope with $msimn/lo{g}^2(cN/n)$.

Recommendations

• A simple proof of the restricted isometry property for random matrices
• Restricted isometry property for random matrices with heavy-tailed columns
• Random polytopes obtained by matrices with heavy-tailed entries
• Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces \(L_U(\Omega)\)

Cites work

• scientific article; zbMATH DE number 1014176 (Why is no real title available?)
• scientific article; zbMATH DE number 2008526 (Why is no real title available?)
• A central limit theorem for convex sets
• A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
• A remark on compressed sensing
• A simple proof of the restricted isometry property for random matrices
• A stability result for mean width of \(L_{p}\)-centroid bodies
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• Concentration of mass on convex bodies
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Decoding by Linear Programming
• Geometric approach to error-correcting codes and reconstruction of signals
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• How neighborly can a centrally symmetric polytope be?
• Lectures on Polytopes
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Power-law estimates for the central limit theorem for convex sets
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Reconstruction and subgaussian processes
• Stability properties of neighbourly random polytopes
• Stable signal recovery from incomplete and inaccurate measurements
• Tail and moment estimates for sums of independent random vectors with logarithmically concave tails
• The Generic Chaining
• The Supremum of Some Canonical Processes
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Weak convergence and empirical processes. With applications to statistics

Cited in

(30)

• Restricted isometry property for random matrices with heavy-tailed columns
• Sparse recovery properties of discrete random matrices
• Universality in polytope phase transitions and message passing algorithms
• On the interval of fluctuation of the singular values of random matrices
• Sparse recovery under weak moment assumptions
• Condition number of a square matrix with i.i.d. columns drawn from a convex body
• A tight bound of hard thresholding
• Column randomization and almost-isometric embeddings
• Row products of random matrices
• Compressive imaging through optical fiber with partial speckle scanning
• Sparse recovery from extreme eigenvalues deviation inequalities
• Variations and extensions of the Gaussian concentration inequality, Part I
• Orlicz Integrability of Additive Functionals of Harris Ergodic Markov Chains
• On the geometry of polytopes generated by heavy-tailed random vectors
• Stability of the elastic net estimator
• An introduction to compressed sensing
• Empirical processes with a bounded \(\psi_1\) diameter
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• The sparsity of LASSO-type minimizers
• The lower tail of random quadratic forms with applications to ordinary least squares
• Weaker regularity conditions and sparse recovery in high-dimensional regression
• Bootstrap confidence sets for spectral projectors of sample covariance
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
• Quantitative Version of a Silverstein’s Result
• Sparsity and non-Euclidean embeddings
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• Flavors of compressive sensing
• Geometry of log-concave ensembles of random matrices and approximate reconstruction
• Random tensor theory: Extending random matrix theory to mixtures of random product states
• A multivariate CLT for weighted sums with rate of convergence of order \(O(1/n)\)

This page was built for publication: Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

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