Sharp sampling complexity for Walsh restricted isometries
Let $N = 2^d$ with $d \ge 1$, index rows and columns by $\mathbb{F}_2^d$, and let $H_N$ be the normalized Walsh matrix, $(H_N)_{a,b} = N^{-1/2}(-1)^{a \cdot b}$. For $m \ge 1$, draw row indices $a_1, \dots, a_m$ independently and uniformly from $\mathbb{F}_2^d$, with replacement, and let $\Phi$ be the $m \times N$ matrix whose $t$-th row is $\sqrt{N/m}$ times row $a_t$ of $H_N$. Let $E_{m,N,k}$ be the event that $$\tfrac12 \|x\|_2^2 \le \|\Phi x\|_2^2 \le \tfrac32 \|x\|_2^2 \quad \text{for every } x \in \mathbb{R}^N \text{ with at most } k \text{ nonzero entries},$$ so that one sample must serve every such $x$, and let $m_*(N, k)$ be the least $m \ge 1$ with $\Pr(E_{m,N,k}) \ge 0.9$. Haviv and Regev showed, for every unitary matrix with entries of modulus $O(N^{-1/2})$ in place of $H_N$, that for each fixed $\varepsilon > 0$, $O(k \log^2 k \, \log N)$ rows drawn this way give $(1 - \varepsilon)\|x\|_2^2 \le \|\Phi x\|_2^2 \le (1 + \varepsilon)\|x\|_2^2$ for all such $x$ with high probability. Błasiok, Lopatto, Luh, Marcinek and Rao showed that if each row of $H_N$ is kept independently with probability at most $c\,(k/N) \log k \, \log(N/k)$, for an absolute constant $c > 0$, and $k$ is a power of two with $\min\{\log_2 k,\ d - \log_2 k\} \ge 12 \log d$, then with probability tending to $1$ as $d \to \infty$ the kept rows annihilate a nonzero vector with at most $k$ nonzero entries.
Problem. Determine $m_*(N, k)$ up to universal multiplicative constants, uniformly over $d \ge 1$ and $1 \le k \le N$, including all necessary logarithmic factors.
Source: Stated by OpenProblemsInNLA as a quantitative form of the gap between the upper bound of Haviv and Regev (2017) and the lower bound of Błasiok, Lopatto, Luh, Marcinek and Rao (2023), who note that a gap of a factor log k remains; the sampling model, the distortion 1/2 and the success probability 0.9 are OpenProblemsInNLA's.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- FA — Functional Analysis
- Secondary
- NA, PR
- Keywords
- compressed sensing, OpenProblemsInNLA, restricted isometry property, Walsh matrices
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{blasiok2023,
author = {B{\l}asiok, Jaros{\l}aw and Lopatto, Patrick and Luh, Kyle and Marcinek, Jake and Rao, Shravas},
title = {An improved lower bound for sparse reconstruction from subsampled {W}alsh matrices},
journal = {Discrete Anal.},
year = {2023},
pages = {Paper No. 3, 9 pp.},
doi = {10.19086/da.74802},
eprint = {1903.12135},
archivePrefix = {arXiv},
}
@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},
}
@misc{openproblemsinnla-fr10,
author = {Townsend, Alex},
title = {{FR-10}: Sharp sampling complexity for Walsh restricted isometries},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/frames-and-matrix-designs/FR-10/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
Let $N = 2^d$, and sample $m$ rows of the Walsh matrix independently and uniformly, retaining repetitions. We determine, up to universal constants, the smallest $m$ for which the normalized sample has restricted isometry constant at most $1/2$ at sparsity $k$ with probability at least $0.9$: the answer is one for $k = 1$, and $k \log(2k) \log(2eN/k)$ for $2 …
In this second paper on descent methods as proof mechanisms in harmonic analysis (the first treated Bourgain's $Λ(p)$ selection theorem), entropic mirror descent gives an improved restricted isometry bound, improving sampling and recovery bounds in the Fourier Ratio program. Let $H$ be a complex $n\times n$ matrix with $H^*H=nI$ and $|H_{ij}|=1$. For fixed $0<\varepsilon<\frac14$ and $A_0>0$, independent Bernoulli row selection …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00258, "Sharp sampling complexity for Walsh restricted isometries", clopen.solutions.