Covering radius and the Restricted Isometry Property

Robert Calderbank*, Sina Jafarpour, Maria Monica Nastasescu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The Restricted Isometry Property or RIP introduced by Candes and Tao requires an n × p dictionary to act as a near isometry on all k-sparse signals. This paper provides a very simple condition under which a dictionary Φ (C) obtained by exponentiating codewords from a binary linear code C satisfies the RIP with high probability. The method is to bound the difference between the dictionary Φ(C) and a second dictionary A generated by a random Bernoulli process which is known to satisfy the RIP with high probability. The difference Δ-Φ (C) is controlled by the covering radius of C, a fundamental parameter that is bounded above by the number of weights in the dual code C (the external distance of C). The main result complements a more sophisticated asymptotic analysis by Babadi and Tarokh of the distribution of eigenvalues of random submatrices of Φ(C). In this analysis, divergence from the distribution corresponding to the full Bernoulli matrix depends on a different fundamental parameter of C, namely the minimum distance of the dual code C .

Original languageEnglish (US)
Title of host publication2011 IEEE Information Theory Workshop, ITW 2011
Pages558-562
Number of pages5
DOIs
StatePublished - Dec 21 2011
Event2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brazil
Duration: Oct 16 2011Oct 20 2011

Publication series

Name2011 IEEE Information Theory Workshop, ITW 2011

Conference

Conference2011 IEEE Information Theory Workshop, ITW 2011
CountryBrazil
CityParaty
Period10/16/1110/20/11

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Covering radius and the Restricted Isometry Property'. Together they form a unique fingerprint.

  • Cite this

    Calderbank, R., Jafarpour, S., & Nastasescu, M. M. (2011). Covering radius and the Restricted Isometry Property. In 2011 IEEE Information Theory Workshop, ITW 2011 (pp. 558-562). [6089564] (2011 IEEE Information Theory Workshop, ITW 2011). https://doi.org/10.1109/ITW.2011.6089564