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

DOI10.1007/S00365-010-9117-4zbMATH Open1222.52009arXiv0904.4723OpenAlexW2066544664WikidataQ105583376 ScholiaQ105583376MaRDI QIDQ634656FDOQ634656

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

Publication date: 16 August 2011

Published in: Constructive Approximation (Search for Journal in Brave)

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)$.

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

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
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Restricted isometry property for matrices whose entries are random variables belonging to some Orlicz spaces \(L_U(\Omega)\)

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)

Cites Work

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

Cited In (30)

• Sparse recovery properties of discrete random matrices
• Universality in polytope phase transitions and message passing algorithms
• Compressive Imaging Through Optical Fiber with Partial Speckle Scanning
• On the interval of fluctuation of the singular values of random matrices
• Condition number of a square matrix with i.i.d. columns drawn from a convex body
• Sparse recovery under weak moment assumptions
• Column randomization and almost-isometric embeddings
• Row products of random matrices
• Sparse recovery from extreme eigenvalues deviation inequalities
• Variations and extensions of the Gaussian concentration inequality, Part I
• Flavors of Compressive Sensing
• 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
• Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries
• The sparsity of LASSO-type minimizers
• Empirical processes with a bounded \(\psi_1\) diameter
• 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
• A Tight Bound of Hard Thresholding
• An Introduction to Compressed Sensing
• Sparsity and non-Euclidean embeddings
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• A multivariate CLT for weighted sums with rate of convergence of order \(O(1/n)\)
• Geometry of log-concave ensembles of random matrices and approximate reconstruction
• Random tensor theory: Extending random matrix theory to mixtures of random product states
• Restricted isometry property for random matrices with heavy-tailed columns

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)