Restricted isometry of sampled Fourier and Hadamard matrices via entropic descent

In this second paper on descent methods as proof mechanisms in harmonic analysis (the first treated Bourgain's $\Lambda (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^{\ast }H=nI$ and $|H_{ij}|=1$. For fixed $0<\epsilon <\frac{1}{4}$ and $A_0>0$, independent Bernoulli row selection with expected cardinality $C_{\epsilon ,A_0}r\log \frac{2en}{r}\log (2r)\le m\le n/2$ preserves, after normalization by $\sqrt{m}$, the squared norm of every complex vector $y$ with $\Vert y{\Vert }_1\le \sqrt{r}\Vert y{\Vert }_2$ within a factor $1\pm \epsilon$, with failure probability at most $C{n}^{-A_0}$. This includes every $r$-sparse vector and also fully supported ones; support size enters only through this inequality. For $y=\hat{f}$ the condition is exactly $\mathrm{FR}(f{)}^2\le r$, where $\mathrm{FR}(f)=\Vert \hat{f}{\Vert }_1/\Vert \hat{f}{\Vert }_2$, giving uniform energy sampling and approximate recovery even for signals with full Fourier support. The same holds for a uniform subset of prescribed cardinality, and for discrete Fourier and real Hadamard matrices. At fixed accuracy the bound removes one sparsity logarithm from the earlier count and replaces $\log n$ by $\log \frac{2en}{r}$; for Walsh matrices it matches, up to constants, the lower bound of B\l asiok et al.\ in their range. One relative-entropy potential controls the corrections of an amplitude predictor at every scale; counting them on the symmetric difference of two samples gives the uniform estimate. We also prove the sufficient bound $C_{A_0}{\epsilon }^{-5}r\log \frac{2en}{r}\log \frac{2r}{\epsilon }$, and stable sparse recovery from $Cs\log \frac{2en}{s}\log (2s)$ measurements, with error controlled by the noise and the best $s$-term approximation.