Sharp sampling thresholds in low-sparsity and full-sparsity regimes

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 argument bounds the occupancy counts of the sampled rows. The note also derives sharp leading constants for uniformly sampled Walsh rows at sparsities two, three and four with distortion $1/2$: for $N=2^d$, the critical sample sizes are asymptotic to $5.2988\,d$, $16.700\,d$ and $36.387\,d$. These results do not determine the sample complexity throughout the full range of sparsities, and the elementary occupancy and random-code arguments are not asserted to be historically new.