Polynomial-time deterministic restricted isometries with nearly linear row count
Call $A \in \mathbb{R}^{m \times N}$ an $s$-restricted isometry if $$\|x\|_2 \le \|Ax\|_2 \le 2\|x\|_2 \quad \text{for every } x \in \mathbb{R}^N \text{ with at most } s \text{ nonzero entries}.$$ Suitably scaled random matrices with independent Gaussian entries and $O(s \log(eN/s))$ rows are $s$-restricted isometries with high probability. Proofs through coherence give deterministic examples only for $s$ up to order $\sqrt{m}$. Bourgain, Dilworth, Ford, Konyagin and Kutzarova gave the first explicit construction beyond this barrier: for some $\varepsilon > 0$, explicit complex $m \times N$ matrices whose restricted isometry constant of order $\lfloor m^{1/2 + \varepsilon} \rfloor$ is at most $m^{-\varepsilon}$, whenever $m$ is large and $m \le N \le m^{1 + \varepsilon}$.
Problem. Are there absolute constants $C, c > 0$ and a deterministic algorithm that, for all integers $N \ge 2$ and $1 \le s \le N$, outputs in time polynomial in $N$ the entries of an $s$-restricted isometry $A \in \mathbb{R}^{m \times N}$ with $m \le C s \log^c(2N)$ (the entries may be rationals of polynomial bit length)? More strongly, can such an algorithm output a matrix $B \in \mathbb{Q}^{m \times N}$ with entries of polynomial bit length, $m \le C s \log(eN/s)$ for an absolute constant $C$, and $\tfrac12 \|x\|_2^2 \le \|Bx\|_2^2 \le \tfrac32 \|x\|_2^2$ for every $x \in \mathbb{R}^N$ with at most $s$ nonzero entries?
Source: Strauss, Question 21(1) in Open Problems in Data Streams and Related Topics (IITK Workshop on Algorithms for Data Streams, 2006); the stronger optimal-row form is stated by OpenProblemsInNLA, after Rao (2025).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- FA — Functional Analysis
- Secondary
- CO, NA
- Keywords
- compressed sensing, explicit constructions, OpenProblemsInNLA, restricted isometry property
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@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)},
}
@article{rao2025,
author = {Rao, Shravas},
title = {Satisfying the restricted isometry property with the optimal number of rows and slightly less randomness},
journal = {Inform. Process. Lett.},
volume = {189},
year = {2025},
pages = {106553},
doi = {10.1016/j.ipl.2024.106553},
eprint = {2311.07889},
archivePrefix = {arXiv},
}
@article{bandeira2013,
author = {Bandeira, Afonso S. and Fickus, Matthew and Mixon, Dustin G. and Wong, Percy},
title = {The road to deterministic matrices with the restricted isometry property},
journal = {J. Fourier Anal. Appl.},
volume = {19},
number = {6},
year = {2013},
pages = {1123--1149},
doi = {10.1007/s00041-013-9293-2},
eprint = {1202.1234},
archivePrefix = {arXiv},
}
@article{bourgain2011,
author = {Bourgain, Jean and Dilworth, Stephen J. and Ford, Kevin and Konyagin, Sergei and Kutzarova, Denka},
title = {Explicit constructions of {RIP} matrices and related problems},
journal = {Duke Math. J.},
volume = {159},
number = {1},
year = {2011},
pages = {145--185},
doi = {10.1215/00127094-1384809},
eprint = {1008.4535},
archivePrefix = {arXiv},
}
@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 = {Theorem 5.14 and Open Problem 5.1},
}
@misc{openproblemsinnla-fr01,
author = {Townsend, Alex},
title = {{FR-01}: Polynomial-time deterministic restricted isometries with nearly linear row count},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/frames-and-matrix-designs/FR-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00197, "Polynomial-time deterministic restricted isometries with nearly linear row count", clopen.solutions.