Uniform uncertainty principle for Bernoulli and subgaussian ensembles

DOI10.1007/s00365-007-9005-8zbMath1230.46011arXivmath/0608665MaRDI QIDQ1039886

Shahar Mendelson, Nicole Tomczak-Jaegermann, Alain Pajor

Publication date: 23 November 2009

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

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

zbMATH Keywords

random matrices; generic chaining; approximate reconstruction; uniform uncertainty principle

Mathematics Subject Classification ID

60B20: Random matrices (probabilistic aspects)

46B07: Local theory of Banach spaces

41A45: Approximation by arbitrary linear expressions

52A23: Asymptotic theory of convex bodies

Related Items

Unnamed Item, Time for dithering: fast and quantized random embeddings via the restricted isometry property, Unnamed Item, High-dimensional dynamic systems identification with additional constraints, Stable Image Reconstruction Using Transformed Total Variation Minimization, Sparse recovery from extreme eigenvalues deviation inequalities, Nonuniform recovery of fusion frame structured sparse signals, An analysis of penalized interaction models, Derandomizing restricted isometries via the Legendre symbol, Sparsity and non-Euclidean embeddings, Restricted isometries for partial random circulant matrices, Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality, On higher order isotropy conditions and lower bounds for sparse quadratic forms, Compressive sensing using chaotic sequence based on Chebyshev map, Dimensionality reduction with subgaussian matrices: a unified theory, Sparse recovery under weak moment assumptions, Compressed sensing with coherent and redundant dictionaries, The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), Error estimates for orthogonal matching pursuit and random dictionaries, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Iterative hard thresholding for compressed sensing, Uniform recovery of fusion frame structured sparse signals, A strong restricted isometry property, with an application to phaseless compressed sensing, Stability properties of neighbourly random polytopes, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Improved bounds for sparse recovery from subsampled random convolutions, High-dimensional \(A\)-learning for optimal dynamic treatment regimes, Trace regression model with simultaneously low rank and row(column) sparse parameter, Sparsity and incoherence in orthogonal matching pursuit, Kernel conjugate gradient methods with random projections, Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery, Bipolar measurement matrix using chaotic sequence, Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise, Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO, Stability and instance optimality for Gaussian measurements in compressed sensing, Erasure recovery matrices for encoder protection, Sparse reconstruction with multiple Walsh matrices, Posterior asymptotic normality for an individual coordinate in high-dimensional linear regression, Weaker regularity conditions and sparse recovery in high-dimensional regression, Near oracle performance and block analysis of signal space greedy methods, Greedy signal space methods for incoherence and beyond, Greedy-like algorithms for the cosparse analysis model, Fast and RIP-optimal transforms, Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach, Improved bounds for the RIP of Subsampled Circulant matrices

Cites Work