Sharp sample complexity for restricted isometries from the cyclic Fourier matrix
Let $F_N \in \mathbb{C}^{N \times N}$ be the unitary discrete Fourier matrix, $(F_N)_{j\ell} = N^{-1/2} e^{-2\pi \mathrm{i} j\ell/N}$ for $0 \le j, \ell < N$. Draw $r_1, \dots, r_m$ independently and uniformly from $\{0, \dots, N-1\}$, repetitions allowed, and let $A \in \mathbb{C}^{m \times N}$ be $\sqrt{N/m}$ times the matrix whose $k$-th row is row $r_k$ of $F_N$. Let $\delta_s(A)$ be the supremum of $\bigl| \|Ax\|_2^2 / \|x\|_2^2 - 1 \bigr|$ over nonzero $x \in \mathbb{C}^N$ with at most $s$ nonzero entries, and let $m_*(N, s)$ be the least $m \ge 1$ with $\Pr[\delta_s(A) \le 1/3] \ge 2/3$. Haviv and Regev showed that for every fixed $\varepsilon > 0$, $O(s \log^2 s \, \log N)$ rows give $\delta_s(A) \le \varepsilon$ with high probability. Bandeira, Lewis and Mixon showed that if $s$ is large enough and divides $N$, then for every $\delta < 1/3$, $\Pr[\delta_s(A) \le \delta] \ge 2/3$ only if $m \ge C(\delta)\, s \log(eN)$, where $C(\delta) > 0$ depends only on $\delta$.
Problem. Determine the order of $m_*(N, s)$, up to absolute multiplicative constants, uniformly over all integers $N \ge 2$ and $2 \le s \le N$. In particular, which logarithmic factors are necessary?
Source: Strauss, Question 21(3) in Open Problems in Data Streams and Related Topics (IITK Workshop on Algorithms for Data Streams, 2006); in this model Bandeira, Lewis and Mixon (2018) and Bandeira (2016), Open Problem 6.1; made quantitative by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- FA — Functional Analysis
- Secondary
- NA, PR
- Keywords
- compressed sensing, OpenProblemsInNLA, restricted isometry property, subsampled Fourier matrices
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@misc{bandeira2016,
author = {Bandeira, Afonso S.},
title = {Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science},
howpublished = {Lecture notes},
year = {2016},
url = {https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf},
note = {Section 6.4 and Open Problem 6.1},
}
@misc{iitk2006,
title = {Open Problems in Data Streams and Related Topics},
howpublished = {IITK Workshop on Algorithms for Data Streams, Kanpur},
year = {2006},
url = {https://www.cse.iitk.ac.in/users/sganguly/data-stream-probs.pdf},
note = {Question 21 (Martin Strauss)},
}
@incollection{haviv2017,
author = {Haviv, Ishay and Regev, Oded},
title = {The Restricted Isometry Property of Subsampled {F}ourier Matrices},
booktitle = {Geometric Aspects of Functional Analysis: Israel Seminar ({GAFA}) 2014--2016},
editor = {Klartag, Bo'az and Milman, Emanuel},
series = {Lecture Notes in Math.},
volume = {2169},
publisher = {Springer},
address = {Cham},
year = {2017},
pages = {163--179},
doi = {10.1007/978-3-319-45282-1_11},
eprint = {1507.01768},
archivePrefix = {arXiv},
note = {Conference version in Proc. 27th ACM-SIAM SODA (2016), 288--297, doi:10.1137/1.9781611974331.ch22},
}
@article{bandeira2018,
author = {Bandeira, Afonso S. and Lewis, Megan E. and Mixon, Dustin G.},
title = {Discrete Uncertainty Principles and Sparse Signal Processing},
journal = {J. Fourier Anal. Appl.},
volume = {24},
number = {4},
year = {2018},
pages = {935--956},
doi = {10.1007/s00041-017-9550-x},
eprint = {1504.01014},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-fr02,
author = {Townsend, Alex},
title = {{FR-02}: Sharp sample complexity for restricted isometries from the cyclic Fourier matrix},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/frames-and-matrix-designs/FR-02/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For row sampling with replacement from any $N\times N$ unitary matrix, the note proves that the least number of rows giving full-space distortion at most $\delta$ with probability at least $\tau$ is asymptotic to $N\log N/h_+(\delta)$, where $h_+(\delta)=(1+\delta)\log(1+\delta)-\delta$. For flat unitary matrices, such as the cyclic Fourier matrix, the same leading constant holds for $s$-sparse restricted isometry whenever $s=N-o(N)$. The …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Sharp sampling thresholds in low-sparsity and full-sparsity regimes v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscripts/sampling_thresholds.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00198, "Sharp sample complexity for restricted isometries from the cyclic Fourier matrix", clopen.solutions.