Uniform Uncertainty Principle for Bernoulli and Subgaussian Ensembles
Date
2008
Authors
Mendelson, Shahar
Pajor, Alain
Tomczak-Jaegermann, Nicole
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Abstract
The paper considers random matrices with independent subgaussian columns and provides a new elementary proof of the Uniform Uncertainty Principle for such matrices. The Principle was introduced by Candes, Romberg and Tao in 2004; for subgaussian random matrices it was carlier proved by the present authors, as a consequence of a general result based on a generic chaining method of Talagrand. The present proof combines a simple measure concentration and a covering argument, which are standard tools of high-dimensional convexity.
Description
Keywords
Keywords: Approximate reconstruction; Generic chaining; Random matrices; Uniform uncertainty principle
Citation
Collections
Source
Constructive Approximation
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31