### 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 language | English (US) |
---|---|

Title of host publication | 2011 IEEE Information Theory Workshop, ITW 2011 |

Pages | 558-562 |

Number of pages | 5 |

DOIs | |

State | Published - Dec 21 2011 |

Event | 2011 IEEE Information Theory Workshop, ITW 2011 - Paraty, Brazil Duration: Oct 16 2011 → Oct 20 2011 |

### Publication series

Name | 2011 IEEE Information Theory Workshop, ITW 2011 |
---|

### Conference

Conference | 2011 IEEE Information Theory Workshop, ITW 2011 |
---|---|

Country | Brazil |

City | Paraty |

Period | 10/16/11 → 10/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

*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