Walsh restricted isometries under sampling with replacement

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 \le k \le N$. The upper
bound uses the entropic encoding estimates of Burstein, Iosevich, and Krause.
We extend their sampling argument by applying the decoder to indexed row
occurrences and randomizing paired assignments to two independent samples.
The lower bound follows the Walsh subspace obstruction of Błasiok, Lopatto,
Luh, Marcinek, and Rao. Averaging over affine offsets under the fixed-sample
law gives an elementary second-moment bound uniform over all dyadic
sparsities. A reduction completes the dense and nondyadic regimes. The
sampling extension and the uniform lower-bound calculation are proved here.