### Abstract

A matrix A ∈ C^{q×N} satisfies the restricted isometry property of order k with constant ∈ if it preserves the l_{2} norm of all k-sparse vectors up to a factor of 1 ± ϵ. We prove that a matrix A obtained by randomly sampling q = O(k log^{2} k log N) rows from an N × N Fourier matrix satisfies the restricted isometry property of order k with a fixed ∈ with high probability. This improves on Rudelson and Vershynin (Comm Pure Appl Math, 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).

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

Title of host publication | Lecture Notes in Mathematics |

Publisher | Springer Verlag |

Pages | 163-179 |

Number of pages | 17 |

DOIs | |

State | Published - 2017 |

### Publication series

Name | Lecture Notes in Mathematics |
---|---|

Volume | 2169 |

ISSN (Print) | 0075-8434 |

### ASJC Scopus subject areas

- Algebra and Number Theory

## Fingerprint Dive into the research topics of 'The restricted isometry property of subsampled fourier matrices'. Together they form a unique fingerprint.

## Cite this

Haviv, I., & Regev, O. (2017). The restricted isometry property of subsampled fourier matrices. In

*Lecture Notes in Mathematics*(pp. 163-179). (Lecture Notes in Mathematics; Vol. 2169). Springer Verlag. https://doi.org/10.1007/978-3-319-45282-1_11