Covering radius and the Restricted Isometry Property


Journal Article

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 ⊥. © 2011 IEEE.

Full Text

Duke Authors

Cited Authors

  • Calderbank, R; Jafarpour, S; Nastasescu, M

Published Date

  • December 21, 2011

Published In

  • 2011 Ieee Information Theory Workshop, Itw 2011

Start / End Page

  • 558 - 562

Digital Object Identifier (DOI)

  • 10.1109/ITW.2011.6089564

Citation Source

  • Scopus