## Abstract

We give a new explicit construction of n x N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some ε>0, large k and k^{2-ε} ≤ N ≤ k^{2+ε}, we construct RIP matrices of order k with n=O(k^{2-ε}). This overcomes the natural barrier n >> k^{2} for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure.

Original language | English (US) |
---|---|

Title of host publication | STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 637-644 |

Number of pages | 8 |

ISBN (Print) | 9781450306911 |

DOIs | |

State | Published - 2011 |

Event | 43rd ACM Symposium on Theory of Computing, STOC 2011 - San Jose, United States Duration: Jun 6 2011 → Jun 8 2011 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 43rd ACM Symposium on Theory of Computing, STOC 2011 |
---|---|

Country/Territory | United States |

City | San Jose |

Period | 6/6/11 → 6/8/11 |

## Keywords

- compressed sensing
- restricted isometry property

## ASJC Scopus subject areas

- Software

## Fingerprint

Dive into the research topics of 'Breaking the k^{2}barrier for explicit RIP matrices'. Together they form a unique fingerprint.