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

DOI10.1007/s00365-010-9117-4zbMath1222.52009arXiv0904.4723OpenAlexW2066544664WikidataQ105583376 ScholiaQ105583376MaRDI QIDQ634656

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)

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

zbMATH Keywords

random matricescompressed sensingrestricted isometry propertycentrally-neighborly polytopesunderdetermined systems of linear equations

Mathematics Subject Classification ID

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

Related Items

Condition number of a square matrix with i.i.d. columns drawn from a convex body, On the interval of fluctuation of the singular values of random matrices, Counting the faces of randomly-projected hypercubes and orthants, with applications, On the geometry of polytopes generated by heavy-tailed random vectors, The lower tail of random quadratic forms with applications to ordinary least squares, Empirical processes with a bounded \(\psi_1\) diameter, Sparsity and non-Euclidean embeddings, Orlicz Integrability of Additive Functionals of Harris Ergodic Markov Chains, Stability of the elastic net estimator, Variations and extensions of the Gaussian concentration inequality, Part I, 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, Flavors of Compressive Sensing, Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries, Restricted isometry property for random matrices with heavy-tailed columns, An Introduction to Compressed Sensing, Random tensor theory: Extending random matrix theory to mixtures of random product states, Sparse recovery under weak moment assumptions, A Tight Bound of Hard Thresholding, Row products of random matrices, Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, Sparse recovery from extreme eigenvalues deviation inequalities, Bootstrap confidence sets for spectral projectors of sample covariance, Weaker regularity conditions and sparse recovery in high-dimensional regression, Quantitative Version of a Silverstein’s Result, Universality in polytope phase transitions and message passing algorithms, Compressive Imaging Through Optical Fiber with Partial Speckle Scanning, The sparsity of LASSO-type minimizers

Cites Work

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