# The Restricted Isometry Property of Subsampled Fourier Matrices

arXiv: https://arxiv.org/abs/1507.01768 · HTML: https://mlsanity.com/paper/1507.01768/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2015.

## Built on by (most cited first, 7 of 7)

- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [A coherence parameter characterizing generative compressed sensing with Fourier measurements](https://mlsanity.com/paper/2207.09340/) (2022)
- [Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget](https://mlsanity.com/paper/2103.07578/) (2021)
- [Communication-Efficient Distributed SGD with Compressed Sensing](https://mlsanity.com/paper/2112.07836/) (2021)
- [Robust width: A lightweight and certifiable adversarial defense](https://mlsanity.com/paper/2405.15971/) (2024)
- [High-Dimensional Confidence Regions in Sparse MRI](https://mlsanity.com/paper/2407.18964/) (2024)
- [Tight L_∞ Sample Complexity for Low-Degree and Sparse Boolean Polynomials](https://mlsanity.com/paper/2606.17319/) (2026)

## Abstract (arXiv)

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