Uniform uncertainty principle for Bernoulli and subgaussian ensembles

Simple item page
dc.creatorMendelson, Shahar
dc.creatorPajor, Alain
dc.creatorTomczak-Jaegermann, Nicole
dc.date2006-08-27
dc.date.accessioned2026-07-07T08:08:07Z
dc.date.available2026-07-07T08:08:07Z
dc.descriptionWe present a simple solution to a question posed by Candes, Romberg and Tao on the uniform uncertainty principle for Bernoulli random matrices. More precisely, we show that a rectangular k*n random subgaussian matrix (with k < n) has the property that by arbitrarily extracting any m (with m < k) columns, the resulting submatrices are arbitrarily close to (multiples of) isometries of a Euclidean space. We obtain the optimal estimate for m as a function of k,n and the degree of "closeness" to an isometry. We also give a short and self-contained solution of the reconstruction problem for sparse vectors.
dc.description15 pages; no figures; submitted
dc.identifierhttps://arxiv.org/abs/math/0608665
dc.identifierhttp://arxiv.org/abs/math/0608665
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/131154
dc.subjectStatistics Theory
dc.subjectFunctional Analysis
dc.subject46B07; 47B06; 41A05; 62G05; 94B75
dc.titleUniform uncertainty principle for Bernoulli and subgaussian ensembles
dc.typetext

Files

Collections

arXiv